Undergrad Martingale, Optional sampling theorem

[WMDhamnekar]

In this exercise, we consider simple, nonsymmetric random walk. Suppose 1/2 < q < 1 and $X_1, X_2, \dots$ are independent random variables with $\mathbb{P}\{X_j = 1\} = 1 − \mathbb{P}\{X_j = −1\} = q.$ Let $S_0 = 0$ and $S_n = X_1 +\dots +X_n.$ Let $F_n$ denote the information contained in $X_1, \dots , X_n$
1. Which of these is $S_n$: martingale, submartingale, supermartingale (more than one answer is possible)?

2. For which values of r is $M_n = S_n − rn$ a martingale?

3. Let $\theta = (1 − q)/q$ and let $M_n =\theta^{S_n}$ . Show that $M_n$ is a martingale.

4. Let a, b be positive integers, and $T_{a,b} = \min\{j : S_j = b \text{or} S_j = −a\}.$ Use the optional sampling theorem to determine $\mathbb{P}\{ S_{T_{a,b} }= b\}$ .

5. Let $T_a = T_{a,\infty}.$ Find $\mathbb{P}\{T_a < \infty\}$

My answers:

1. $S_n$ is a submartingale. This is because $E[S_{n+1} | F_n] \geq qS_n + (1 − q)S_n = S_n$, and $S_n$ is increasing in n.

2. $M_n$ is a martingale if and only if r = 0. This is because $E[M_{n+1} | F_n] = E[S_{n+1} − r(n+1)| F_n] =(S_n - rn) = q(S_n − rn) + (1 − q)(S_n − rn) = S_n − rn$, so $r = 0$ is required for $M_n$ to be a martingale.

3. We have $E[\theta^{S_{n+1}} | F_n] = \theta^{qS_n + (1 − q)S_n} = \theta^{S_n} = M_n$, so $M_n$ is a martingale.

4. Using the optional sampling theorem and the fact that $S_j$ is likely to increase by 1 in each step with $\mathbb{P}[\frac12 < q < 1]$, we have $\mathbb{P}\{ S_{T_{a,b}} = b\} = q^a$.

5. Since $S_n$ is a submartingale, $T_a < \infty$ is unsure. $T_a$ is the stopping time where $n$ is the first time $S_n$ reaches −a, so $\mathbb{P}\{T_a < \infty\} = 0 \leq p <q$ where (p +q)=1

 

[Office_Shredder]

If $M_n$ is a Martingale when $r=0$, wouldn't that make $S_n$ a martingale for #1?

 

[WMDhamnekar]

If $M_n$ is a Martingale when $r=0$, wouldn't that make $S_n$ a martingale for #1?

In this case, $M_n = S_n - rn$ is a martingale if $r = \mathbb{E}[X_1]$. Since $\mathbb{P}\{X_1 = 1\} = q$ and $\mathbb{P}\{X_1 = -1\} = 1-q$, we have $\mathbb{E}[X_1] = 2q-1$. Therefore, $M_n$ is a martingale if $r=2q-1$.
Credit goes to microsoft new bing Chat generative pre-training transformer.

 

[WMDhamnekar]

My answer to 4 is wrong. Correct answer is $(q)^b$ where 1/2 < q < 1 as given in the question.
But if p = q = 1/2, then the answer is
This is a problem in probability theory involving a random walk. The optional stopping theorem can be used to determine the probability that the random walk reaches b before reaching $-a$. Let $p = \mathbb{P}\{S_{T_{a,b}} = b\}$ and note that $\mathbb{E}[S_{T_{a,b}}] = pb + (1-p)(-a)$. By the optional stopping theorem applied to the martingale $S_n$, we have $\mathbb{E}[S_{T_{a,b}}] = \mathbb{E}[S_0] = 0$. Solving for p gives us $p = \frac{a}{a+b}$.

So, the probability that the random walk reaches b before reaching -a is $\frac{a}{a+b}$.

 

[Office_Shredder]

I find it hard to believe that if $q=0.5$ you get $a/(a+b)$ and if $q=0.500001$ you get $(.500001)^b$, which are very different numbers for lots of choices of $a$ and $b$ (e.g. $a=b=10$)

Shouldn't the answer to 4 depend on both a and b at least?

 

[WMDhamnekar]

I find it hard to believe that if $q=0.5$ you get $a/(a+b)$ and if $q=0.500001$ you get $(.500001)^b$, which are very different numbers for lots of choices of $a$ and $b$ (e.g. $a=b=10$)

Shouldn't the answer to 4 depend on both a and b at least?

Can you prove answer to 4 depends upon a and b ?

 

[Office_Shredder]

Can you prove answer to 4 depends upon a and b ?

I just feel like, "does it hit a or b first" obviously depends on a? If a=1 and b=100 the odds you hit a first are decent, if a=1,000,000 and b=100 the odds you hit a first are infinitesimal.