0
$\begingroup$

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.

  • 0
    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.2011-09-30

1 Answers 1

1

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).$

  • 0
    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.2011-09-30