In several proofs of the expected lookup length in an open addressing hash table, an assumption is made (which is said to follow from the "simple uniform hashing assumption":
Given a hash table with n slots and m keys in it, the probability that any particular slot is occupied is m/n.
I'm having difficulty creating a mental model involving an experiment and a sample space in which I can derive this.
I'm thinking of a sample space consisting of m-tuples of keys. The experiment is to randomly select one such tuple. The event A is the set of all such tuples that have at least 1 key in them that hashes into the given slot.
The probability of A then is
1 - (the probability that none of the m keys hash to the given slot). So
1 - ((n-1)/n)^m. But that's not equal to