1

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.

Community
  • 1
user12290
  • 1,305
  • This is easy to solve (exactly) with dynamic programming, but I'm not sure how to do it analytically. – Neil G Jun 28 '11 at 08:08
  • I'm assuming if $j_2, j_3$ are both zero you just continue? – mathmath8128 Jun 28 '11 at 08:15
  • What means that you are taking random variables from [1,1000] with replacement? – SBF Jun 28 '11 at 08:19
  • @Gortaur: it means that you $j_1$ could equal $j_2$, etc. – Neil G Jun 28 '11 at 08:41
  • Anyway, the answer is 2055.23... Looking forward to seeing if anyone can do this analytically. – Neil G Jun 28 '11 at 08:44
  • @Neil - could you please clarify how did you obtain it? Since the time horizon of the problem is infinite, for me it's not clear how to apply DP. I also thought about finite state ($2^{1000}$) MC but if we can calculate there an average time of reaching a single state? – SBF Jun 28 '11 at 08:53
  • @Gortaur: There are only 1001 states. See the linked answer. Looks like I made a mistake in my code; the answer is 2861... – Neil G Jun 28 '11 at 18:55

0 Answers0