4
$\begingroup$

Consider the following random walk: enter image description here

Namely, if $S_i$ is the state at time $i$, then $\Pr(S_{i+1}=1|S_i=0)=1$, and for every $s>0$ we have $$S_{i+1}|S_i=s= \begin{cases} s+1 & \text{w.p. }1-p\\ s-1 & \text{w.p. }p \end{cases}. $$ In my application, $p>\frac{1}{2}$. I'm interested in two quantities, $\Pr(S_T > H)$ and $\mathbb E(S_T)$. My intuition is that $\Pr(S_T > C \ln T)\leq \frac{1}{T^2}$ for some global constant $C$, and that $\mathbb E(S_T)=O(1)$. However, I couldn't show it (yet).

Any ideas?


Here are some trivial claims. First, $\Pr(S_T > H) \leq \exp(-\frac{H^2}{T})$ due to Azuma's inequality, but that doesn't use the value $p$ nor the fact that $p> \frac{1}{2}$. Second, $\mathbb E(S_T) \leq O(\sqrt{T})$ since $S_t$ is stochastically dominated by a symmetric random walk, for which the expected place at time $T$ is $O(\sqrt{T})$.

The stationary distribution is easy to find, being $\pi_0=1-\frac{1}{2p}$ and $\pi_i = \frac{\pi_0}{p} \left(\frac{1-p}{p}\right)^{i-1}$, but I'm not sure how to use it.

$\endgroup$
8
  • 1
    $\begingroup$ Consider a symmetric random walk. Then (I think) your goal is equivalent to asking what is $Pr(S_T>H \lor S_T <-H)$, and what is $\mathbb{E}[|S_T|]$. $\endgroup$
    – nir shahar
    May 13 at 13:23
  • $\begingroup$ I think you are right only if $p=0.5$. $\endgroup$
    – omerbp
    May 13 at 13:29
  • 1
    $\begingroup$ You are interested in biased random walk on the line with a reflective (or reflecting) barrier at zero. $\endgroup$ May 13 at 14:43
  • 1
    $\begingroup$ Since at least half of the time you're not at the origin, it is certainly not the case that $\mathbb{E}(S_T) = o(1)$. Moreover, from the stationary distribution we can calculate that $\mathbb{E}(S_T) \longrightarrow 1/2(2p-1)$ (I think). $\endgroup$ May 13 at 14:53
  • 1
    $\begingroup$ Some info. Let $P_i^t = P(S_t = i)$ and $E^t = E[S_T]$. Then you can express $P_i^{t+1}$ in terms of $P_j^{t}$, and therefore $E^{t+1}$ in terms of $E^{t}$ and $P_j^{t}$. It's simple but a bit monotone. If I didn't make a mistake, then you should get $E^{t+1} = E^t + 1 - 2p (1 - P_0^t)$. Since $P_0^t$ is $0$ for odd $t$, we have $E^{t+1} = E^t + (1-2p)$ for odd $t$ and $E^{t+2} = E^t + 2 - 4p +2p P_0^t$. I also did some experiments, and $P_0^{2t} \to 2 - \frac 1p$, and for $P_0^t = 2-\frac 1p$, $E^{t+2} = E^t$. I don't know how fast $P_0^{2t}$ converges to this value though. $\endgroup$
    – user114966
    May 13 at 23:15
1
$\begingroup$

Suppose that $S_T > C\ln T$. Let $T_0-1$ be the last time that the random walk reached the origin. Thus if we run an unconstrained biased random walk starting at position $1$ at time $T_0$, we reach beyond $C\ln T$ at time $T$. This can only happen if $T-T_0 \geq C\ln T$.

The probability that an unconstrained biased random walk starting at position $x$ ends up to the right of $x$ after $L$ steps is exponentially small in $L$, by Hoeffding's inequality. In your case, $L \geq C\ln T$, and so this probability is polynomially small in $T$. Taking a union bound over all possible values of $T_0$ (at most $T$ of them), you can choose $C$ so that the error probability is at most $\frac{1}{T^d}$ for $d$ of your choice.

