Return to Question

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.

However the case $c \leq 1 - \tfrac 1 n$ is certainly relevant to me, and I would like to use a martingale approach to study the distribution of $\tau_0$ in this case. Intriguingly, everything I try seems to fail. 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.

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.

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.

However the case $c \leq 1 - \tfrac 1 n$ is certainly relevant to me, and I would like to use a martingale approach to study the distribution of $\tau_0$ in this case. Intriguingly, everything I try seems to fail. 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 to approach this problem are also welcome, but the focus of this question is on the martingale approach.

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.

However the case $c \leq 1 - \tfrac 1 n$ is certainly relevant to me, and I would like to use a martingale approach to study the distribution of $\tau_0$ in this case. Intriguingly, everything I try seems to fail. 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.

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 as much information as possible about 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.

However the case $c \leq 1 - \tfrac 1 n$ is certainly relevant to me, and I would like to use a martingale approach to study the distribution of $\tau_0$ in this case. Intriguingly, everything I try seems to fail. 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 to approach this problem are also welcome, but the focus of this question is on the martingale approach.

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.

However the case $c \leq 1 - \tfrac 1 n$ is certainly relevant to me, and I would like to use a martingale approach to study the distribution of $\tau_0$ in this case. Intriguingly, everything I try seems to fail. 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 to approach this problem are also welcome, but the focus of this question is on the martingale approach.