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

Solution 1:

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 $

Solution 2:

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.

Solution 3:

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.

Solution 4:

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.