12
$\begingroup$

So I'm having trouble writing down a rigorous proof of something that seems very clear.

Consider the following Markov chain on a ring: with probability $1/2$, it stays where it is, with probability $1/2-1/n$ it moves counterclockwise, and with probability $1/n$ it jumps to a random node. When the latter has happened, we'll say a jump has occurred.

Let $A$ be the event that by time $10n$, exactly one jump has occurred. Let $B$ be the event that the random walk has never taken the self loop at node $1$.

I want to prove that $P(B|A)$ is lower bounded by some constant independent of $n$. I'm actually guessing that $P(B|A) \geq 1/2^{11}$.

This seems obvious to me: conditional on $A$, the number of times the chain transitions into node $1$ by time $10n$ is at most $11$, and the probability of not taking the self-loop is $1/2$ each time. But how to say this formally?

Edit: Actually the above sketch is somewhat problematic: as Craig points out in the comments, taking exactly one jump changes the probabilities of taking the self loop whenever the chain is at node $1$. But, presumably, the chance of taking the counterclockwise transition should only increase, since the number of jumps is below what you'd expect in $10n$ transitions. So I'd be perfectly satisfied with the bound $(1/2-1/n)^{11}$ instead.

  • 1
    Just want to clarify one thing: Conditional on _not_ jumping at node 1, the probability of not taking the self-loop is $>1/2$ (in fact, it is $n/2(n-1)$).2011-09-09
  • 1
    What exactly is $n$? The number of nodes in the ring? And can jumping to a random node also be to the same node and/or the counterclockwise node?2011-09-09
  • 0
    @Thijs Laarhoven - right, $n$ is the number of nodes in the ring. A jump goes to each of the $n$ nodes with probability $1/n$ - so a jump can leave one in the same place (with probability $1/n$).2011-09-09
  • 0
    Are we assuming that we start at node 1? I think it matters.2011-09-19
  • 1
    @Byron, perhaps you could offer some insight into what made you put 500 of your hard- and well-earned points up for this?2011-09-19
  • 5
    @joriki The reason is simple but a bit embarrassing. I thought the problem was interesting, but I couldn't solve it!2011-09-20
  • 5
    @joriki: Byron is always very generous with his points.2011-09-20
  • 0
    I think we need a bit more specification of what would constitute a rigorous/formal proof here. The argument given in the question seems perfectly fine to me, and I'm not sure what level of rigour it's supposed to be developed at. With $k$ the number of visits to $1$ in $10n-1$ steps given one jump, we have $k\le11$ and thus $P(B|A)\gt\sum_jP(k=j|A)(1/2-1/n)^j\ge\sum_jP(k=j|A)(1/2-1/n)^{11}=(1/2-1/n)^{11}$. Which part of that do you want fleshed out?2011-09-20
  • 1
    @joriki If I had to put my finger on it, I suppose my problem is with the (unstated) assumption that $$P(k=j,B|A)\geq P(k=j|A)(1/2-1/n)^j.$$ As far as I can see, conditioned on $A$, the process $(X_j)_{j=1}^{10n}$ is not Markov so I'm not sure how to justify the product on the right. On the other hand, I may be giving this problem more respect than it deserves. I hope there is a short solution.2011-09-20
  • 0
    @joriki - I personally would like to see the first inequality (e.g. $P(B|A)>\sum_j \ldots$) fully fleshed out.2011-09-20
  • 2
    What exactly is meant by "the self loop at node $1$"? Does it include the probability $\frac{1}{n}$ jump jumping to node $1$ (with probability $\frac{1}{n}$)? Or is it simply the $\frac{1}{2}$ chance of remaining at node $1$? Some of your comments seem to indicate the latter.2011-09-21

3 Answers 3