# Expected number of steps before three counters reach N modulo 2N at the same time

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?

-
For any N or a fixed one? – Jens Nov 10 '10 at 21:59
For any N, but the exact expected value is not important, a reasonable upper bound is good. – hakos Nov 10 '10 at 22:14
@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. – Qiaochu Yuan Nov 10 '10 at 23:28
Aha, thanks for the clarification, in that sense N is fixed in advance. – hakos Nov 10 '10 at 23:43
The answer is "obviously" proportional to N<sup>3</sup>, the size of the state space, but I can't say more off the top of my head. – Michael Lugo Nov 11 '10 at 6:31

Still working on a general solution, but here are a few exact solutions for small $N$.

For $N = 1..8$ the exact values are 10, $\frac{416}{5}$, $\frac{10294}{35}$, $\frac{18481664}{25823}$, $\frac{235115486250}{165493097}$, $\frac{1690479776164}{681135455}$, $\frac{25081308000562315334439801586}{6314587098176165651428105}$, $\frac{282872889746351048352862015165111214080}{47431617359482015647230177875265569}$.

Numerical values: 10, 83.2, 294.114, 715.706, 1420.7, 2481.86, 3971.96, 5963.8.

These were computed "the hard way" by making a large state diagram, exploiting a lot of symmetry, and then solving a system of linear equations. There are 165 states, for example, in the case of $N=8$, which means solving for 165 equations in 165 unknowns. There is undoubtedly a more clever way to compute this.

I offer the bound $c \cdot N^3$ without proof; I believe the expected number of steps is asymptotic to this value with $c \approx 12$.

Added 13-Nov-2010: The following table provides strong evidence for the $12N^3$ asymptotic bound given earlier.

 N        E(N)    12(N^3)

1        10.0        12
2        83.2        96
3       294.1       324
4       715.7       768
5      1420.7      1500
6      2481.9      2592
7      3972.0      4116
8      5963.8      6144
9      8530.2      8748
10     11743.8     12000
11     15677.6     15972
12     20404.2     20736
13     25996.5     26364
14     32527.3     32928
15     40069.3     40500
16     48695.3     49152
17     58478.1     58956
18     69490.5     69984
19     81805.3     82308
20     95495.3     96000
21    110633.2    111132
22    127291.9    127776
23    145544.0    146004
24    165462.6    165888
25    187120.2    187500


Edit 11-Nov-2010:

Here is the system of linear equations for $N=3$. Ostensibly there are $6^3 = 216$ states but by symmetry this can be reduced to $20$. The three subscripts on each variable represent the distance from the goal state in each dimension. In accordance with the problem statement we start at the farthest node from the goal. Thus we are solving for $x_{3,3,3}$ here. (The answer is $\frac{10294}{35}$).

I show this tedium in hopes someone can figure out how to generalize.

$x_{0,0,0}=0$

$x_{0,0,1}=\frac{1}{6} x_{0,0,0}+\frac{1}{6} x_{0,0,2}+\frac{2}{3} x_{0,1,1}+1$

$x_{0,0,2}=\frac{1}{6} x_{0,0,1}+\frac{1}{6} x_{0,0,3}+\frac{2}{3} x_{0,1,2}+1$

$x_{0,0,3}=\frac{1}{3} x_{0,0,2}+\frac{2}{3} x_{0,1,3}+1$

$x_{0,1,1}=\frac{1}{3} x_{0,0,1}+\frac{1}{3} x_{0,1,2}+\frac{1}{3} x_{1,1,1}+1$

$x_{0,1,2}=\frac{1}{6} x_{0,0,2}+\frac{1}{6} x_{0,1,1}+\frac{1}{6} x_{0,1,3}+\frac{1}{6} x_{0,2,2}+\frac{1}{3} x_{1,1,2}+1$

$x_{0,1,3}=\frac{1}{6} x_{0,0,3}+\frac{1}{3} x_{0,1,2}+\frac{1}{6} x_{0,2,3}+\frac{1}{3} x_{1,1,3}+1$

$x_{0,2,2}=\frac{1}{3} x_{0,1,2}+\frac{1}{3} x_{0,2,3}+\frac{1}{3} x_{1,2,2}+1$

$x_{0,2,3}=\frac{1}{6} x_{0,1,3}+\frac{1}{3} x_{0,2,2}+\frac{1}{6} x_{0,3,3}+\frac{1}{3} x_{1,2,3}+1$

$x_{0,3,3}=\frac{2}{3} x_{0,2,3}+\frac{1}{3} x_{1,3,3}+1$

$x_{1,1,1}=\frac{1}{2} x_{0,1,1}+\frac{1}{2} x_{1,1,2}+1$

$x_{1,1,2}=\frac{1}{3} x_{0,1,2}+\frac{1}{6} x_{1,1,1}+\frac{1}{6} x_{1,1,3}+\frac{1}{3} x_{1,2,2}+1$

$x_{1,1,3}=\frac{1}{3} x_{0,1,3}+\frac{1}{3} x_{1,1,2}+\frac{1}{3} x_{1,2,3}+1$

$x_{1,2,2}=\frac{1}{6} x_{0,2,2}+\frac{1}{3} x_{1,1,2}+\frac{1}{3} x_{1,2,3}+\frac{1}{6} x_{2,2,2}+1$

$x_{1,2,3}=\frac{1}{6} x_{0,2,3}+\frac{1}{6} x_{1,1,3}+\frac{1}{3} x_{1,2,2}+\frac{1}{6} x_{1,3,3}+\frac{1}{6} x_{2,2,3}+1$

