How can I show that $P(S_n \ge 0 \mid T_0 = k) = 1/2?$ I understand it intuitively, but I get lost with notation.

51 Views Asked by At

Edit: $S_n$ is the state of the random walker (for a simple symmetric random walk) for $n \in \{1, 2, \ldots, k\}$. $T_0$ is the time taken for the random walker to return to state $0$ for the first time.

I want to show that $P(S_n \ge 0 \mid T_0 = k) = 1/2, n \in \{1,2, \ldots,k\} $ i.e. show that 1/2 is the probability that the path taken exclusively goes through positive states before returning to $0$ (regardless of my starting position). Intuitively, this seems obvious because until I've returned to and crossed $0$ at some time step $k$, the path of states from time step $n$ to time step $k$ must consist of states that are all either positive or negative. This is true because the only way a path can include both positive and negative states is if the path crosses $0$, and I'm specifically interested in the path created up until I've crossed $0$, i.e. excluding the case of crossing over. Accordingly, the path pursued depends on whether I move forward or backward at $n = 1$. In a symmetric simple random walk, the probability of moving forward is equal to that of moving backward i.e. $p = q = 1/2$.

My current idea is to say that $P(S_n \ge 0 \mid T_0 = k) = P(S_n >= 0, n\in\{1,2,\ldots, k\}| S_k = 0) = P(S_{n\neq{k}} > 0 \mid S_k = 0)$. I have no idea where to take the notation from this point to express the ideas mentioned above.

1

There are 1 best solutions below

1
On

Personally, I think your paragraph explanation is a better proof than a symbolic argument will be! But if you want to push symbols, your paragraph is a good guide for how to proceed.

First, notice that

$$\mathbb P(S_n \geq 0 \text{ for all } 0 < n < k \mid T_0 = k) \color{blue}{\neq} \mathbb P(S_n \geq 0 \text{ for all } 0 < n < k \mid S_n = 0).$$ You're not conditioning on the correct thing on the right-hand side; you're conditioning only on $S_n$ returning to $0$ at time $n$, not that it's the first such return. Instead, consider proceeding with the definition of conditional probability:

\begin{align*}\mathbb P(S_n \geq 0 \text{ for all } 0 < n < k \mid T_0 = k) &= \frac{\mathbb P(S_n \geq 0 \text{ for all } 0 < n < k \text{ and } T_0 = k)}{\mathbb P(T_0 = k)} \\ &= \frac{\mathbb P(S_1 > 0, \dots, S_{k-1} > 0, S_k = 0)}{\mathbb P(T_0 = k)} \end{align*}

Then, you could argue that $\{T_0 = k\}$ is the disjoint union of two events: $\{S_1 > 0, \dots, S_{k-1} > 0, S_k = 0\}$, and $\{S_1 < 0, \dots, S_{k-1} < 0, S_k = 0\}$. Do you see where to go from here?