Math Problems Vault

Problem 9.1

Consider the simple random walk $\{ S_{n}; n \geq 1\}$ with $S_{n} = X_{1}+\cdots +X_{n}$ and $\mathbb {P}\left(X_{i} = 1\right) = p$ , $\mathbb {P}\left(X_{i} = -1\right) = 1-p$ ; assume that $p \leq 1/2$ .

?

(a)

Show that $\mathbb {P}\left(\bigcup_{n \geq 1} \left\{ S_{n} \geq k\right\} \right) = \left[\mathbb {P}\left(\bigcup_{n \geq 1} \left\{ S_{n} \geq 1\right\} \right)\right]^{k}$ for any positive integer $k$ .

(b)

Find a quadratic equation for $y = \mathbb {P}\left(\bigcup_{n \geq 1} \left\{ S_{n} \geq 1\right\} \right)$ .

(c)

For $p<1/2$ , show that the two roots of this quadratic equation are $p/(1-p)$ and $1$ . Argue that $\mathbb {P}\left(\bigcup_{n \geq 1} \left\{ S_{n} \geq 1\right\} \right)$ cannot be $1$ and thus must be $p/(1-p)$ .

(d)

For $p = 1/2$ , show that the quadratic equation in (c) has a double root at $1$ , and thus $\mathbb {P}\left(\bigcup_{n \geq 1} \left\{ S_{n} \geq 1\right\} \right) = 1$ .

(e)

Let $r^{*}$ be the unique positive root of $\mathsf{g}(r) = 1$ where $\mathsf{g}(r) = \mathbb {E}\left[e^{rX}\right]$ . Show that $p/(1-p) = \exp (-r^{*})$ .

Problem 9.2

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

Consider a G/G/1 queue with IID arrivals $\{ X_{i}; i \geq 1\}$ , IID FCFS service times $\{ Y_{i}; i \geq 0\}$ , and an initial arrival to an empty system at time $0$ . Define $U_{i} = X_{i}-Y_{i-1}$ for $i \geq 1$ . Consider a sample path where $(u_{1}, \ldots , u_{6}) = (1, -2, 2, -1, 3, -2)$ .

?

(a)

