# Martingale, Optional sampling theorem

• I
WMDhamnekar
MHB
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\}##

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

Last edited:

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

WMDhamnekar
WMDhamnekar
MHB
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
MHB
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}##.

Last edited:
Staff Emeritus
Gold Member
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
MHB
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 ?🤔🤔

Staff Emeritus