# A rigorous proof of an obvious fact about a Markov chain

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.

-
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)$). – Craig Sep 9 '11 at 1:40
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? – TMM Sep 9 '11 at 1:46
@joriki The reason is simple but a bit embarrassing. I thought the problem was interesting, but I couldn't solve it! – Byron Schmuland Sep 20 '11 at 0:07
@joriki: Byron is always very generous with his points. – George Lowther Sep 20 '11 at 0:17
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. – robjohn Sep 21 '11 at 18:30

I didn't quite dare to write this up when there was a $500$-point bounty on the question, since it seems too easy for that. It's more likely than not that I'm missing something basic, since no answer was given despite the unusual bounty; but this still seems pretty straightforward to me, so I'll spell it out and perhaps you can tell me where I'm going wrong.

I'll first restate the question to make sure the problem isn't in my misunderstanding of the question. We have $n$ states arranged cyclically, and transition probabilities that are both time-invariant and translation-invariant. For each state there are three possibilities in each step: With probability $1/2$, the state remains the same, with probability $1/2-1/n$ there is a transition to the next state in the cycle, and with probability $1/n$ there is a transition to a state selected randomly with uniform distribution over all $n$ states (including the current state and the next state in the cycle). Thus, the total transition probabilities are $1/2+1/n^2$ to remain in the same state, $1/2-1/n+1/n^2$ for the transition to the next state in the cycle, and $1/n^2$ for the transitions to the remaining $n-2$ states.

Now we want to consider this process under the condition $A$ that by time $10n$ exactly one jump has occurred (where a "jump" was clarified to also include the $1/n^2$ probability of staying in the same state). In particular, we want to bound the probability under this condition of the event $B$ that "the random walk has never taken the self loop at node 1". There are a number of potential ambiguities there. First, I assume that "never" means "not by time $10n$". Second, robjohn's question whether the "self loop" includes the $1/n^2$ term or only the $1/2$ term hasn't been answered. I don't think this makes a difference for my argument; I'll assume that the $1/n^2$ term is included, since the bound for that case also implies the bound in the other case. Third, MartianInvader's question on whether "node 1" refers to the starting node hasn't been answered. Again, I'll assume that it does, since that makes the question at least as hard as any other interpretation. In summary, I interpret $B$ as "the random walk has not remained at the initial node in any step up to time $10n$".

Now, since the transition probabilities are time-invariant, under the condition $A$ that by time $10n$ exactly one jump has occurred, each time is equally likely to be the time of the one jump, so the overall probabilities are the average of probabilities of $10n$ processes, each of which has the one jump certainly occurring at a particular time $1\le t\le10n$, and at all other times there is no jump and the remaining transition probabilities are renormalized by a factor of $1/(1-1/n)$, so they are $\frac12\frac1{1-1/n}$ and $(\frac12-\frac1n)\frac1{1-1/n}$, respectively. Each of these $10n$ processes are Markov processes. In each of these processes, the probability of never taking the self loop at the initial node is at least $(\frac12\frac1{1-1/n})^m\gt(\frac12)^m$, where $m$ is the greatest number of chances the process might have, up to time $10n$, of taking that self loop without ever taking it. Now in $10n$ steps, the process can have at most $10$ such chances without jumping, and the one jump can add at most one further chance, so $m\le11$. Therefore, in each of the processes, the probability of never taking the self loop is at least $1/2^{11}$, and hence this bound also holds for the average of these probabilities, which is the desired conditional probability.

-
Thanks for this. I will take some time to absorb it, and will comment later. – Byron Schmuland Oct 2 '11 at 13:02

Not a solution

Since my bounty expires soon, I thought that I would add a long comment about this problem. I don't claim that this is the right way to solve the problem, but this is how I see it.

Let $\alpha$ denote a fixed starting state for the process $(X_t)$, that is,
assume $\mathbb{P}(X_0=\alpha)=1$.

Intuition and rigor match up perfectly in the following modified problem:

Let $T$ be the time when the chain returns to $\alpha$ for the tenth time. By the strong Markov property, the ten transitions from state $\alpha$ up to time $T$ are independent random variables. Thus, letting $S$ to be the number of times we "stay" at $\alpha$, we have $\mathbb{P}(S=0, 0\leq t\leq T)=(1/2)^{10}$.

Now, the unique invariant probability distribution $\pi$ for this chain is uniform over the $n$ states and consequently, $\mathbb{E}(T_\alpha)=1/\pi_\alpha=n,$ where $T_\alpha$ is the return time of the state $\alpha$.

Since the average time for one return is exactly $n$, we expect about ten returns up to time $10n$. This suggests $$\mathbb{P}(S=0, 0\leq t\leq 10n)\approx \mathbb{P}(S=0, 0\leq t\leq T)=(1/2)^{10}.\hskip.7in (1)$$ If we could make this approximation rigorous, we get the needed lower bound.

In my opinion, conditioning on the number of jumps being equal to one is a red herring. That condition is only needed to control the number of returns to $\alpha$ up to time $10n$. The same could be achieved by a good approximation in (1).

I hope that somebody who is better at such arguments will take up the challenge and give a rigorous proof of this result.

-
Byron, I've tried to spell out an answer. I suspect I probably failed to address the issue you're interested in, but perhaps now you can point out more specifically which part you think is lacking in rigour. – joriki Sep 30 '11 at 14:08

Correct if I have totally misunderstood the question.

Given that 1 jump has occurred, the probability that the other $10n$ moves are counterclockwise is $(1-\frac{2}{n})^{10n}$ because the probability that any given node will move counterclockwise if it did not stay the same is $2(\frac{1}{2}-\frac{1}{n})$.

$\frac{d}{dx}(1-\frac{2}{n})^{10n}$=$\frac{2(10n)}{n}(1-\frac{2}{n})^{10n}$

$\frac{d}{dx}=0$ when $10n-1=0$ or $1-\frac{2}{n}=0$, that is when $n=2$ or $n=0.1$.

There are no stationary points or discontinuities for n>2 therefore if the function starts increasing it will carry on increasing. The probability is greater for n=3 than for n=2, so it does start increasing. For n=2, the probability is 0, which is less that your lower bound. Only integer values of n are being consided, so for n>2 the lower bound is $\frac{1}{3^{30}}$.

-