(More formally, choose the $\pm 1$ steps $\xi_1,\ldots\xi_T$ of your walk ahead of time. You start at some fixed $S_0$, which here is implicitly assumed to be $S_0 = 1$, and then $S_{n+1} = |S_n + \xi_{n+1}|$. If $S_T > C\ln T$ then $S_{T_0} + \xi_{T_0+1} + \cdots + \xi_T \geq C\ln T$, by definition of $T_0$. We bound the probability that this happens for fixed $T_0$ and take a union bound.)


As for $\mathbb{E}(S_T)$, since you have a stationary distribution, then your chain is positive recurrent (see Chapter 21 of Markov Chains and Mixing Times). Your chain is not ergodic due to a parity issue, so let's consider the square of your chain (moving two steps at once). The square decomposes into two separate chains. The one of the even integers looks as follows:

  • At $0$, stay at $0$ with probability $p$, and transition to $2$ with probability $1-p$.
  • At $2n>0$, transition to $2(n-1)$ with probability $p^2$, stay at $2n$ with probability $2p(1-p)$, and transition to $2(n+1)$ with probability $(1-p)^2$.

The one on the odd integers looks as follows:

  • At $1$, stay at $1$ with probability $p(2-p)$, and transition to $3$ with probability $(1-p)^2$.
  • At $2n+1$, transition to $2(n-1)+1$ with probability $p^2$, stay at $2n+1$ with probability $2p(1-p)$, and transition to $2(n+1)+1$ with probability $(1-p)^2$.

Let's focus on the case of even integers. Let $f_{2n} = cn$. Using $p(i,j)$ for the probability to transition from $i$ to $j$,

\begin{align} &p(0,0) e^{f_0 - f_0} + p(0,2) e^{f_2 - f_0} = p + (1-p) e^{-c}, \\ &p(2n,2n-2) e^{f_{2n-2} - f_{2n}} + p(2n,2n) e^{f_{2n} - f_{2n}} + p(2n,2n+2) e^{f_{2n+2} - f_{2n}} = p^2 e^{-c} + 2p(1-p) + (1-p)^2 e^c. \end{align} For any $c > 1$, the first line is strictly less than 1. For $c = 1+\epsilon$, the second line is $$ p^2 (1 - \epsilon) + 2p(1-p) + (1-p)^2 (1 + \epsilon) + O(\epsilon^2), $$ which is less than 1 for any small $\epsilon>0$ since $p^2 > (1-p)^2$.

We have thus verified Popov's conditions for geometric ergodicity (see for example Isaacson), and we conclude1 that there exists $\beta < 1$ such that $$ \left|\Pr[S_{2T} = 2n \mid S_0 = 0] - \pi^e_{2n}\right| = O(e^{f_0-f_{2n}}\beta^T) = O(\beta^T), $$ where $\pi^e$ is the stationary distribution of the even component of the squared chain, given by $\pi^e_{2n} = 2\pi_{2n}$. Denoting the corresponding expectation by $E^e = \mathbb{E}(\pi^e)$, we conclude that $$ |\mathbb{E}(S_{2T} \mid S_0 = 0) - E^e| = O(\beta^T). $$ Similarly, $$ |\mathbb{E}(S_{2T+1} \mid S_0 = 0) - E^o| = O(\beta^T). $$ We obtain similar results for any other fixed starting point.

1This equation appears in Popov's paper but not in Isaacson's.

$\endgroup$
2
  • $\begingroup$ Thanks! The main observation, which I somehow missed, was that to reach $C\ln T$ we must have a sequence that doesn’t return to zero. Regarding the expected value: can you hint something about the rate of convergence? Or an upper bound for a given $T$? $\endgroup$
    – omerbp
    May 16 at 6:40
  • $\begingroup$ It seems to be exponential. $\endgroup$ May 16 at 22:56

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.