Information theory aside: In practice all because you can't write bit-by-bit and if you leave full bytes untouched there still might be enough information for an attacker to get information, especially if it's of the "did this computer once store this file" kind of information, not the actual file contents.

If I'm not completely mistaken overwriting the file once will be enough to prevent recovering with logical means, that is, reading the bits the way the manufacturer intended you to, physical forensics can go further by being able to discern "this bit, before it got overwritten, was a 1 or 0" by looking very closely at the physical medium, details on how much flipping you need to defeat that will depend on the physical details.

And I wouldn't be too terribly sure about that electro magnet you built into your case to erase your HDD with a panic button: It's in a fixed place, will have a fixed magnetic field, it's going to scramble everything sure but the way it scrambles is highly uniform so the bits can probably be recovered. If you want to be really sure buy a crucible and melt the thing.

Also, may I interest you in this stylish tin-foil hat, special offer.

If you delete normally, only the index of the files are removed, so the data can be recovered by a recovery program reading the "empty" space on the disk and looking for readable data.

If you do a single pass erase, the bits will overwritten one time. About half the bits will be unchanged, but that makes little difference. Any recovery software trying to read it will read the newly written bits instead of the old ones and will not be able to recover anything.

However, forensic investigation can probably recover data after a single pass erase. The shred command defaults to 3 passes, but you can do many more if you need to be even more sure.

Unless you have data that someone would spend large sums on forensics to recover, 1 to 3 passes is probably enough.

If it's completely random then 50%, that's how stream ciphers works.