Math Problems Vault

Problem 5.19 from Gallager R.G. "Stochastic Processes: Theory for Applications" [Gal13]More problems in Chapter 5 "Renewal processes"

(a)(b)(c)(d)

Let $J = \min \left\{ n \mid S_{n} \leq b \text{ or } S_{n} \geq a\right\}$ , where $a$ is a positive integer, $b$ is a negative integer, and $S_{n} = X_{1}+X_{2}+\cdots +X_{n}$ . Assume that $\left\{ X_{i}; i \geq 1\right\}$ is a set of zero-mean IID rv s that can take on only the set of values $\left\{ -1, 0, +1\right\}$ , each with positive probability.

?

(a)

Is $J$ a stopping rule? Why or why not?

(b)

What are the possible values of $S_{J}$ ?

(c)

Find an expression for $\mathbb {E}\left[S_{J}\right]$ in terms of $p$ , $a$ , and $b$ , where $p = \mathbb {P}\left(S_{J} \geq a\right)$ .

(d)

Find an expression for $\mathbb {E}\left[S_{J}\right]$ from Wald's equality. Use this to solve for $p$ .

Problem 9.14 from Gallager R.G. "Stochastic Processes: Theory for Applications" [Gal13]More problems in Chapter 9 "Random walks, large deviations, and martingales"

(a)(b)

Consider a random walk with thresholds $\alpha > 0$ , $\beta < 0$ . We wish to find $\mathbb {P}\left(S_{J} \geq \alpha \right)$ in the absence of a lower threshold. Use the upper bound $\mathbb {P}\left(S_{J} \geq \alpha \right) \leq \exp (-r^{*}\alpha )$ (eq. (9.46), Corollary 9.4.4) for the probability that the random walk crosses $\alpha$ before $\beta$ .

?

(a)

Given that the random walk crosses $\beta$ first, find an upper bound to the probability that $\alpha$ is crossed before a yet lower threshold at $2\beta$ is crossed.

(b)

Given that $2\beta$ is crossed before $\alpha$ , upper bound the probability that $\alpha$ is crossed before a threshold at $3\beta$ . Extending this argument to successively lower thresholds, find an upper bound to each successive term, and find an upper bound on the overall probability that $\alpha$ is crossed. By observing that $\beta$ is arbitrary, show that (9.46) is valid with no lower threshold.

Problem 9.15 from Gallager R.G. "Stochastic Processes: Theory for Applications" [Gal13]More problems in Chapter 9 "Random walks, large deviations, and martingales"

(a)(b)(c)

This exercise verifies that Corollary 9.4.4 holds in the situation where $\gamma (r_{+}) < 0$ . We have defined $r^{*} = r_{+}$ in this case.

?

(a)

Use the Wald identity at $r = r_{+}$ to show that

\mathbb {P}\left(S_{J} \geq \alpha \right)\mathbb {E}\left[\exp (r_{+}S_{J} - J\gamma (r_{+})) \mid S_{J} \geq \alpha \right] \leq 1.

(b)

Show that

\mathbb {P}\left(S_{J} \geq \alpha \right)\exp \left[r_{+}\alpha - \gamma (r_{+})\right] \leq 1.

(c)

Show that

\mathbb {P}\left(S_{J} \geq \alpha \right) \leq \exp \left[-r_{+}\alpha + \gamma (r_{+})\right] \qquad \text{and} \qquad \mathbb {P}\left(S_{J} \geq \alpha \right) \leq \exp \left[-r^{*}\alpha \right].

Remark.

?

Note that the first bound above is a little stronger than the second, and note that lower bounding $J$ by $1$ is not necessarily a very weak bound, since this is the case where if $\alpha$ is crossed, it tends to be crossed for small $J$ .

Problem 9.16 from Gallager R.G. "Stochastic Processes: Theory for Applications" [Gal13]More problems in Chapter 9 "Random walks, large deviations, and martingales"

(a)(b)(c)(d)

?

(a)

Use Wald's equality to show that if $\overline{X} = 0$ , then $\mathbb {E}\left[S_{J}\right] = 0$ , where $J$ is the time of threshold crossing with one threshold at $\alpha > 0$ and another at $\beta < 0$ .

(b)

Obtain an expression for $\mathbb {P}\left(S_{J} \geq \alpha \right)$ . Your expression should involve the expected value of $S_{J}$ conditional on crossing the individual thresholds (you need not try to calculate these expected values).

(c)

Evaluate your expression for the case of a simple random walk.

(d)

Evaluate your expression when $X$ has an exponential density, $\mathsf{f}_{X}(x) = a_{1}e^{-\lambda x}$ for $x \geq 0$ and $\mathsf{f}_{X}(x) = a_{2}e^{\mu x}$ for $x < 0$ and where $a_{1}$ and $a_{2}$ are chosen so that $\overline{X} = 0$ .

Problem 9.17 from Gallager R.G. "Stochastic Processes: Theory for Applications" [Gal13]More problems in Chapter 9 "Random walks, large deviations, and martingales"

(a)(b)(c)

A random walk $\left\{ S_{n}; n \geq 1\right\}$ , with $S_{n} = \sum_{i=1}^{n} X_{i}$ , has the following probability density for $X_{i}$ :

\mathsf{f}_{X}(x) = \begin{cases} \dfrac {e^{-x}}{e - e^{-1}}, & -1 \leq x \leq 1, \\ 0, & \text{elsewhere.} \end{cases}

?

(a)

Find the values of $r$ for which $\mathsf{g}(r) = \mathbb {E}\left[\exp (rX)\right] = 1$ .

(b)

