1
$\begingroup$

Let $S[4]$ be a binary array with elements of $S$ are taken uniformly and independently from $\{0,1\}$. Also take $k$ uniformly from $\{0,1\}$. Take $i=1$. Now run the following process:

  1. Take $a,b$ uniformly and independently from $[1,4]$
  2. Change $k=(k+S[a]) \bmod 2$
  3. $S[b]=(k+S[i])\bmod 2$
  4. $i=(i+1) \bmod 4$

Run the whole process (1,2,3,4) until all elements of S are filled with 0. What is expected number of runs for this event?

  • 0
    Yes. However, steps are differet.2011-07-31
  • 0
    In your step 1, I assume you mean take them uniformly and independently from $\{1,2,3,4\}$ and not $[1,4]$?2011-07-31
  • 0
    Exactly. I mean $a,b$ are taken uniformly from $\{1,2,3,4\}$.2011-07-31
  • 0
    I probably won't have time to spend actually solving this, but it shouldn't be hard to build the transition matrix for this Markov chain. Naively, the state space would be $\{0,1,2,3\}\times\{0,1\}^4$, but you can eliminate the variable $i$ from the state by replacing step 4 with "shift all elements of $S$ down by one step". That leaves you with 15 transient states and one absorbing one.2011-08-01
  • 0
    ...except I forgot to include $k$ in the state space; that gives one factor of $\{0,1\}$ more.2011-08-01
  • 2
    This is very similar to [your previous question](http://math.stackexchange.com/q/53462). You should mention what's different, and explain what aspect of this you're having difficulties with despite the very detailed solution Ilmari provided in his answer there; otherwise a lot of effort might unnecessarily be duplicated. Also there's some similarity with this series of questions: [1](http://math.stackexchange.com/q/50048), [2](http://math.stackexchange.com/q/48166), [3](http://math.stackexchange.com/q/47520), including the titles. Are you user12290? If so, please have your accounts merged.2011-08-01
  • 0
    Yes, it is similar to my previous question. However, here $i$ is deterministic. Hence, I had a doubt whether the previous approach will be applicable here or not. Yes, I am user 12290. Ok, I will submit question from my one account.2011-08-01

0 Answers 0