Let $Z_{i}^{6} = U_{6}+U_{6-1}+\cdots +U_{6-i+1}$ . Find the queueing delay for customer $6$ as the maximum of the `backward' random walk with elements $0, Z_{1}^{6}, Z_{2}^{6}, \ldots , Z_{6}^{6}$ ; sketch this random walk.

(b)

Find the queueing delay for customers $1$ to $5$ .

(c)

Which customers start a busy period (i.e., arrive when the queue and server are both empty)? Verify that if $Z_{i}^{6}$ maximizes the random walk in (a), then a busy period starts with arrival $6-i$ .

(d)

Now consider a forward random walk $V_{n} = U_{1}+\cdots +U_{n}$ . Sketch this walk for the sample path above and show that the queueing delay for each customer is the difference between two appropriately chosen values of this walk.

Problem 9.3

(a)(b)(c)

A G/G/1 queue has a deterministic service time of $2$ and interarrival times that are $3$ with probability $p<1/2$ and $1$ with probability $1-p$ .

?

(a)

Find the distribution of $W_{1}$ , the wait in queue of the first arrival after the beginning of a busy period.

(b)

Find the distribution of $W_{\infty }$ , the steady-state wait in queue.

(c)

Repeat (a) and (b) assuming the service times and interarrival times are exponentially distributed with rates $\mu$ and $\lambda$ respectively.

Problem 9.4

Let $U = V_{1}+\cdots +V_{n}$ , where $V_{1}, \ldots , V_{n}$ are IID rv s with the MGF $\mathsf{g}_{V}(s)$ . Show that $\mathsf{g}_{U}(s) = \left[\mathsf{g}_{V}(s)\right]^{n}$ .

?

Problem 9.5

(a)(b)(c)

Let $\{ a_{n}; n \geq 1\}$ and $\{ \alpha_{n}; n \geq 1\}$ be sequences of numbers. For some $b$ , assume that $a_{n} \leq \alpha_{n} e^{-bn}$ for all $n \geq 1$ . For each of the following choices for $\alpha_{n}$ and arbitrary $b$ , determine whether the bound is exponentially tight. You may assume $b \geq 0$ if you wish, but it really does not matter.

?

(a)

$\alpha_{n} = \sum_{j=1}^{k} c_{j} n^{-j}$ .

(b)

$\alpha_{n} = \exp (-\sqrt{n})$ .

(c)

$\alpha_{n} = e^{-n^{2}}$ .

What you are intended to learn from this is that an exponentially tight bound is not necessarily a reasonable approximation for large $n$ . It is intended for sequences that are essentially exponentially decreasing in $n$ and where one is satisfied with knowing the exponent without concern for the non-exponential coefficients.

Problem 9.6

Define $\gamma (r)$ as $\ln \left[\mathsf{g}(r)\right]$ , where $\mathsf{g}(r) = \mathbb {E}\left[\exp (rX)\right]$ . Assume that $X$ is discrete with possible outcomes $\{ a_{i}; i \geq 1\}$ , let $p_{i}$ denote $\mathbb {P}\left(X=a_{i}\right)$ , and assume that $\mathsf{g}(r)$ exists in some open interval $(r_{-}, r_{+})$ containing $r=0$ . For any given $r$ , $r_{-}<r<r_{+}$ , define a rv $X_{r}$ with the same set of possible outcomes $\{ a_{i}; i \geq 1\}$ as $X$ , but with a PMF $q_{i} = \mathbb {P}\left(X_{r}=a_{i}\right) = p_{i} \exp \left[a_{i} r-\gamma (r)\right]$ . Note that $X_{r}$ is not a function of $X$ , and is not even to be viewed as in the same probability space as $X$ ; it is of interest simply because of the behavior of its defined probability mass function. It is called a tilted rv relative to $X$ , and this exercise, along with Exercise 9.11, will justify our interest in it.

?

(a)

Verify that $\sum_{i} q_{i} = 1$ .

(b)

Verify that $\mathbb {E}\left[X_{r}\right] = \sum_{i} a_{i} q_{i}$ is equal to $\gamma '(r)$ .

(c)

Verify that $\operatorname {Var}\left[X_{r}\right] = \sum_{i} a_{i}^{2} q_{i}-(\mathbb {E}\left[X_{r}\right])^{2}$ is equal to $\gamma ''(r)$ .

(d)

Argue that $\gamma ''(r) \geq 0$ for all $r$ such that $\mathsf{g}(r)$ exists, and that $\gamma ''(r)>0$ if $\gamma ''(0)>0$ .

(e)

Give a similar definition of $X_{r}$ for a rv $X$ with a density, and modify (a)--(d) accordingly.

Problem 9.7

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

?

(a)

Suppose $Z$ is uniformly distributed over $[-b, +b]$ . Find $\mathsf{g}_{Z}(r)$ , $\mathsf{g}_{Z}'(r)$ , and $\gamma '(r)$ as a function of $r$ .

(b)

Show that the interval over which $\mathsf{g}_{Z}(r)$ exists is the real line, i.e., $r_{+}=\infty$ and $r_{-}=-\infty$ . Show that $\lim_{r \rightarrow \infty } \gamma '(r) = b$ .

(c)

Show that if $a>b$ , then $\inf_{r \in I(X)} \gamma (r)-ra = -\infty$ , so that the optimized Chernoff bound says that $\mathbb {P}\left(S_{n}>na\right) = 0$ . Explain without any mathematics why $\mathbb {P}\left(S_{n}>na\right)=0$ must be valid. Explain (with as little mathematical verbiage as possible) why an infimum rather than a minimum must be used in the optimized Chernoff bound.

(d)

Show that for an arbitrary rv $X$ if $r_{+}=\infty$ and $\lim_{r \rightarrow \infty } \gamma '(r) = b$ , then the optimized Chernoff bound says that $\mathbb {P}\left(S_{n}>na\right)=0$ for $a>b$ .

Problem 9.8

Note that the MGF of the non-negative exponential rv with density $e^{-x}$ is $(1-r)^{-1}$ for $r<r_{+}=1$ . It can be seen from this that $\mathsf{g}(r_{+})$ does not exist (i.e., it is infinite) and both $\lim_{r \rightarrow r_{+}} \mathsf{g}(r) = \infty$ and $\lim_{r \rightarrow r_{+}} \mathsf{g}'(r) = \infty$ , where the limit is over $r<r_{+}$ . In this exercise, you are first to assume an arbitrary rv $X$ for which $r_{+}<\infty$ and $\mathsf{g}(r_{+}) = \infty$ and show that both $\lim_{r \rightarrow r_{+}} \mathsf{g}(r) = \infty$ and $\lim_{r \rightarrow r_{+}} \mathsf{g}'(r) = \infty$ . You will then use this to show that if $\sup_{r<r_{+}} \mathsf{g}'(r)<\infty$ , then $\gamma (r_{+})<\infty$ and the optimized Chernoff exponent $\mu (a)$ is given by $\mu (a) = \gamma (r_{+})-r_{+} a$ for $a>\sup_{r<r_{+}} \gamma '(r)$ .

?

(a)

For $X$ such that $r_{+}<\infty$ and $\mathsf{g}(r_{+})=\infty$ , explain why

\lim _{A \rightarrow \infty } \int _{0}^{A} e^{x r_{+}} \, d\mathsf{F}(x) = \infty .

(b)

Show that for any $\epsilon >0$ and any $A>0$ ,

\mathsf{g}(r_{+}-\epsilon ) \geq e^{-\epsilon A} \int _{0}^{A} e^{x r_{+}} \, d\mathsf{F}(x).

(c)

Choose $A=1/\epsilon$ and show that

\lim _{\epsilon \rightarrow 0} \mathsf{g}(r_{+}-\epsilon ) = \infty .

(d)

Show that $\lim_{\epsilon \rightarrow 0} \mathsf{g}'(r_{+}-\epsilon ) = \infty$ .

(e)

Use (a)--(d) to show that if $r_{+}<\infty$ and $\sup_{r<r_{+}} \mathsf{g}'(r)<\infty$ , then $\mathsf{g}(r_{+})<\infty$ .

(f)

Show that if $r_{+}<\infty$ and $\sup_{r<r_{+}} \mathsf{g}'(r)<\infty$ , then $\mu (a) = \gamma (r_{+})-r_{+} a$ for $a>\sup_{r<r_{+}} \gamma '(r)$ .

Problem 9.9

(a)(b)(c)

?

(a)

Show that the two appearances of $\epsilon$ in the exponential lower bound established in the text for $\mathbb {P}\left(S_{n} \geq n \gamma '(r)\right)$ can be replaced with two independent arbitrary positive quantities $\epsilon_{1}$ and $\epsilon_{2}$ , getting

\mathbb {P}\left(S_{n} \geq n(\gamma '(r)-\epsilon _{1})\right) \geq (1-\delta ) \exp \left[-n(r \gamma '(r)+r \epsilon _{2}-\gamma (r))\right].

Show that if this equation is valid for $\epsilon_{1}$ and $\epsilon_{2}$ , then it is valid for all larger values of $\epsilon_{1}$ and $\epsilon_{2}$ .

(b)

Show that by increasing the required value of $n_{o}$ such that this equation is valid for all $n \geq n_{o}$ , the factor of $(1-\delta )$ can be eliminated above.

(c)

For any $r \in (0, r_{+})$ , let $\delta_{1}$ be an arbitrary number in $(0, r_{+}-r)$ , let $r_{1} = r+\delta_{1}$ , and let $\epsilon_{1} = \gamma '(r_{1})-\gamma '(r)$ . Show that there is an $m$ such that for all $n \geq m$ ,

\mathbb {P}\left(S_{n} \geq n \gamma '(r)\right) \geq \exp \left\{ -n\left[(r+\delta _{1}) \gamma '(r+\delta _{1})+(r+\delta _{1}) \epsilon _{2}-\gamma (r+\delta _{1})\right]\right\} . \tag {9.164}

Using the continuity of $\gamma$ and its derivatives, show that for any $\epsilon >0$ , there is a $\delta_{1}>0$ so that the right-hand side of (9.164) is greater than or equal to $\exp \left[-n(\gamma '(r)-r \gamma (r)+\epsilon )\right]$ .

Problem 9.10

In this exercise, we show that the optimized Chernoff bound is tight for the third case of the large-deviations exponent (the case $a>\sup_{r<r_{+}} \gamma '(r)$ , with $r_{+}<\infty$ ) as well as the first case. That is, we show that if $r_{+}<\infty$ and $a>\sup_{r<r_{+}} \gamma '(r)$ , then, for any $\epsilon >0$ , $\mathbb {P}\left(S_{n} \geq na\right) \geq \exp \left\{ n\left[\gamma (r_{+})-r_{+} a-\epsilon \right]\right\}$ for all large enough $n$ .

?

(a)

Let $Y_{i}$ be the truncated version of $X_{i}$ , truncated for some given $b$ to $Y_{i}=X_{i}$ for $X_{i} \leq b$ and $Y_{i}=b$ otherwise. Let $W_{n} = Y_{1}+\cdots +Y_{n}$ . Show that $\mathbb {P}\left(S_{n} \geq na\right) \geq \mathbb {P}\left(W_{n} \geq na\right)$ .

(b)

Let $\mathsf{g}_{b}(r)$ be the MGF of $Y$ . Show that $\mathsf{g}_{b}(r)<\infty$ and that $\mathsf{g}_{b}(r)$ is non-decreasing in $b$ for all $r<\infty$ .

(c)

Show that $\lim_{b \rightarrow \infty } \mathsf{g}_{b}(r) = \infty$ for all $r>r_{+}$ and that $\lim_{b \rightarrow \infty } \mathsf{g}_{b}(r) = \mathsf{g}(r)$ for all $r \leq r_{+}$ .

(d)

Let $\gamma_{b}(r) = \ln \mathsf{g}_{b}(r)$ . Show that $\gamma_{b}(r)<\infty$ for all $r<\infty$ . Also show that $\lim_{b \rightarrow \infty } \gamma_{b}(r) = \infty$ for $r>r_{+}$ and $\lim_{b \rightarrow \infty } \gamma_{b}(r) = \gamma (r)$ for $r \leq r_{+}$ .

(e)

Let $\gamma_{b}'(r) = (\partial /\partial r) \gamma_{b}(r)$ and let $\delta >0$ be arbitrary. Show that for all large enough $b$ , $\gamma_{b}'(r_{+}+\delta )>a$ .

(f)

Show that the optimized Chernoff bound for $\mathbb {P}\left(W_{n} \geq na\right)$ is exponentially tight for the values of $b$ in (e). Show that the optimizing $r$ is less than $r_{+}+\delta$ .

(g)

Show that for any $\epsilon >0$ and all sufficiently large $b$ ,

\gamma _{b}(r)-ra \geq \gamma (r)-ra-\epsilon \geq \gamma (r_{+})-r_{+} a-\epsilon \qquad \text{for } 0<r \leq r_{+}.

(h)

Show that for arbitrary $\epsilon >0$ , there exists $\delta >0$ and $b_{o}$ such that

\gamma _{b}(r)-ra \geq \gamma (r_{+})-r_{+} a-\epsilon \qquad \text{for } r_{+}<r<r_{+}+\delta \text{ and } b \geq b_{o}.

(i)

Note that if we put (g), (h) and (d) together, and use the $\delta$ of (h) in (d), then we have shown that the optimized exponent in the Chernoff bound for $\mathbb {P}\left(W_{n} \geq na\right)$ satisfies $\mu_{b}(a) \geq \gamma (r_{+})-r_{+} a-\epsilon$ for sufficiently large $b$ . Show that this means that $\mathbb {P}\left(S_{n} \geq na\right) \geq \gamma (r_{+})-r_{+} a-2 \epsilon$ for sufficiently large $n$ .

Problem 9.11

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

Assume that $X$ is discrete, with possible values $\{ a_{i}; i \geq 1\}$ and probabilities $\mathbb {P}\left(X=a_{i}\right) = p_{i}$ . Let $X_{r}$ be the corresponding tilted rv as defined in Exercise 9.6. Let $S_{n} = X_{1}+\cdots +X_{n}$ be the sum of $n$ IID rv s with the distribution of $X$ , and let $S_{n,r} = X_{1,r}+\cdots +X_{n,r}$ be the sum of $n$ IID tilted rv s with the distribution of $X_{r}$ . Assume that $\overline{X}<0$ and that $r>0$ is such that $\gamma (r)$ exists.

?

(a)

Show that $\mathbb {P}\left(S_{n,r}=s\right) = \mathbb {P}\left(S_{n}=s\right) \exp \left[sr-n \gamma (r)\right]$ .

(b)

Find the mean and variance of $S_{n,r}$ in terms of $\gamma (r)$ .

(c)

Define $a = \gamma '(r)$ and $\sigma_{r}^{2} = \gamma ''(r)$ . Show that $\mathbb {P}\left(\left|S_{n,r}-na\right| \leq \sqrt{2n} \sigma_{r}\right)>1/2$ . Use this to show that

\mathbb {P}\left(\left|S_{n}-na\right| \leq \sqrt{2n} \sigma _{r}\right) > (1/2) \exp \left[-r(an+\sqrt{2n} \sigma _{r})+n \gamma (r)\right].

(d)

Use this to show that for any $\epsilon$ and for all sufficiently large $n$ ,

\mathbb {P}\left(S_{n} \geq n(\gamma '(r)-\epsilon )\right) > \frac{1}{2} \exp \left[-rn(\gamma '(r)+\epsilon )+n \gamma (r)\right].

Problem 9.12

(a)(b)(c)

Let $\overrightarrow {p} = (p_{1}, \ldots , p_{\mathsf{M}})$ and $\overrightarrow {\tilde{p}} = (\tilde{p}_{1}, \ldots , \tilde{p}_{\mathsf{M}})$ be strictly positive probability vectors. The Kullback--Leibler divergence between $\overrightarrow {\tilde{p}}$ and $\overrightarrow {p}$ is defined by

D(\overrightarrow {\tilde{p}} \| \overrightarrow {p}) = \sum _{j} \tilde{p}_{j} \ln \left(\frac{\tilde{p}_{j}}{p_{j}}\right).

?

(a)

Show that the divergence $D(\overrightarrow {\tilde{p}} \| \overrightarrow {p}) \geq 0$ is $0$ if $\overrightarrow {\tilde{p}} = \overrightarrow {p}$ .

(b)

Let $\overrightarrow {u} = u_{1}, \ldots , u_{\mathsf{M}}$ satisfy $\sum_{j} u_{j} = 0$ and show that $\overrightarrow {\tilde{p}} + \epsilon \overrightarrow {u}$ is a probability vector over a sufficiently small region of $\epsilon$ around $0$ . Show that

\frac{\partial }{\partial \epsilon } D(\overrightarrow {\tilde{p}} + \epsilon \overrightarrow {u} \| \overrightarrow {p})\Big|_{\epsilon = 0} = 0.

(c)

Show that

\frac{\partial ^{2}}{\partial \epsilon ^{2}} D(\overrightarrow {\tilde{p}} + \epsilon \overrightarrow {u} \| \overrightarrow {p}) \geq 0,

where $\overrightarrow {\tilde{p}} + \epsilon \overrightarrow {u}$ is a probability vector with non-zero components. Explain why this implies that $D$ is convex in $\overrightarrow {\tilde{p}}$ and non-negative over the region of probability vectors.

Problem 9.13

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

Consider a random walk $\left\{ S_{n}; n \geq 1\right\}$ , where $S_{n} = X_{1} + \cdots + X_{n}$ and $\left\{ X_{i}; i \geq 1\right\}$ is a sequence of IID exponential rv s with the PDF $\mathsf{f}(x) = \lambda e^{-\lambda x}$ for $x \geq 0$ . In other words, the random walk is the sequence of arrival epochs in a Poisson process.

?

(a)

Show that for $\lambda a > 1$ , the optimized Chernoff bound for $\mathbb {P}\left(S_{n} \geq na\right)$ is given by

\mathbb {P}\left(S_{n} \geq na\right) \leq (a \lambda )^{n} e^{-n(a \lambda - 1)}.

(b)

Show that the exact value of $\mathbb {P}\left(S_{n} \geq na\right)$ is given by

\mathbb {P}\left(S_{n} \geq na\right) = \sum _{i=0}^{n-1} \frac{(na \lambda )^{i} e^{-na \lambda }}{i!}.

(c)

By upper and lower bounding the quantity on the right above, show that

\frac{(na \lambda )^{n} e^{-na \lambda }}{n! \, a \lambda } \leq \mathbb {P}\left(S_{n} \geq na\right) \leq \frac{(na \lambda )^{n} e^{-na \lambda }}{n! (a \lambda - 1)}.

(d)

Use the Stirling bounds on $n!$ to show that

\frac{(a \lambda )^{n} e^{-n(a \lambda - 1)}}{\sqrt{2 \pi n} \, a \lambda \exp (1 / 12 n)} \leq \mathbb {P}\left(S_{n} \geq na\right) \leq \frac{(a \lambda )^{n} e^{-n(a \lambda - 1)}}{\sqrt{2 \pi n} \, (a \lambda - 1)}.

Remark.

?

The point of this exercise is to demonstrate that the Chernoff bound is not only exponentially tight for this example but captures the important factors in the behavior of $\mathbb {P}\left(S_{n} \geq na\right)$ .

Problem 9.14

(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

(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

(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

(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

(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

(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.20

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

Recall the bounds from Theorem 9.5.1: for a threshold test at $\eta = e^{n\gamma_{0}(r)}$ ,

\mathbb {P}\left(e(n) \mid X=0\right) \leq \exp \left(n\left[\gamma _{0}(r) - r\gamma _{0}'(r)\right]\right) \tag {9.61}

and

\mathbb {P}\left(e(n) \mid X=1\right) \leq \exp \left(n\left[\gamma _{0}(r) + (1-r)\gamma _{0}'(r)\right]\right), \tag {9.62}

where $\gamma_{0}(r)$ is the semi-invariant MGF of the log-likelihood ratio $Z$ conditional on $X = 0$ .

?

(a)

Use a power series expansion around $r = 0$ to show that $\gamma_{0}(r) - r\gamma_{0}'(r) = -r^{2}\gamma_{0}''(0)/2 + o(r^{2})$ .

(b)

Choose $r = n^{-1/3}$ in (9.61) and (9.62). Show that (9.61) can then be rewritten as

\begin{aligned} \mathbb {P}\left(e(n) \mid X=0\right) & \leq \exp \left\{ n\left[-r^{2}\gamma _{0}''(0)/2 + o(r^{2})\right]\right\} \\ & = \exp \left\{ -n^{1/3}\gamma _{0}''(0)/2 + o(n^{1/3})\right\} . \end{aligned}

Thus $\mathbb {P}\left(e(n) \mid X=0\right)$ approaches $0$ with increasing $n$ exponentially in $n^{1/3}$ .

(c)

Using the same power series expansion for $r$ in (9.62), show that

\begin{aligned} \mathbb {P}\left(e(n) \mid X=1\right) & \leq \exp \left\{ n\left[r^{2}\gamma _{0}''(0)/2 + \gamma _{0}'(0) + o(r)\right]\right\} \\ & = \exp \left\{ n\gamma _{0}'(0) + o(n^{2/3})\right\} . \end{aligned}

Thus $\lim_{n}(1/n)\ln \mathbb {P}\left(e(n) \mid X=1\right) = \gamma_{0}'(0) = \mathbb {E}\left[Z \mid X=0\right]$ .

(d)

Explain why the bound in (9.62) is exponentially tight given that $\mathbb {P}\left(e(n) \mid X=0\right) \rightarrow 0$ as $n \rightarrow \infty$ .

Problem 9.21

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

This illustrates a very different type of sequential decision problem from those of Section 9.5. Alice is looking for a spouse and dates a set of $n$ suitors sequentially, one per week. For simplicity, assume that Alice must make her decision to accept a suitor for marriage immediately after dating that suitor; she cannot come back later to accept a formerly rejected suitor. Her decision must be based only on whether the current suitor is more suitable than all previous suitors. Mathematically, we can view the dating as continuing for all $n$ weeks, but the choice at week $m$ is a stopping rule. Assume that each suitor's suitability is represented by a real number and that all $n$ numbers are different. Alice does not observe the suitability numbers, but only observes at each time $m$ whether suitor $m$ has the highest suitability so far. The suitors are randomly permuted before Alice dates them.

?

(a)

A reasonable algorithm for Alice is to reject the first $k$ suitors (for some $k$ to be optimized later) and then to choose the first suitor $m > k$ that is more suitable than all the previous $m - 1$ suitors. Find the probability $q_{k}$ that Alice chooses the most suitable of all $n$ when she uses this algorithm for given $k$ .

(b)

Approximating $\sum_{i=1}^{j} 1/i$ by $\ln j$ , show that for $n$ and $k$ large

q_{k} \approx \frac{k}{n}\ln (n/k).

Ignoring the constraint that $n$ and $k$ are integers, show that the right-hand side above is maximized at $k/n = e$ and that $\max_{k} q_{k} \approx 1/e$ .

(c)

(Optional) Show that the algorithm of (a), optimized over $k$ , is optimal over all algorithms (given the constraints of the problem). Let $p_{m}$ be the maximum probability of choosing the optimal suitor given that no choice has been made before time $m$ . Show that

p_{m} = \max \left[\frac{1}{n} + \frac{m-1}{m}p_{m+1}, \; p_{m+1}\right];

part of the problem here is understanding exactly what $p_{m}$ means.

(d)

Explain why this is a poor model for choosing a spouse (or for making a best choice in a wide variety of similar problems).

Remark.

?

Note: If no suitor is selected by the algorithm in part (a), it makes no difference whether suitor $n$ is chosen at the end or no suitor is chosen.

Problem 9.22

(a)(b)

?

(a)

Suppose $\left\{ Z_{n}; n \geq 1\right\}$ is a martingale. Verify

\mathbb {E}\left[Z_{n}\right] = \mathbb {E}\left[Z_{1}\right] \quad \text{for } n > 1. \tag {9.83}

(b)

If $\left\{ Z_{n}; n \geq 1\right\}$ is a submartingale, verify

\mathbb {E}\left[Z_{n}\right] \geq \mathbb {E}\left[Z_{i}\right] \quad \text{for all } i, 1 \leq i < n, \tag {9.88}

and if a supermartingale, verify

\mathbb {E}\left[Z_{n}\right] \leq \mathbb {E}\left[Z_{i}\right] \quad \text{for all } i, 1 \leq i < n. \tag {9.89}

Problem 9.23

Suppose $\left\{ Z_{n}; n \geq 1\right\}$ is a martingale. Show that

\mathbb {E}\left[Z_{m} \mid Z_{n_{i}}, Z_{n_{i-1}}, \ldots , Z_{n_{1}}\right] = Z_{n_{i}} \quad \text{for all } 0 < n_{1} < n_{2} < \cdots < n_{i} < m.

?

Problem 9.24

(a)(b)(c)

?

(a)

Assume that $\left\{ Z_{n}; n \geq 1\right\}$ is a submartingale. Show that

\mathbb {E}\left[Z_{m} \mid Z_{n}, Z_{n-1}, \ldots , Z_{1}\right] \geq Z_{n} \quad \text{for all } n < m.

(b)

Show that

\mathbb {E}\left[Z_{m} \mid Z_{n_{i}}, Z_{n_{i-1}}, \ldots , Z_{n_{1}}\right] \geq Z_{n_{i}} \quad \text{for all } 0 < n_{1} < n_{2} < \cdots < n_{i} < m.

(c)

Assume now that $\left\{ Z_{n}; n \geq 1\right\}$ is a supermartingale. Show that (a) and (b) still hold with $\geq$ replaced by $\leq$ .

Problem 9.25

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 9.26

This exercise uses a martingale to find the expected number of successive trials $\mathbb {E}\left[J\right]$ until some fixed pattern, $a_{1}, a_{2}, \ldots , a_{k}$ , of successive binary digits occurs within a sequence of IID binary rv's $X_{1}, X_{2}, \ldots$ (see Example 4.5.1 and Exercise 5.35 for alternative approaches). We take the stopping time $J$ to be the smallest $n$ for which $(X_{n-k+1}, \ldots , X_{n}) = (a_{1}, \ldots , a_{k})$ . A mythical casino and sequence of gamblers who follow a prescribed strategy will be used to determine $\mathbb {E}\left[J\right]$ . The outcomes of the plays (trials), $\left\{ X_{n}; n \geq 1\right\}$ at the casino is a binary IID sequence for which $\mathbb {P}\left(X_{n} = i\right) = p_{i}$ for $i \in \left\{ 0,1\right\}$ .

If a gambler places a bet $s$ on 1 at play $n$ , the return is $s/p_{1}$ if $X_{n} = 1$ and $0$ otherwise. With a bet $s$ on 0, the return is $s/p_{0}$ if $X_{n} = 0$ and $0$ otherwise; i.e., the game is fair.

?

(a)

Assume an arbitrary choice of bets on 0 and 1 by the various gamblers on the various trials. Let $Y_{n}$ be the net gain of the casino on trial $n$ . Show that $\mathbb {E}\left[Y_{n}\right] = 0$ . Let $Z_{n} = Y_{1} + Y_{2} + \cdots + Y_{n}$ be the aggregate gain of the casino over $n$ trials. Show that for any given pattern of bets, $\left\{ Z_{n}; n \geq 1\right\}$ is a martingale.

(b)

In order to determine $\mathbb {E}\left[J\right]$ for a given pattern $a_{1}, a_{2}, \ldots , a_{k}$ , we program our gamblers to bet as follows:

(i) Gambler 1 has an initial capital of 1 which is bet on $a_{1}$ at trial 1. If $X_{1} = a_{1}$ , the capital grows to $1/p_{a_{1}}$ , all of which is bet on $a_{2}$ at trial 2. If $X_{2} = a_{2}$ , the capital grows to $1/(p_{a_{1}}p_{a_{2}})$ , all of which is bet on $a_{3}$ at trial 3. Gambler 1 continues in this way until either losing at some trial (in which case he leaves with no money) or winning on $k$ successive trials (in which case he leaves with $1/\left[p_{a_{1}} \cdots p_{a_{k}}\right]$ ).

(ii) Gambler $\ell$ , for each $\ell > 1$ , follows the same strategy, but starts at trial $\ell$ . Note that if the pattern $a_{1}, \ldots , a_{k}$ appears for the first time at trials $n-k+1, n-k+2, \ldots , n$ , i.e., if $J = n$ , then gambler $n-k+1$ leaves at time $n$ with capital $1/\left[p(a_{1}) \cdots p(a_{k})\right]$ and gamblers $j < n-k+1$ have all lost their capital. We will come back later to investigate the capital at time $n$ for gamblers $n-k+2$ to $n$ .

First consider the string $a_{1}=0, a_{2}=1$ with $k = 2$ . Find the sample values of $Z_{1}, Z_{2}, Z_{3}$ for the sample sequence $X_{1} = 1, X_{2} = 0, X_{3} = 1, \ldots$ . Note that gamblers 1 and 3 have lost their capital, but gambler 2 now has capital $1/p_{0}p_{1}$ . Show that the sample value of the stopping time for this case is $J = 3$ . Given an arbitrary sample value $n \geq 2$ for $J$ , show that $Z_{n} = n - 1/p_{0}p_{1}$ .

(c)

Find $\mathbb {E}\left[Z_{J}\right]$ from (a). Use this plus (b) to find $\mathbb {E}\left[J\right]$ .

(d)

Repeat (b) and (c) using the string $(a_{1}, \ldots , a_{k}) = (1,1)$ and initially assuming $(X_{1}X_{2}X_{3}) = (011)$ . Be careful about gambler 3 for $J = 3$ . Show that $\mathbb {E}\left[J\right] = 1/p_{1}^{2} + 1/p_{1}$ .

(e)

Repeat (b) and (c) for $(a_{1}, \ldots , a_{k}) = (1,1,1,0,1,1)$ .

(f)

Consider an arbitrary binary string $a_{1}, \ldots , a_{k}$ and condition on $J = n$ for some $n \geq k$ . Show that the sample capital of gambler $\ell$ is then equal to

$0$ for $\ell < n-k$ ;
$1/\left[p_{a_{1}}p_{a_{2}} \cdots p_{a_{k}}\right]$ for $\ell = n-k+1$ ;
$1/\left[p_{a_{1}}p_{a_{2}} \cdots p_{a_{i}}\right]$ for $\ell = n-i+1$ , $1 \leq i < k$ if $(a_{1}, \ldots , a_{i}) = (a_{k-i+1}, \ldots , a_{k})$ ;
$0$ for $\ell = n-i+1$ , $1 \leq i < k$ if $(a_{1}, \ldots , a_{i}) \neq (a_{k-i+1}, \ldots , a_{k})$ .

Verify that this general formula agrees with (b), (d), and (e).

(g)

For a given binary string $(a_{1}, \ldots , a_{k})$ , and each $j$ , $1 \leq j \leq k$ let $\mathbb {I}_{j} = 1$ if $(a_{1}, \ldots , a_{j}) = (a_{k-j+1}, \ldots , a_{k})$ and let $\mathbb {I}_{j} = 0$ otherwise. Show that

\mathbb {E}\left[J\right] = \sum _{i=1}^{k} \frac{\mathbb {I}_{i}}{\prod _{m=1}^{i} p_{a_{m}}}.

Note that this is the same as the final result in Exercise 4.28. The argument is shorter here, but more motivated and insightful there. Both approaches are useful and lead to simple generalizations.

Problem 9.27

(a)(b)(c)

?

(a)

This exercise shows why the condition $\mathbb {E}\left[\left|Z_{J}\right|\right] < \infty$ is required in Lemma 9.8.4. Let $Z_{1} = -2$ and, for $n \geq 1$ , let $Z_{n+1} = Z_{n}\left[1 + X_{n}(3n+1)/(n+1)\right]$ where $X_{1}, X_{2}, \ldots$ are IID and take on the values $+1$ and $-1$ with probability $1/2$ each. Show that $\left\{ Z_{n}; n \geq 1\right\}$ is a martingale.

(b)

Consider the stopping trial $J$ such that $J$ is the smallest value of $n > 1$ for which $Z_{n}$ and $Z_{n-1}$ have the same sign. Show that, conditional on $n < J$ , $Z_{n} = (-2)^{n}/n$ and, conditional on $n = J$ , $Z_{J} = -(-2)^{n}(2n-1)/(n^{2}-n)$ .

(c)

Show that $\mathbb {E}\left[\left|Z_{J}\right|\right]$ is infinite, so that $\mathbb {E}\left[Z_{J}\right]$ does not exist according to the definition of expectation, and show that $\lim_{n \rightarrow \infty } \mathbb {E}\left[Z_{n} \mid J > n\right] \mathbb {P}\left(J > n\right) = 0$ .

Problem 9.28

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

This exercise shows why the supremum of a martingale can behave markedly differently from the maximum of an arbitrarily large number of the variables. More precisely, it shows that $\mathbb {P}\left(\sup_{n \geq 1} Z_{n} \geq a\right)$ can be unequal to $\mathbb {P}\left(\bigcup_{n \geq 1}\left\{ Z_{n} \geq a\right\} \right)$ .

?

(a)

Consider a martingale where $Z_{n}$ can take on only the values $2^{-n-1}$ and $1-2^{-n-1}$ , each with probability $1/2$ . Given that $Z_{n}$ , conditional on $Z_{n-1}$ , is independent of $Z_{1}, \ldots Z_{n-2}$ , find $\mathbb {P}\left(Z_{n} \mid Z_{n-1}\right)$ for each $n$ so that the martingale condition is satisfied.

(b)

Show that $\mathbb {P}\left(\sup_{n \geq 1} Z_{n} \geq 1\right) = 1/2$ and show that $\mathbb {P}\left(\bigcup_{n}\left\{ Z_{n} \geq 1\right\} \right) = 0$ .

(c)

Show that for every $\epsilon > 0$ , $\mathbb {P}\left(\sup_{n \geq 1} Z_{n} \geq a\right) \leq \mathbb {E}\left[Z_{1}\right]/(a-\epsilon )$ .

(d)

Use (c) to establish

\mathbb {P}\left(\sup _{n \geq 1} Z_{n} \geq a\right) \leq \frac{\mathbb {E}\left[Z_{1}\right]}{a} \quad \text{for all } a > 0. \tag {9.111}

Problem 9.29

Theorem 9.7.4 states: assume that $h$ is a convex function from $\mathbb {R}$ to $\mathbb {R}$ , that $\left\{ Z_{n}; n \geq 1\right\}$ is a martingale, and that $\mathbb {E}\left[\left|h(Z_{n})\right|\right] < \infty$ for all $n$ . Then $\left\{ h(Z_{n}); n \geq 1\right\}$ is a submartingale.

Show that Theorem 9.7.4 is also valid for martingales relative to a joint process. That is, show that if $h$ is a convex function of a real variable and if $\left\{ Z_{n}; n \geq 1\right\}$ is a martingale relative to a joint process $\left\{ Z_{n}, X_{n}; n \geq 1\right\}$ , then $\left\{ h(Z_{n}); n \geq 1\right\}$ is a submartingale relative to $\left\{ h(Z_{n}), X_{n}; n \geq 1\right\}$ .

?

Problem 9.30

Show that if $\left\{ Z_{n}; n \geq 1\right\}$ is a martingale (submartingale or supermartingale) relative to a joint process $\left\{ Z_{n}, X_{n}; n \geq 1\right\}$ and if $J$ is a stopping trial for $\left\{ Z_{n}; n \geq 1\right\}$ relative to $\left\{ Z_{n}, X_{n}; n \geq 1\right\}$ , then the stopped process is a martingale (submartingale or supermartingale) respectively relative to the joint process.

?

Problem 9.31

Prove Corollaries 9.9.3 to 9.9.5, i.e., prove the following three statements.

Let $\left\{ Z_{n}; n \geq 1\right\}$ be a martingale with $\mathbb {E}\left[Z_{n}^{2}\right] < \infty$ for all $n \geq 1$ . Then
$\mathbb {P}\left(\max _{1 \leq n \leq m} \left|Z_{n}\right| \geq b\right) \leq \frac{\mathbb {E}\left[Z_{m}^{2}\right]}{b^{2}} \quad \text{for all integer } m \geq 2, \text{ and all } b > 0.$
(Kolmogorov’s random walk inequality) Let $\left\{ S_{n}; n \geq 1\right\}$ be a random walk with $S_{n} = X_{1} + \cdots + X_{n}$ , where $\left\{ X_{i}; i \geq i\right\}$ is a set of IID rv’s with mean $\overline{X}$ and variance $\sigma^{2}$ . Then for any positive integer $m$ and any $\epsilon > 0$ ,
$\mathbb {P}\left(\max _{1 \leq n \leq m} \left|S_{n} - n\overline{X}\right| \geq m\epsilon \right) \leq \frac{\sigma ^{2}}{m\epsilon ^{2}}.$
Let $\left\{ S_{n}; n \geq 1\right\}$ be a random walk, $S_{n} = X_{1} + \cdots + X_{n}$ , where each $X_{i}$ has mean $\overline{X} < 0$ and semi-invariant MGF $\gamma (r)$ . For any $r > 0$ such that $0 < \gamma (r) < \infty$ , and for any $\alpha > 0$ ,
$\mathbb {P}\left(\max _{1 \leq i \leq n} S_{i} \geq \alpha \right) \leq \exp \left\{ -r\alpha + n\gamma (r)\right\} .$

?

Problem 9.32

(a)(b)

Let $\left\{ Z_{n}; n \geq 1\right\}$ be the scaled branching process of Section 9.6.2: $\left\{ X_{n}; n \geq 0\right\}$ is a branching process where $X_{n}$ is the aggregate number of elements of generation $n$ , each element $i$ of generation $n$ (for $1 \leq i \leq X_{n}$ ) has a number of offspring $Y_{i,n}$ collectively constituting generation $n+1$ (i.e. $X_{n+1} = \sum_{i=1}^{X_{n}} Y_{i,n}$ ), and the rv s $Y_{i,n}$ are IID over both $i$ and $n$ with mean $\overline{Y} := \mathbb {E}\left[Y_{i,n}\right]$ ; the scaled process is $Z_{n} := X_{n}/\overline{Y}^{n}$ .

?

(a)

Assume that $Y$ , the number of offspring of each element, has finite mean $\overline{Y}$ and finite variance $\sigma^{2}$ . Assume that the population at time 0 is 1. Show that

\mathbb {E}\left[Z_{n}^{2}\right] = 1+\sigma ^{2}\left[\overline{Y}^{-2}+\overline{Y}^{-3}+\cdots +\overline{Y}^{-n-1}\right].

(b)

Assume that $\overline{Y} > 1$ and find $\lim_{n \rightarrow \infty } \mathbb {E}\left[Z_{n}^{2}\right]$ . Show from this that the conditions for the martingale convergence theorem, Theorem 9.9.8, are satisfied.

Remark.

?

Theorem 9.9.8 (Martingale convergence theorem): let $\left\{ Z_{n}; n \geq 1\right\}$ be a martingale and assume that there is some finite $M$ such that $\mathbb {E}\left[Z_{n}^{2}\right] \leq M$ for all $n$ . Then there is a rv $Z$ such that, for all sample sequences except a set of probability 0, $\lim_{n \rightarrow \infty } Z_{n} = Z$ .

Note: this condition is not satisfied if $\overline{Y} \leq 1$ . The general martingale convergence theorem requires only a bounded first absolute moment, so it holds for $\overline{Y} \leq 1$ .

Problem 9.33

Show that if $\left\{ Z_{n}; n \geq 1\right\}$ is a martingale (submartingale or supermartingale) relative to a joint process $\left\{ Z_{n}, X_{n}; n \geq 1\right\}$ and if $J$ is a stopping trial for $\left\{ Z_{n}; n \geq 1\right\}$ relative to $\left\{ Z_{n}, X_{n}; n \geq 1\right\}$ , then the stopped process satisfies (9.98), (9.99), or (9.100) respectively.

?

Problem 9.34

Show that if $\left\{ Z_{n}; n \geq 1\right\}$ is a martingale relative to a joint process $\left\{ Z_{n}, X_{n}; n \geq 1\right\}$ and if $J$ is a stopping trial for $\left\{ Z_{n}; n \geq 1\right\}$ relative to $\left\{ Z_{n}, X_{n}; n \geq 1\right\}$ , then $\mathbb {E}\left[Z_{J}\right] = \mathbb {E}\left[Z_{1}\right]$ if and only if (9.104) is satisfied.

?

Problem 9.35

Consider an investment example similar to that of Example 9.10.1 in which there is only one investment other than cash. The ratio $X$ of that investment value at the end of an epoch to that at the beginning is either 2 or $1/4$ , each with equal probability. Thus $\mathbb {P}\left(X=2\right) = 1/2$ and $\mathbb {P}\left(X=1/4\right) = 1/2$ . Successive ratios, $X_{1}, X_{2}, \ldots$ , are IID.

?

(a)

In (a)--(c), assume a fixed allocation strategy where a fraction $\lambda$ is kept in the double-or-quarter investment and $1-\lambda$ is kept in cash. Find the expected wealth, $W_{n}(\lambda )$ and the expected log wealth $\mathbb {E}\left[L_{n}(\lambda )\right]$ as a function of a constant $\lambda \in \left[0,1\right]$ and $n \geq 1$ . Assume unit initial wealth.

(b)

For $\lambda =1$ , find the PMF for $W_{4}(1)$ and give a brief explanation of why $\mathbb {E}\left[W_{n}(1)\right]$ is growing exponentially with $n$ but $\mathbb {E}\left[L_{n}(1)\right]$ is decreasing linearly toward $-\infty$ .

(c)

Using the same approach as in Example 9.10.1, find the value of $\lambda^{*}$ that maximizes $\mathbb {E}\left[L_{n}(\lambda )\right]$ . Show that your solution satisfies the optimality conditions in (9.136).

(d)

Find the range of $\lambda$ over which $\mathbb {E}\left[L_{n}(\lambda )\right]$ is positive.

(e)

Find the PMF of the rv $Z_{n}/Z_{n-1}$ as given in (9.138) for any given $\lambda_{n}$ .

Problem 9.36

An interesting special case of this simple theory of investment is the horse-racing game due to J. Kelly. There are $\ell -1$ horses in a race and each horse $j$ wins with some probability $p(j) > 0$ . One and only one horse wins, and if $j$ wins, the gambler receives $r(j) > 0$ for each dollar bet on $j$ and nothing for the bets on other horses. In other words, the price-relative $X(j)$ for each $j$ , $1 \leq j \leq \ell -1$ , is $r(j)$ with probability $p(j)$ and 0 otherwise. For cash, $X(\ell )=1$ .

The gambler's allocation of wealth on the race is denoted by $\lambda (j)$ on each horse $j$ with $\lambda (\ell )$ kept in cash. As usual, $\sum_{j} \lambda (j)=1$ and $\lambda (j) \geq 0$ for $1 \leq j \leq \ell$ . Note that $X(1), \ldots , X(\ell -1)$ are highly dependent, since only one has a nonzero sample value in any race.

?

(a)

For any given allocation $\overrightarrow {\lambda }$ find the expected wealth and the expected log wealth at the end of a race for unit initial wealth.

(b)

Assume that a statistically identical sequence of races is run, i.e., $\overrightarrow {X}_{1}, \overrightarrow {X}_{2}, \ldots$ , are IID, where each $\overrightarrow {X}_{n} = \left(X_{n}(1), \ldots , X_{n}(\ell )\right)^{\mathsf{T}}$ . Assuming a constant allocation on each race and unit initial wealth, find the expected log wealth $\mathbb {E}\left[L_{n}(\overrightarrow {\lambda })\right]$ at the end of the $n$ th race and express it as $n\mathbb {E}\left[Y(\overrightarrow {\lambda })\right]$ .

(c)

Let $\overrightarrow {\lambda }^{*}$ maximize $\mathbb {E}\left[Y(\overrightarrow {\lambda })\right]$ . Use the necessary and sufficient condition (9.136) on $\overrightarrow {\lambda }^{*}$ for horse $j$ , $1 \leq j < \ell$ to show that $\lambda^{*}(j)$ can be expressed in the following two equivalent ways; each uniquely specifies each $\lambda^{*}(j)$ in terms of $\lambda^{*}(\ell )$ .

\begin{align} \lambda ^{*}(j) & \geq p(j)-\frac{\lambda ^{*}(\ell )}{r(j)}; \qquad \text{with equality if } \lambda ^{*}(j) > 0. \\ \lambda ^{*}(j) & = \max \left\{ p(j)-\frac{\lambda ^{*}(\ell )}{r(j)}, 0\right\} . \end{align}

Solving for $\lambda^{*}(\ell )$ (which in turn specifies the other components of $\overrightarrow {\lambda }^{*}$ ) breaks into 3 special cases which are treated below in (d), (e), and (f) respectively. The first case, in (d), shows that if $\sum_{j<\ell } 1/r(j) < 1$ , then $\lambda^{*}(\ell )=0$ . The second case, in (e), shows that if $\sum_{j<\ell } 1/r(j) > 1$ , then $\lambda^{*}(\ell ) > \min_{j}(p(j)r(j))$ , with the specific value specified by the unique solution to

\sum _{j<\ell } \frac{p(j)}{\max \left[p(j)r(j), \; \lambda ^{*}(\ell )\right]} \leq 1; \qquad \text{with equality if } \lambda ^{*}(\ell ) > 0.

The third case, in (f), shows that if $\sum_{j<\ell } 1/r(j)=1$ , then $\lambda^{*}(\ell )$ is nonunique, and its set of possible values occupy the range $\left[0, \min_{j}\left(p(j)r(j)\right)\right]$ .

(d)

Sum the first inequality of (c) over $j$ to show that if $\lambda^{*}(\ell ) > 0$ , then $\sum_{j<\ell } 1/r(j) \geq 1$ . Note that the logical obverse of this is that $\sum_{j<\ell } 1/r(j) < 1$ implies that $\lambda^{*}(\ell )=0$ and thus that $\lambda^{*}(j)=p(j)$ for each horse $j$ .

(e)

In (c), $\lambda^{*}(j)$ for each $j < \ell$ was specified in terms of $\lambda^{*}(\ell )$ ; here you are to use the necessary and sufficient condition (9.136) on cash to specify $\lambda^{*}(\ell )$ . More specifically, you are to show that $\lambda^{*}(\ell )$ satisfies each of the following two equivalent inequalities:

\begin{align} \sum _{j<\ell } \frac{p(j)}{\lambda ^{*}(j)r(j)+\lambda ^{*}(\ell )} & \leq 1; \qquad \text{with equality if } \lambda ^{*}(\ell ) > 0. \\ \sum _{j<\ell } \frac{p(j)}{\max \left[p(j)r(j), \; \lambda ^{*}(\ell )\right]} & \leq 1; \qquad \text{with equality if } \lambda ^{*}(\ell ) > 0. \end{align}

Show from the second inequality above that if $\lambda^{*}(\ell ) \leq p(j)r(j)$ for each $j$ , then $\sum_{j} 1/r(j) \leq 1$ . Point out that the logical obverse of this is that if $\sum_{j} 1/r(j) > 1$ , then $\lambda^{*}(\ell ) > \min_{j}\left(p(j)r(j)\right)$ . Explain why this second inequality has a unique solution for $\lambda^{*}(\ell )$ in this case. Note that $\lambda^{*}(j)=0$ for each $j$ such that $p(j)r(j) < \lambda^{*}(\ell )$ .

(f)

Now consider the case in which $\sum_{j<\ell } 1/r(j)=1$ . Show that the second inequality of (e) is satisfied with equality for each choice of $\lambda^{*}(\ell )$ , $0 \leq \lambda^{*}(\ell ) \leq \min_{j<\ell }\left(p(j)r(j)\right)$ .

(g)

Consider the special case of a race with only two horses. Let $p(1)=p(2)=1/2$ . Assume that $r(1)$ and $r(2)$ are large enough to satisfy $1/r(1)+1/r(2) < 1$ ; thus no cash allotment is used in maximizing $\mathbb {E}\left[Y(\overrightarrow {\lambda })\right]$ . With $\lambda (3)=0$ , we have

\mathbb {E}\left[Y(\overrightarrow {\lambda })\right] = \frac{1}{2}\ln \left[\lambda (1)r(1)\right]+\frac{1}{2}\ln \left[\lambda (2)r(2)\right] = \frac{1}{2}\ln \left[\lambda (1)r(1)\left(1-\lambda (1)\right)r(2)\right].

Use this equation to give an intuitive explanation for why $\lambda^{*}(1)=1/2$ , independent of $r(1)$ and $r(2)$ .

(h)

Again consider the special case of two horses with $p(1)=p(2)=1/2$ , but let $r(1)=3$ and $r(2)=3/2$ . Show that $\overrightarrow {\lambda }^{*}$ is nonunique with $(1/2,1/2,0)$ and $(1/4,0,3/4)$ as possible values. Show that if $r(2) > 3/2$ , then the first solution above is unique, and if $r(2) < 3/2$ , then the second solution is unique, assuming $p(1)=1/2$ and $r(1)=3$ throughout.

(i)

For the case where $\sum_{j<\ell } 1/r(j)=1$ , define $q(j)=1/r(j)$ as a PMF on $\left\{ 1, \ldots , \ell -1\right\}$ . Show that $\mathbb {E}\left[Y(\overrightarrow {\lambda }^{*})\right] = D(\mathsf{p} \parallel \mathsf{q})$ for the conditions of (f).

Remark.

?

Note (part (h)): the case $3/2 < r(2) < 2$ provides an example where an investment is used to maximize log-wealth even though $\mathbb {E}\left[X(2)\right] = p(2)r(2) < 1$ , i.e., horse 2 is a poor investment, but is preferable to cash in this case as a hedge against horse 1 losing.

Note (part (i)): to interpret this, we could view a horse race where each horse $j$ has probability $q(j)$ of winning the reward $r(j)=1/q(j)$ as a fair game'. Our gambler, who knows that the true probabilities are $\left\{ p(j); 1 \leq j < \ell \right\}$, then has inside information' if $p(j) \neq q(j)$ , and can establish a positive rate of return equal to $D(\mathsf{p} \parallel \mathsf{q})$ .

Problem 9.37

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

Let the function $h_{\epsilon }(u)$ have the value 0 for $-\epsilon < \mathbb {E}\left[Y(\overrightarrow {\lambda })\right] < \epsilon$ and the value 1 elsewhere.

?

(a)

Show that $\lim_{n \rightarrow \infty } h_{\epsilon }\left(L_{n}(\overrightarrow {\lambda })\right) = 0$ WP1.

(b)

Show that for all $\epsilon > 0, \delta > 0$ , there is an $n_{o}$ such that

\mathbb {P}\left(\bigcup _{n \geq n_{o}} \left\{ \left|\frac{1}{n}L_{n}(\overrightarrow {\lambda })-\mathbb {E}\left[Y(\overrightarrow {\lambda })\right]\right| > \epsilon \right\} \right) \leq \delta .

(c)

Show that the probability of the complementary event is

\mathbb {P}\left(\bigcap _{n \geq n_{o}} \left\{ \mathbb {E}\left[Y(\overrightarrow {\lambda })\right]-\epsilon \leq \frac{1}{n}L_{n}(\overrightarrow {\lambda }) \leq \mathbb {E}\left[Y(\overrightarrow {\lambda })\right]+\epsilon \right\} \right) > 1-\delta .

(d)

Show that

\mathbb {P}\left(\bigcap _{n \geq n_{o}} \left\{ \exp \left[n\left(\mathbb {E}\left[Y(\overrightarrow {\lambda })\right]-\epsilon \right)\right] \leq W_{n}(\overrightarrow {\lambda }) \leq \exp \left[n\left(\mathbb {E}\left[Y(\overrightarrow {\lambda })\right]+\epsilon \right)\right]\right\} \right) > 1-\delta .

Remark.

?

Theorem 9.10.2: assume that $\mathbb {E}\left[\left|Y(\overrightarrow {\lambda })\right|\right] < \infty$ . Then for every $\epsilon , \delta > 0$ , there exists an $n_{o}$ such that

\mathbb {P}\left(\bigcap _{n \geq n_{o}} \left\{ \exp \left[n\left(\mathbb {E}\left[Y(\overrightarrow {\lambda })\right]-\epsilon \right)\right] \leq W_{n}(\overrightarrow {\lambda }) \leq \exp \left[n\left(\mathbb {E}\left[Y(\overrightarrow {\lambda })\right]+\epsilon \right)\right]\right\} \right) > 1-\delta .

Problem 9.38

(a)(b)(c)

In this exercise, you are to express the buy-and-hold strategy and the two-pile strategy of (9.137) as special cases of a time-varying allocation.

?

(a)

Suppose the buy-and-hold strategy starts with an allocation $\overrightarrow {\lambda }_{1}$ . Let $W_{n}(k)$ be the investor's wealth in investment $k$ at time $n$ . Show that

W_{n}(k) = \lambda _{1}(k) \prod _{m=1}^{n} X_{m}(k).

(b)

Show that $\lambda_{n}(k)$ can be expressed in each of the following ways:

\lambda _{n}(k) = \frac{W_{n-1}(k)}{\sum _{j} W_{n-1}(j)} = \frac{\lambda _{n-1}(k)X_{n-1}(k)}{\sum _{j} \lambda _{n-1}(j)X_{n-1}(j)}.

(c)

For the two pile strategy of (9.137), verify (9.137) and find an expression for $\lambda_{n}(k)$ .

Problem 9.39

(a)(b)(c)

?

(a)

Consider the martingale $\left\{ Z_{n}; n \geq 1\right\}$ where $Z_{n} = W_{n}/W_{n}^{*}$ and $W_{n}$ is the wealth at time $n$ for the pure triple or nothing strategy of Example 9.10.1 and $W_{n}^{*}$ is the wealth using the constant allocation $\overrightarrow {\lambda }^{*}$ . Find the PMF of $Z$ where $Z = \lim_{n \rightarrow \infty } Z_{n}$ WP1.

(b)

Now consider the two-pile strategy of (9.137) and find the PMF of the limiting rv $Z$ for this strategy.

(c)

Now consider a `tempt-the-fates' strategy where one uses the pure triple or nothing strategy for the first three epochs and uses the constant allocation $\overrightarrow {\lambda }^{*}$ thereafter. Again find the PMF of the limiting rv $Z$ .