Let $P_{\alpha }$ be the probability that the random walk ever crosses a threshold at $\alpha$ for some $\alpha > 0$ . Find an upper bound to $P_{\alpha }$ of the form $P_{\alpha } \leq e^{-\alpha A}$ , where $A$ is a constant that does not depend on $\alpha$ ; evaluate $A$ .

(c)

Find a lower bound to $P_{\alpha }$ of the form $P_{\alpha } \geq Be^{-\alpha A}$ , where $A$ is the same as in (b) and $B$ is a constant that does not depend on $\alpha$ .

Problem 9.18 from Gallager R.G. "Stochastic Processes: Theory for Applications" [Gal13]More problems in Chapter 9 "Random walks, large deviations, and martingales"

(a)(b)(c)

Let $\left\{ X_{n}; n \geq 1\right\}$ be a sequence of IID integer-valued rv s with the PMF $\mathsf{p}_{X}(k) = Q_{k}$ . Assume that $Q_{k} > 0$ for $\left|k\right| \leq 10$ and $Q_{k} = 0$ for $\left|k\right| > 10$ . Let $\left\{ S_{n}; n \geq 1\right\}$ be a random walk with $S_{n} = X_{1} + \cdots + X_{n}$ . Let $\alpha > 0$ and $\beta < 0$ be integer-valued thresholds, let $J$ be the smallest value of $n$ for which either $S_{n} \geq \alpha$ or $S_{n} \leq \beta$ . Let $\left\{ S_{n}^{*}; n \geq 1\right\}$ be the stopped random walk; i.e., $S_{n}^{*} = S_{n}$ for $n \leq J$ and $S_{n}^{*} = S_{J}$ for $n > J$ . Let $\pi_{i}^{*} = \mathbb {P}\left(S_{J} = i\right)$ .

?

(a)

Consider a Markov chain in which this stopped random walk is run repeatedly until the point of stopping. That is, the Markov chain transition probabilities are given by $P_{ij} = Q_{j-i}$ for $\beta < i < \alpha$ and $P_{i0} = 1$ for $i \leq \beta$ and $i \geq \alpha$ . All other transition probabilities are $0$ and the set of states is the set of integers $[-9+\beta , 9+\alpha ]$ . Show that this Markov chain is ergodic.

(b)

Let $\left\{ \pi_{i}\right\}$ be the set of steady-state probabilities for this Markov chain. Find the set of probabilities $\left\{ \pi_{i}^{*}\right\}$ for the stopping states of the stopped random walk in terms of $\left\{ \pi_{i}\right\}$ .

(c)

Find $\mathbb {E}\left[S_{J}\right]$ and $\mathbb {E}\left[J\right]$ in terms of $\left\{ \pi_{i}\right\}$ .

Problem 9.19 from Gallager R.G. "Stochastic Processes: Theory for Applications" [Gal13]More problems in Chapter 9 "Random walks, large deviations, and martingales"

(a)(b)

Consider the following binary hypothesis testing problem: there are two hypotheses $X=0, X=1$ , and, conditional on each hypothesis, IID observations $Y_{1}, \ldots , Y_{n}$ are drawn with conditional density $\mathsf{f}_{Y|X}(y \mid 0)$ or $\mathsf{f}_{Y|X}(y \mid 1)$ respectively.

?

(a)

Conditional on $X = 0$ for the hypothesis testing problem, consider the rv s $Z_{i} = \ln \left[\mathsf{f}(y_{i} \mid X=1)/\mathsf{f}(y_{i} \mid X=0)\right]$ . Show that $r^{*}$ , the positive solution to $\mathsf{g}(r) = 1$ , where $\mathsf{g}(r) = \mathbb {E}\left[\exp (rZ_{i})\right]$ , is given by $r^{*} = 1$ .

(b)

Assuming that $Y$ is a discrete rv (under each hypothesis), show that the tilted rv $Z_{r}$ with $r = 1$ has the PMF $\mathsf{p}_{Y}(y \mid X=1)$ .

Problem 9.25 from Gallager R.G. "Stochastic Processes: Theory for Applications" [Gal13]More problems in Chapter 9 "Random walks, large deviations, and martingales"

Let $\left\{ Z_{n} = \exp \left(rS_{n} - n\gamma (r)\right); n \geq 1\right\}$ be the generating function martingale of (9.77), where $S_{n} = X_{1} + \cdots + X_{n}$ and $X_{1}, \ldots , X_{n}$ are IID with mean $\overline{X} < 0$ . Let $J$ be the possibly-defective stopping trial for which the process stops after crossing a threshold at $\alpha > 0$ (there is no negative threshold). Show that $\exp \left(r^{*}\alpha \right)$ is an upper bound to the probability of threshold crossing by considering the stopped process $\left\{ Z_{n}^{*}; n \geq 1\right\}$ .

?

Remark.

?

The purpose of this exercise is to illustrate that the stopped process can yield useful upper bounds even when the stopping trial is defective.

Problem 12.9.7 from Grimmett G.R., Stirzaker D.R. "Probability and Random Processes" [GrSt20]More problems in Section 12.9 "Problems"

Let $X_{1}, X_{2}, \ldots$ be independent identically distributed random variables and suppose that $M(t) = \mathbb {E}\left[e^{t X_{1}}\right]$ satisfies $M(t) = 1$ for some $t > 0$ . Show that $\mathbb {P}\left(S_{k} \geq x \text{ for some } k\right) \leq e^{-t x}$ for $x > 0$ and such a value of $t$ , where $S_{k} = X_{1}+X_{2}+\cdots +X_{k}$ .

?

Wald's Identity for Threshold Crossings

References