3 ms·

> Turns out if your hash function is N bits you will need to have 2^(N/2) items before see two hashed to the same thing by chance. No no no. That's not how pro

by ebg13 7y ago

> Turns out if your hash function is N bits you will need to have 2^(N/2) items before see two hashed to the same thing by chance. No no no. That's not how probability works. You will see that many on average, but you don't "need to" anything before you can see a collision. You could get collisions on the next 100 files. It's just unlikely. The bitspace bounds the denominator of match probability for each file independently, it does not count files. Unlikely events happen all the time somewhere.

fyp 7y ago
The precise statement is that you need to have O(2^(N/2)) items before the probability of finding a hash collision is greater than 50% (or whatever nontrivial percentage). English is hard and I think whoever cares about the details can look it up themselves.
- ebg13 7y ago
  > I think whoever cares about the details can look it up themselves Your statement was an incredibly common and often repeated misperception of probability and circumstance. Someone looking it up for themselves, as you suggest, is more likely than not to encounter dozens of wrong statements on the subject before they ever find a right one. I think it behooves us to not add more misinformation to the pile.
- daveFNbuck 7y ago
  The precise statement should be Omega, not O, since you're doing a lower-bound.
zeroxfe 7y ago
> No no no. That's not how probability works. Pretty sure GP understands how probability works, maybe take a more charitable interpretation of their comment?
- ebg13 7y ago
  > Pretty sure GP understands how probability works, maybe take a more charitable interpretation of their comment? There are many circumstances where I fully agree with charitable interpretation, but this is not one of them. In this case it's tantamount to saying that it's ok to mislead people because they should just know better. (especially in light of their reply) If you are correct about what they understand, then I'd rather they were more charitable to the other people who don't already understand it by not writing things that are wrong and potentially dangerous. Someone out there is going to learn about this by googling, see 19 out of 20 people get it wrong, implement a system that relies on the majority false information, and then destroy the lives of a bunch of innocent people. It may not be someone you know, and it may not impact your neighbors, but it happens _all_ the time. I care about the harm of spreading misinformation, and I think you should as well.

by ebg13 7y ago

fyp 7y ago

The precise statement is that you need to have O(2^(N/2)) items before the probability of finding a hash collision is greater than 50% (or whatever nontrivial percentage). English is hard and I think whoever cares about the details can look it up themselves.

ebg13 7y ago
> I think whoever cares about the details can look it up themselves Your statement was an incredibly common and often repeated misperception of probability and circumstance. Someone looking it up for themselves, as you suggest, is more likely than not to encounter dozens of wrong statements on the subject before they ever find a right one. I think it behooves us to not add more misinformation to the pile.
daveFNbuck 7y ago
The precise statement should be Omega, not O, since you're doing a lower-bound.

zeroxfe 7y ago

> No no no. That's not how probability works. Pretty sure GP understands how probability works, maybe take a more charitable interpretation of their comment?

ebg13 7y ago
> Pretty sure GP understands how probability works, maybe take a more charitable interpretation of their comment? There are many circumstances where I fully agree with charitable interpretation, but this is not one of them. In this case it's tantamount to saying that it's ok to mislead people because they should just know better. (especially in light of their reply) If you are correct about what they understand, then I'd rather they were more charitable to the other people who don't already understand it by not writing things that are wrong and potentially dangerous. Someone out there is going to learn about this by googling, see 19 out of 20 people get it wrong, implement a system that relies on the majority false information, and then destroy the lives of a bunch of innocent people. It may not be someone you know, and it may not impact your neighbors, but it happens _all_ the time. I care about the harm of spreading misinformation, and I think you should as well.