We have three counters, $i, j, k$, all initialized to zero. Each step consists of adding or subtracting one from one of the counters, so $(\Delta i, \Delta j, \Delta k)$ is selected among $(\pm1, 0, 0), (0, \pm1, 0), (0, 0, \pm1)$, each with probability 1/6. What is the expected number of steps before all the counters are N modulo 2N at the same time?
Expected number of steps before three counters reach N modulo 2N at the same time
13
$\begingroup$
probability
-
0For any N or a fixed one? – 2010-11-10
-
0For any N, but the exact expected value is not important, a reasonable upper bound is good. – 2010-11-10
-
0@hakos: what Jens means is that do you want N to be fixed in advance, or are you okay with the counters all being 1 mod 2, or all being 2 mod 4, or all being 3 mod 6, or... the point being the second problem is (I think) harder. – 2010-11-10
-
0Aha, thanks for the clarification, in that sense N is fixed in advance. – 2010-11-10
-
0@hakos: in the first case there is a fairly automatic, if tedious, way to solve this problem with generating functions. I am hoping someone has a nicer solution. – 2010-11-10
-
0@Qiaochu Does that approach allow you to estimate the expectation? It seems you'll just get an unmanageable (multiple) sum. – 2010-11-11
-
0There's always the trick of substituting an n'th root of unity, but here you'll need to sum over several substitutions and it doesn't seem to help. – 2010-11-11
-
1The answer is "obviously" proportional to N3, the size of the state space, but I can't say more off the top of my head. – 2010-11-11