Problem 9.40

(a)(b)(c)

Consider the Markov modulated random walk in the figure below. The rv s $Y_{n}$ in this example take on only a single value for each transition, that value being 1 for all transitions from state 1, 10 for all transitions from state 2, and 0 otherwise. $\epsilon > 0$ is a very small number, say $\epsilon < 10^{-6}$ .

{#fig-1 width="50%"}

?

(a)

Show that the steady-state gain per transition is $5.5/(1+\epsilon )$ . Show that the relative-gain vector is $\overrightarrow {w} = \left(0, (\epsilon -4.5)/\left[\epsilon (1+\epsilon )\right], (10\epsilon +4.5)/\left[\epsilon (1+\epsilon )\right]\right)$ .

(b)

Let $S_{n} = Y_{0}+Y_{1}+\cdots +Y_{n-1}$ and take the starting state $X_{0}$ to be 0. Let $J$ be the smallest value of $n$ for which $S_{n} \geq 100$ . Find $\mathbb {P}\left(J=11\right)$ and $\mathbb {P}\left(J=101\right)$ . Find an estimate of $\mathbb {E}\left[J\right]$ that is exact in the limit $\epsilon \rightarrow 0$ .

(c)

Show that $\mathbb {P}\left(X_{J}=1\right) = (1-45\epsilon +o(\epsilon ))/2$ and that $\mathbb {P}\left(X_{J}=2\right) = (1+45\epsilon +o(\epsilon ))/2$ . Verify, to first order in $\epsilon$ , that (9.159) is satisfied.

Problem 9.41

Show that (9.159) results from taking the derivative of (9.163) and evaluating it at $r=0$ .

?

Problem 9.42

(a)(b)(c)

Let $\left\{ Z_{n}; n \geq 1\right\}$ be a martingale, and for some integer $m$ , let $Y_{n} = Z_{n+m}-Z_{m}$ .

?

(a)

Show that $\mathbb {E}\left[Y_{n} \mid Z_{n+m-1}=z_{n+m-1}, Z_{n+m-2}=z_{n+m-2}, \ldots , Z_{m}=z_{m}, \ldots , Z_{1}=z_{1}\right] = z_{n+m-1}-z_{m}$ .

(b)

Show that $\mathbb {E}\left[Y_{n} \mid Y_{n-1}=y_{n-1}, \ldots , Y_{1}=y_{1}\right] = y_{n-1}$ .

(c)

Show that $\mathbb {E}\left[\left|Y_{n}\right|\right] < \infty$ . Note that (b) and (c) show that $\left\{ Y_{n}; n \geq 1\right\}$ is a martingale.

Problem 9.43

(a)(b)

This exercise views the continuous-time branching process of Exercise 7.15 as a stopped random walk. Recall that the process was specified there as a Markov process such that for each state $j$ , $j \geq 0$ , the transition rate to $j+1$ is $j\lambda$ and to $j-1$ is $j\mu$ . There are no other transitions, and in particular, there are no transitions out of state 0, so that the Markov process is reducible. Recall that the embedded Markov chain is the same as the embedded chain of an $\mathrm{M}/\mathrm{M}/1$ queue except that there is no transition from state 0 to state 1.

?

(a)

To model the possible extinction of the population, convert the embedded Markov chain above to a stopped random walk, $\left\{ S_{n}; n \geq 0\right\}$ . The stopped random walk starts at $S_{0}=0$ and stops on reaching a threshold at $-1$ . Before stopping, it moves up by 1 with probability $\lambda /(\lambda +\mu )$ and downward by 1 with probability $\mu /(\lambda +\mu )$ at each step. Give the (very simple) relationship between the state $X_{n}$ of the Markov chain and the state $S_{n}$ of the stopped random walk for each $n \geq 0$ .

(b)

Find the probability that the population eventually dies out as a function of $\lambda$ and $\mu$ . Be sure to consider all three cases $\lambda > \mu$ , $\lambda < \mu$ , and $\lambda =\mu$ .