# Expectation of an event

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?

-
Yes. However, steps are differet. –  diamond kukur Jul 31 '11 at 8:59
In your step 1, I assume you mean take them uniformly and independently from $\{1,2,3,4\}$ and not $[1,4]$? –  cardinal Jul 31 '11 at 13:01
Exactly. I mean $a,b$ are taken uniformly from $\{1,2,3,4\}$. –  diamond kukur Jul 31 '11 at 14:20
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. –  Ilmari Karonen Aug 1 '11 at 2:50
This is very similar to your previous question. 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, 2, 3, including the titles. Are you user12290? If so, please have your accounts merged. –  joriki Aug 1 '11 at 5:05