There is a list of length $n$ of $0’s$ and $1’s$. Each location of the list is set to $1$ with a probability of $p$ and set to $0$ with a probability of $1-p$. Suppose he picks locations randomly in the list. What is the expected number of picks until finding all the $1$’s in the list?
I believe that the expected number of picks is $1/p$ until he finds the first one in the list, but I'm having trouble extending this into finding all the $1$'s in the list. Any help would be really great, thank you.
If we keep track of our check history (so we don't ever check the same place twice), then we assert that there will be no loss of generality if we pick places in sequential order, rather than random.
Then if $K$ is the index of the last
1checked, we are looking for $\mathsf E(K)$.The probability that: the $k$-th item checked is a
1and that all of the $n{-}k$ unchecked items that remain are0, is: $\mathsf P(K{=}k) = \color{navy}{\underline{\qquad}}$.$$\mathsf E(K) = \sum_{k=0}^{n}\, k\;\mathsf P(K{=}k)$$
Hint: rearrange the resulting expression so you may use the Geometric Series closed forms $$\begin{align}\sum_{r=0}^n a^r & = \frac{a^{n+1}-1}{a-1}\\[1ex] \sum_{r=0}^n r\,a^r & = \frac{a\,\big(n a^{n+1}-(n+1) a^n+1\big)}{(a-1)^2}\end{align}$$