Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

At each iteration I take three random integers (i,j,k) from [1,1000] with replacement and do the following:

1.  Set A[i]=1

2a. If A[j]=1 and A[k]=0, then set A[k]=1

2b. if A[j]=0 and A[k]=1, then set A[k]=1

2c. If A[j]=A[k]=0, do nothing

and go back to the previous step.

For example let the first drawn triplet be (10,12,25). Set A[10]=1 and now we can not apply 2a or 2b. Let 2nd drawn triplet be (12,25,28). So, A[12]=1 and can not apply 2a or 2b now. However when go back to 1st step, using 2a set A[25]=1. After coming 2nd step, A[28] will be 1. Now drawn 3rd triplet (i_3, j_3, k_3) and go back to step 1, 2.

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

Before k+1-th triplet drawn, assume t many cell are filed with 1. But can not write any recursive relation before k+2-th triplet drawn.

Please also mention some books or papers which may help to solve these kind of problems.

share|improve this question
    
and presumably 2d. If A[j]=A[k]=1, do nothing. 2b also looks as if it is a "do nothing" step unless it should say something else. –  Henry Sep 30 '11 at 6:31
add comment

1 Answer 1

up vote 1 down vote accepted

The recursion looks easier to write down than to solve.

If you do step 1 when you have $t$ cells marked with 1, then there is a probability $\frac{n-t}{n}$ of moving to having $t+1$ cells marked with 1.

If you do step 2 when you have $t$ cells marked with 1, then there is a probability $\frac{n-t}{n}\times\frac{t}{n}$ of moving to having $t+1$ cells marked with 1.

Suppose $T_{k}$ is the number of cells marked with 1 after $k$ draws, and $S_k$ is the number of cells marked with 1 after step 1 of the $k$th draw. Then $$\Pr(S_{k+1}=t)=\frac{t}{n} \Pr(T_k=t) + \frac{n-t+1}{n}\Pr(T_k=t-1),$$ $$\Pr(T_{k+1}=t)=\frac{n^2-nt+t^2}{n^2} \Pr(S_{k+1}=t) + \frac{(n-t+1)(t-1)}{n^2}\Pr(S_{k+1}=t-1).$$

share|improve this answer
    
A recursion like this should be able to be analyzed using generating functions. Let $S(x,y) = \sum_{k=0}^\infty \sum_{t=0}^\infty Pr(S_k=t) x^k y^t$ and similarly for $T(x,y)$; then the first recursion becomes the functional equations $S(x,y) = 1 + x(\frac tn + y\frac{n+t-1}n) T(x,y)$ (I think the $1+{}$ accurately reflects the initial case) and the second recursion gives a similar functional equation for $T(x,y)$ in terms of $S(x,y)$. Solving for $S(x,y)$ should give a rational function of $x$ and $y$, whose coefficients might be able to be extracted. –  Greg Martin Sep 30 '11 at 8:38
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.