13
$\begingroup$

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?

  • 0
    For any N or a fixed one?2010-11-10
  • 0
    For 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
  • 0
    Aha, 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
  • 0
    There'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
  • 1
    The 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

4 Answers 4