1

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?

Ilmari Karonen
  • 26,117
diamond kukur
  • 43
  • Yes. However, steps are differet. – diamond kukur Jul 31 '11 at 08: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 01 '11 at 02:50
  • ...except I forgot to include $k$ in the state space; that gives one factor of ${0,1}$ more. – Ilmari Karonen Aug 01 '11 at 03:12
  • 2
    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 01 '11 at 05:05
  • 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. – diamond kukur Aug 01 '11 at 07:22

0 Answers0