1
$\begingroup$

Possible Duplicate:
Expectation of an event

Let $A$ be an array of length 1000 with all entries 0. I want to fill up $A$ with ones using the following approach:

Each time I take three random integers $(j_1,j_2,j_3)$ from [1,1000] with replacement such that

  1. Set $A[j_1]=1;$

  2. If $A[j_2]=1$ and $A[j_3]=0$, then set $A[j_3]=1$ or, if $A[j_2]=0$ and $A[j_3]=1$, then set $A[j_2]=1$.

What is the expected number of such trials to fill up A with all ones?

If $A[j_2]=A[j_3]=0$, just continue. With replacement means $j_2$ may be equal to $j_3$ or any previous $j_2$ etc.

  • 0
    @Gortaur: There are only 1001 states. See the linked answer. Looks like I made a mistake in my code; the answer is 2861...2011-06-28

0 Answers 0