Let $0 < c < 1$. Consider the Markov chain $(X_i)$ on $\{0, 1, \dots, n\}$, with transition probabilities $$ P(k,k+1) = \left(1 - \tfrac {k}{n} \right)(1-c), \quad k = 0, \dots, n-1, $$ $$ P(k,k-1) = \tfrac{c k}{n}, \quad k = 1, \dots, n, $$ and with all remaining probability mass in $P(k,k)$ so that $\sum_j P(k,j) = 1$. I am interested in the distribution of $\tau_0$, the hitting time of $0$.

I know a general trick to obtain $\mathbb E_{l+1} \tau_l$ (the subscript $l+1$ denoting the starting point of the chain) using the invariant distribution of a modification of $(X_i)$ which is reflecting in $l$; see (Levin, Peres, Wilmer, 2009, Section 2.5) for the essential idea (with state ordering reversed). Then $\mathbb E_j \tau_0 = \sum_{l=0}^{j-1} \mathbb E_{l+1} \tau_l$. Unfortunately the resulting expression is very involved, but I am working on it. This is not the core of the problem.

The point is that I can make quite a lot of progress using a martingale approach in case $c > 1-\tfrac 1 n$, say $c = 1-\tfrac C n$ with $0 < C < 1$. As an example, the process $N_i = X_i \wedge \tau_0 + \alpha(i \wedge \tau_0)$, with $\alpha = (1-C)/n$, can be seen to be a non-negative supermartingale, so that by the optional stopping theorem, $\mathbb E_j[\tau_0] \leq \frac{jn}{1-C}$ for all $j$. I can obtain much more precise results using this approach.

Intriguingly, everything I try seems to fail when applying the martingale approach for $0 < c \leq 1-\tfrac 1 n$. For example, $$ M_i := \left( \frac{n}{n-1} \right)^i (X_i - n (1-c))$$ can be seen to be a martingale, but unfortunately the conditions of the optional stopping theorem will not be satisfied for this martingale. I have also looked at constants $\alpha, \gamma$ such that $$ N_i := \exp(-\alpha X_i +\gamma i)$$ is a non-negative supermartingale. However, in this case $\gamma$ will be a negative constant resulting in only lower bounds on $\mathbb E \tau_0$ or $\mathbb P_j(\tau_0 > i)$.

One of the intuitions behind these troubles is that the Markov chain has a certain drift towards 0 in case $c > 1-\tfrac 1 n$, whereas it seems to equilibriate around $n(1-c)$ in case $c \leq 1 -\tfrac 1 n$.

To summarize:

  • If you can please obtain upper bounds on $\mathbb P_j(\tau_0 \geq i)$ or $\mathbb E_j \tau_0$ using a martingale approach, for $0 < c \leq 1 - \tfrac 1 n$, or else
  • Please explain why a martingale approach is doomed to fail for this problem.

Other suggestions for this problem are also welcome, but the focus of this question is on the martingale approach.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.