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.