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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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

Your Answer


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

Browse other questions tagged or ask your own question.