$x_{1,3,3}=\frac{1}{6} x_{0,3,3}+\frac{2}{3} x_{1,2,3}+\frac{1}{6} x_{2,3,3}+1$

$x_{2,2,2}=\frac{1}{2} x_{1,2,2}+\frac{1}{2} x_{2,2,3}+1$

$x_{2,2,3}=\frac{1}{3} x_{1,2,3}+\frac{1}{3} x_{2,2,2}+\frac{1}{3} x_{2,3,3}+1$

$x_{2,3,3}=\frac{1}{6} x_{1,3,3}+\frac{2}{3} x_{2,2,3}+\frac{1}{6} x_{3,3,3}+1$

$x_{3,3,3}=x_{2,3,3}+1$

-

Here's a sketch of another derivation of the hitting time for one counter (re Mike's answer).

Consider the usual $\pm 1$ random walk on the integer line. It is well known that the expected time it takes to reach distance $N$ is $N^2$. In our case reaching distance $N$ and reaching the value $N$ modulo $2N$ is the same, since we can't get to $\pm 3N$ without moving through $\pm N$.

We move the specified counter in expectation once every three steps, and therefore it's $3N^2$ and not $N^2$ (because the direction of movement and this "waiting for our turn" are independent).

This argument shows that the case of one counter is rather special.

-
Nice intuitive explanation for my result! Does this imply anything immediate about the order of the expected value in the three-counter case? – Mike Spivey Nov 12 '10 at 18:07
In the three- (or two-)counter case, the "modular" walk is not equivalent to the non-modular one, so I guess not. What one could try is do some experiments and find out what are the nominal values of all counters when they reach (N,N,N) modulo 2N. – Yuval Filmus Nov 12 '10 at 18:09

This question in its full generality is probably best tackled by some generating function approach as Qiaochu points out. I toyed around with the $N=1$ case and got some interesting results that I am sharing below. For the $N=1$ case, we don't have to distinguish between the $+1$ and the $-1$s. In fact, a nice visualization is to think of a row of bulbs one of which is randomly toggled at each stage. Question: Given that they are all off initially, how long does it take on an average for all of them to light up?

Let $f_k$ be the expected number of steps for all bulbs to light up starting from $k$ lighted bulbs out of a total of $n$ bulbs. Then, we have the recursions

$f_0 = 1 + f_1$

$f_k = 1 + \frac{k}{n} f_{k-1} + \frac{n-k}{n} f_{k+1}$

$f_n = 0$

We need to solve for $f_0$. I cheated on solving the recursion by numerically solving it for various $n$ and appealing to OEIS. The answer turns out to be

$f_0 = n \sum_{j=0}^{n-1} \frac{2^j}{j+1}$.

In the case of $3$ bulbs, the answer is $10$. I don't know how to extend this approach to the case of arbitrary $N$ without making it messy. I am not very comfortable with generating function based solution approaches. If someone were to post one for this problem, I would love to learn the techniques of "generating functionology" through that.

-
BTW, your answer is entirely for the N=1 case, correct? "In the case of 3 bulbs…" doesn't mean N=3. :-) – ShreevatsaR Nov 11 '10 at 10:42
@ShreevatsaR - yes, I chose an unfortunate notation with $N$ as the OP intended and $n$ as the number of counters which is $3$ in the OP's question. – Dinesh Nov 11 '10 at 18:20

Here's another direction of attack. The expected number of steps before a single, given counter reaches $N$ is exactly $3N^2$.

As in I. J. Kennedy's approach, let $x_k$ denote the expected time before a given counter reaches $N$ given that the counter starts $k$ steps away from $N$. Then the $x_k$'s satisfy, for $1 \leq k \leq N-1,$ $$x_k = \frac{1}{6} (1 + x_{k+1}) + \frac{4}{6} (1 + x_k) + \frac{1}{6} (1 + x_{k-1}),$$ with boundary conditions $x_0 = 0$ and $x_N = \frac{2}{3} (1 + x_N) + \frac{1}{3}(1 + x_{N-1}),$ the second of which simplifies to $x_N = x_{N-1} + 3$.

The difference equation reduces to $$x_{k+1} - 2x_k + x_{k-1} = -6,$$ and thus is linear, nonhomogeneous, and second-order. The solution technique is very similar to that for the corresponding differential equation. The characteristic equation for the homogeneous difference equation is $r^2 -2r + 1 = 0$, which means we have the double root $r = 1$. Thus the general solution to the homogeneous equation is $y_k = A(1)^k + B k (1)^k = A + Bk$. We then use the method of undetermined coefficients with $z_k = Ck^2$ as our candidate to find a particular solution to the nonhomogeneous equation. This yields $C = -3$. Thus the general solution to the difference equation is $$x_k = A + Bk - 3k^{2}.$$ Now, we use the boundary conditions to find $A$ and $B$. These yield $A = 0$ and $$A + BN - 3N^2 = A + B(N-1) - 3(N-1)^2 + 3.$$ Solving this, we have $B = 6N$. Thus our solution is $$x_k = 6Nk - 3k^2,$$ which means $$x_N = 3N^{2}.$$

I don't have time right now to pursue this further, but maybe someone else can use this to find a reasonable upper bound for the time until all three counters hit $N$ simultaneously like the OP wants. In particular, though, if it takes on the order of $N^2$ steps on average for a given counter to reach $N$ for the first time it seems that it should take more than the order of $N^3$ steps on average for all three of them to hit $N$ together.

-