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?
 A: 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.
A: 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.
A: 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.
