2

Let $$S_n^* = \max_{1\leq m \leq n}S_m$$

$S_0 = 0$. Assume that $n$ and $a$ are even positive integers, $b$ is an even integer $b\leq a$, $a \leq n$, $ 2a - b \leq n$.

Prove that $P(S_n^*\geq a, S_n=b)=P(S_n=2a-b)={n\choose ({n+b})/2-a}(1/2)^n$

2) also find $P(S_n^*\leq a, S_n=b)$

Once I can prove $P(S_n^*\geq a, S_n=b)=P(S_n=2a-b)$ its easy to prove the next result, however I am having difficulty visualizing this result using reflection principle. Also, the second one should be easy once i get this concept. Can some one please help?

Teddy38
  • 3,309
Raveesh
  • 135

2 Answers2

4

Let's review the reflection principle.

Set $\tau_a = \inf \{n: S_n \ge a\}$. Observe $$ \{S_n^*\ge a,S_n=b\}=\{\tau_a \le n,S_n =b\}.$$ Now: $$P( \tau_a \le n, S_n = b ) = \sum_{k\le n} P(S_n=b,\tau_a =k).$$

By strong Markov property and symmetry of walk (this is the reflection part):

$$P(S_n = b | \tau_a=k) = P(S_{n-k} = b-a)= P(S_{n-k}=|b-a|).$$

This gives

$$P(S_n = b, \tau_a = k) = P(S_{n-k} = |b-a|)P(\tau_a = k)=P(S_n - S_k =|b-a|)P(\tau_a = k).$$

Note that the events on RHS are independent, so it is equal to

$$P(S_n -S_k =|b-a|,\tau_a =k) =P(S_n =a+|b-a|,\tau_a=k).$$

Since $a+|b-a|\ge a$, it follows that $\{S_n = a+|b-a|\}\subset \{\tau_a \le n\}$. This gives:

$$P(S^*_n \ge a,S_n =b)=\sum_{k\le n}P(S_n =a+|b-a|,\tau_a=k) =P(S_n = a+|b-a|),$$

which is the formula for the reflection principle (the reflection is about $a$: probability of being at $a+(b-a)=b$ and at $a-(b-a)=2a-b$ is the same).

For the second part, use the first part:

\begin{align*} P(S^*_n \le a,S_n =b) &= P(S_n =b) - P(S^*_n \ge a-1,S_n =b)\\ &=P(S_n =b) -P(S_n = a-1+|b-a+1|). \end{align*}

Fnacool
  • 7,519
  • How do you make the move $S_{n-k}=S_n-S_k$, inside the probability? – Dole Nov 04 '18 at 14:03
  • 1
    Left side is where walker after $n-k$ steps, if starting from zero. Right side is the increment between the $k$-th step and the $n$-th step, that is what the random walk does in $n-k$ steps. – Fnacool Nov 05 '18 at 23:54
2

If $S_n^\star \ge a$, you need to reflect the random walk the first time you hit $a$. Now $S_n$ will hit $b$ if you go down $a - b$ steps after the first time you hit $a$, this is equivalent to asking that the reflected walk goes up $a - b$ times, i.e. $S_n = a + a - b = 2a - b$.

Dominik
  • 19,963
  • thanks so much, so in the next example i will have to reflect anything that is less than a, in that case $S_n = a+b $ ? – Raveesh Nov 15 '16 at 15:20