Consider the following problem 11.2-6 from CLRS book:
Suppose we have stored $n$ keys in a hash table of size $m$, with collisions resolved by chaining, and that we know the length of each chain, including the length $L$ of the longest chain. Describe a procedure that selects a key uniformly at random from among the keys in the hash table and returns it in expected time $O(L(1+\frac{1}{\alpha}))$.
I found the solution:
Choose one of the $m$ spots in the hash table at random. Let $n_k$ denote the number of elements stored at $T[k]$. Next pick a number $x$ from $1$ to $L$ uniformly at random. If $x < n_j$ , then return the $x^{th}$ element on the list. Otherwise, repeat this process. Any element in the hash table will be selected with probability $\frac{1}{mL}$, so we return any key with equal probability. Let $X$ be the random variable which counts the number of times we must repeat this process before we stop and p be the probability that we return on a given attempt. Then $E[X] = p(1+\alpha)+(1−p)(1+E[X])$ since we’d expect to take $1+\alpha$ steps to reach an element on the list, and since we know how many elements are on each list, if the element doesn’t exist we’ll know right away. Then we have $E[X] = \alpha+ \frac{1}{p}$. The probability of picking a particular element is $\frac{n}{mL} = \frac{\alpha}{L}$, so we have $E[X] = \alpha + \frac{L}{\alpha} = L(\frac{\alpha}{L} + \frac{1}{\alpha}) = O(L(1 + \frac{1}{\alpha})).$
I have two questions:
Why Any element in the hash table will be selected with probability $\frac{1}{mL}$?
why $E[X] = p(1+\alpha)+(1−p)(1+E[X])$ contains $(1+E[X])$ and then $E[X] = \alpha+ \frac{1}{p}$?
