Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Consider the random walk where $X_t=\sum_{i=1}^t Y_i$, $Y_i$s are iid and take $\pm$1 with probabilities $p$ and $1-p$ respectively, where $0<p<0.5$. Define stopping time $\tau_k=\min\left\{t:X_t=k\right\}$. Suppose we know $P(\tau_1<\infty)=\frac{p}{1-p}=q$, is there a way to argue $P(\tau_k<\infty)=q^k$?

I tried to use an inductive argument. Suppose $P(\tau_{k-1}<\infty)=q^{k-1}$, $$P(\tau_k<\infty)=P(\tau_k<\infty\mid \tau_{k-1}<\infty)P(\tau_{k-1}<\infty)+P(\tau_k<\infty\mid \tau_{k-1}=\infty)P(\tau_{k-1}=\infty)$$

The second of the probabilities is zero, and I only need to argue $P(\tau_k<\infty\mid \tau_{k-1}<\infty)=q$. I can intuitively see a regeneration basis for this, but is there a clear way to argue this? Also is there a cleaner way to proceed with this proof?

share|cite|improve this question
For $p = \frac 23$, we get $q = \frac p{1-p} = \frac{2 \cdot 3}{3 \cdot 1} = 2$?! – martini Jun 8 '13 at 11:44
@martini: Thanks, I missed out $0<p<0.5$. – Bravo Jun 8 '13 at 11:50

Let $k \in \mathbb{N}$. Denote by $$Z_s := X_{s+\tau_k}-X_{\tau_k} \qquad (s \in \mathbb{N}_0)$$ the restarted random walk. Then $\tau_k$ is independent of $(Z_s)_{s \geq 0}$. This is intuitively clear, for a proof see below. Now note that

$$\begin{align*} \tau_{k+1} &= \tau_k + \min \{t-\tau_k; X_{(t-\tau_k)+\tau_k} - X_{\tau_k} = 1\} \\ &= \tau_k + \underbrace{\min\{s \geq 0; Z_s=1\}}_{=:\sigma_1} \end{align*}$$

Since $\tau_k$ is independent of $(Z_s)_{s \geq 0}$, we see that $\tau_k$ and $\sigma_1$ are also independent. Moreover, the increments $Y_j$ are supposed to be identically distributed, so $\sigma_1 \sim \tau_1$. Thus,

$$\mathbb{P}(\tau_{k+1}<\infty) = \mathbb{P}(\tau_k < \infty, \sigma_1 < \infty) = \mathbb{P}(\tau_k<\infty) \cdot \underbrace{\mathbb{P}(\sigma_1<\infty)}_{\mathbb{P}(\tau_1<\infty)}.$$

By induction,

$$\mathbb{P}(\tau_{k+1}<\infty) = q^k \cdot q = q^{k+1}$$

$\tau_k$ and $(Z_s)_{s \geq 0}$ are independent:

$$\begin{align*} \mathbb{E} \exp \left(\imath \, \xi \cdot \tau_k + \imath \sum_{j=0}^n \eta_j \cdot Z_{s_j} \right) &= \sum_{m \geq 1} e^{\imath \, \xi \cdot m} \cdot \mathbb{E} \bigg( \underbrace{1_{[\tau_k=m]}}_{\in \mathcal{F}_m} \cdot \underbrace{\exp \bigg(\imath \sum_{j=0}^n \eta_j \cdot \underbrace{(X_{s_j+m}-X_m)}_{\sim X_{s_j}} \bigg)}_{\text{independent of} \, \mathcal{F}_m} \bigg) \\ &= \mathbb{E}e^{\imath \, \xi \cdot \tau_k} \cdot \mathbb{E}\exp \left(\imath \, \sum_{j=0}^n \eta_j \cdot X_{s_j} \right) \end{align*}$$ where $\xi, \eta_j \in \mathbb{R}$, $s_j \in \mathbb{N}_0$ and $\mathcal{F}_m := \sigma(X_1,\ldots,X_m)$ denotes the canonical filtration. For $\xi=0$ this shows that the finite dimensional distributions of $X$ and $Z$ coincide. Hence,

$$\begin{align*} \mathbb{E} \exp \left(\imath \, \xi \cdot \tau_k + \imath \sum_{j=0}^n \eta_j \cdot Z_{s_j} \right)&= \mathbb{E}e^{\imath \, \xi \cdot \tau_k} \cdot \mathbb{E}\exp \left(\imath \, \sum_{j=0}^n \eta_j \cdot Z_{s_j} \right) \end{align*}$$

which implies that $\tau_k$ and $(Z_s)_{s \geq 0}$ are independent, see here.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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