MTH 504 Homework

Homework 12

1. 13.13 This seems like a fun problem. I think it is related to the “move-to-front” chain which is the reversal of the top-to-random shuffle we will study soon.

2. 13.14 Fun return time problem for a knight on a chess board.

3. Use the strong Markov property to show that $\rho_{xz} \geq \rho_{xy} \rho_{yz}$.

4. Suppose $p$ is irreducible, $f$ is harmonic on $F$ and $f(x) \to \infty$ as $x \to \infty$; i.e., ${x \colon f(x) \leq M }$ is finite for any $M < \infty$. Then the chain is recurrent.

5. Consider a telephone system with an infinite number of lines (a telephone is like an iPhone without a screen). This is called the $M/M/\infty$ queue. Let $X_n$ be the number of phone lines in use at time $n$ and suppose

   $$X_{n+1} = \sum_{m=1}^{X_n} \xi_{n,m} + Y_{n+1}$$

   where $\xi_{n,m}$ are iid with $P(\xi_{n,m} = 1)$ and $P(\xi_{n,m} = 0) = 1-p$ and $Y_n$ is an independent iid sequence of Poisson mean $\lambda$ rvs. In words, for each conversation we flip a coin with probability $p$ of heads to see if it continues for another minute. Meanwhile, a Poisson mean $\lambda$ number of conversations start between time $n$ and $n+1$. Show that the chain is recurrent for $p < 1$.

6. Let $w_{xy} = P_x( T_y < T_x)$. Show that $\mu_x(y) = w_{xy}/w_{yx}$.

7. For the $M/M/\infty$, compute the distribution at time $1$ when $X_0 = \Poisson(\mu)$ and use the result to find the stationary distribution.

Homework 11

1. 13.10 The Doob h-transform. Please pick this one to do in class!

2. 13.11 This is a process related to the running maximum of an increasing process, it is surprising that it is an irreducible Markov chain.

3. 13.12 This is a hitting location problem for a simple random walk. It results in a cute formula for the location of the random walk at the hitting time.

Homework 10

1. 13.8 For a random walk starting at $0 \in \mathbb{Z}$, find the expected number of visits to a site $k \neq 0$ before the first return to $1$.

2. 13.9 Kolmogorov criterion for reversibility. Show that a reversible measure exists iff

   $$\prod_{i=1}^n \frac{Q(x_i,x_{i-1})}{Q(x_{i-1},x_i)} = 1$$

3. Take a random walk on $\Z$ with iid $0$-mean increments. Show that all states are recurrent. Also show that the simple random walk in $d \geq 3$ is transient.

Homework 9

1. 13.6 Birth and Death Process.

2. 13.7 $Q$ is a markov chain on $0,1,2,\ldots,N$ defined using $\Binomial(N,i/N)$. Classify its states, and determine the law of $X_\infty$.

3. 13.8 Show that the expected number of visits of the SRW on $\Z$ to $k \neq 0$ before the first return to $0$ is $1$.

Homework 8

1. 13.1 Image of a Markov chain (under a consistency condition) is a Markov chain.

2. 13.2 Use 13.2 to show the random walk on the binary tree is transient.

3. 13.5 Find the probability of extinction of the Galton-Watson process. Fun problem.

Homework 7

1. Consider the paths of the nearest-neighbor simple random walk on $\mathbb{Z}$. Show that the number of paths that go from $(0,0)$ to $(n,x)$ is $\binom{n}{(n+x)/2}$.

   1. Show that if $x,y > 0$ then the number of paths from $(0,x)$ to $(n,y)$ that are 0 at some time is equal to the number of paths from $(0,-x)$ to $(n,y)$. Conclude that number of paths from $(1,1)$ to $(n,x)$ that hit $0$ at some time is the same as the number of paths $(1,-1$ to $(n,x)$.

   2. Consider an election in which candidate $B$ gets $\beta$ votes and $A$ gets $\alpha > \beta$ votes. Let $\xi_i \in \{-1,1\}$ with uniform probability and interpret 1s and -1s as votes for $A$ and $B$. Thus $S_k$ denotes the lead that $A$ has over $B$ by the time vote $k$ is counted. Suppose that $A$ receives $\alpha$ votes and $B$ receives $\beta$. Let $n = \alpha + -\beta$. Consider the event

      $$G = \{ A \text{ leads } B \text{ throughout the counting} \}.$$

      Show that $P(G) = (\alpha - \beta)/n$.

   3. Suppose $S_0 = 0$. Show that $P(S_1 \neq 0, S_2 \neq 0, S_{2n} \neq 0) = P(S_{2n} = 0)$.

2. Let $\{\xi_j\}_{j=1}^n$ be iid nonnegative integer valued rvs. Let $S_k = \sum_{j=1}^k \xi_j$ and consider the event

   $$G = \{S_j < j \colon 1 \leq j < n\}$$

   Then, consider the backward martingale $X_{-j} = S_j/j$, and let $T = \inf\{ k \geq -n \colon X_k \geq 1\}$. If the set the infimum is taken over is empty, then set $T = -1$. Show, using the stopping theorem that

   $$P(G | S_n) = (1 - S_n/n)^+$$

   Relate this result to the previous problem.

   Hint: See Durrett, example 4.7.5 version 5a

3. Show the existence of regular conditional probabilities by reading Chapter 6 of Kallenberg (2002).

Homework 6

1. Le Gall 12.11. This is Rademacher’s theorem

2. Le Gall 12.14. Another proof of the strong law

3. Le Gall 12.15 Law of the Iterated Logarithm

Homework 5

1. Le Gall 12.12. Consider a sequence of $(X_n)$ with the special property

   $$P\left( X_{n+1} = \frac{X_n}{2} \right) = 1 - X_n, \quad P\left( X_{n+1} = \frac{1 + X_n}{2} \right) = X_n$$

   Show that it is a martingale, and compute its limit

2. Le Gall 12.13. Polya’s Urn redux.

3. Le Gall 12.16. Kakutani’s theorem about products of positive random variables.

4. Le Gall 12.17. Let $(X_n)$ be a sequence of independent Bernoulli random variables with $p = 1/2$. Let $(\alpha_n)$ be any sequence of positive numbers. Let

   $$S_n = \sum_{j=1}^n \alpha_j X_j$$

   Prove that $S_n$ converges if $(\alpha_n)$ is in $\ell^2$.

   solution

Homework 4

We will continue working through Le Gall’s exercises, all of which are tastefully chosen. We have also found our first typo in Le Gall in Homework 3!

1. (12.7 Le Gall). Let $(X_n)$ be a Martingale with $X_0 = 0$, assume that it has bounded increments. Show that almost surely, either it has a finite limit, or if not, both $\sup X_n = +\infty$ and $\inf X_n = -\infty$ (it fluctuates wildly).
2. (12.8 Wald’s identity). Let $X_n$ be iid, and suppose $S_n$ is their usual sum. Suppose $T$ is a stopping time (with finite expectation) so that $S$ is a sum with a random number of elements (this is frequently encountered). Prove that $E[S_T] = E[T] E[X_1]$; i.e., the expected value value of the sum is the expected number of elements times the expected value of each element.
3. (12.9). Yet another proof of the Strong law. This might be a nice problem for somebody to do.
4. (12.10). Let $\tau_\infty$ be the tail $\sigma$-algebra of an iid sequence $X_n$. Give a Martingale proof of the Kolmogorov $0$-$1$ law.

Homework 3

1. Polya’s Urn. An urn contains $r$ red and $g$ green balls. At each turn, we take a ball out uniformly at random. Then, we replace it and add $c$ more balls of the same color. Let $X_n$ be the fraction of green balls.

   1. Show that $\exists X_{\infty}$ such that $X_n \to X_{\infty}$ almost surely.
   2. Find the distribution of $X_{\infty}$ in the special case where $c=1,g=1,r=1$.
   3. Simulate Polya’s urn on a computer and graph $X_n$

2. Prove that Doob’s maximal inequalities imply Kolmogorov’s inequalities.

3. Le Gall 12.2 Prove that $A \cap \{ T \geq n \} \in \mathcal{F}$ and so on.

4. Le Gall 12.3 Suppose $P(T \leq n + N \vert \mathcal{F}_n) \geq \epsilon$. Then $T < \infty ~ \almostsurely$ and $E[T] < \infty$.

5. Le Gall 12.4 Let $S_n$ be a simple random walk and $\phi \colon \Z \times \Z^+ \to \R$ satisfy

   $$\phi(s + 1, n + 1) + \phi(s - 1, n+ 1) = 2 \phi(s,n)$$

   Show that $\phi(S_n,n)$ is a martingale (among other things).

6. Le Gall 12.5 Prove that an adapted process $X_n$ is a martingale iff $E[X_T] = E[X_0]$ for every bounded stopping time $T$.

7. Le Gall 12.6 A preview of uniform integrability. Let $X_n$ be a martingale, and let $T$ be a stopping time such that

   $$P(T < \infty) = 1, E[\vert X_T\vert ] < \infty, E[\vert X_n\vert 1_{T > n}] \to 0$$

   Prove that $E[\vert X_T - X_{T \wedge n} \vert ] \to 0$. Conclude that $E[X_T] = E[X_0]$.

Homework 2

1. A (discrete) semimartingale is any process $X_n$ that can be written as $X_n = Y_n + Z_n$ where $Y_n$ is a martingale, and $Z_n$ is a bounded variation process; i.e., $Z_n = U_n - V_n$ where $U_n,V_n$ are adapted processes that are increasing in $n$. Prove that any semimartingale can be written as a difference of a submartingale and a supermartingale.

2. Suppose $\{T_i\}_{i=1}^n$ are stopping times. Show that

   a. $\sum_{i=1}^n T_i$

   b. $\max( T_1, \ldots, T_n)$

   are stopping times.

3. Let $T$ be a stopping time. Let $X$ be a martingale. Prove that $X_T$ is integrable and

   $$\E[ X_T ] = \E[X_0]$$

   in each of the following situations.

   a. $T$ is bounded almost surely (proved in class)

   b. $X$ is bounded and $T$ is $\almostsurely$ finite

   c. $\E[T] < \infty$ and for some $K \in \R^+$,

   $$| X_n(\w) - X_{n-1}(\w) | \leq K \forall (n,\w)$$

4. Let $X$ be a supermartingale and $T$ be stopping time. Let $C^T$ be the process defined by

   $$C^T_n = 1_{n \leq T}$$

   a. Show that $C^T_n$ is previsible. Let

   $$Y_n = X_0 + \sum_{i=1}^n C^T_i X_{i} - X_{i-1}$$

   b. Show that $Y = X_{T \land n}$ and that it is a supermartingale. Use this to show that

   $$\E[ X_{T \land n} ] \leq \E[ X_0 ]$$

5. Let $X$ be a submartingale, and for $\lambda \in \R$, let

   $$T = \inf \{ j \geq 1 \colon X_j \geq \lambda \}$$

   a. Show that $T$ is a stopping time.

   b. Show that

   $$\E[ | X_n | ] \geq \E[ X_n, T \leq n]$$

Homework 1

1. Prove the following basic properites of conditional expectation. We are working on a space $(\Omega,\mathcal{F},P)$.

   • Tower property: $E[ E[X \vert \Sigma_1 ] \vert \Sigma_2 ] = E[ X \vert \Sigma_2]$ where $\Sigma_2 \subset \Sigma_1 \subset \mathcal{F}$
   • If $Y$ is independent of $\Sigma$ then $E[ Y \vert \Sigma ] = E[Y]$
   • If $X$ is $\Sigma$ measurable, then $E[X \vert \Sigma ] = X$ almost surely.
   • Let $\mathcal{A}_n$ be a sequence of (sub) $\sigma$-algebras and $X_n$ be a sequence of nonnegative $\mathcal{F}$ measurable random variables. Prove that if $E[X_n \vert \mathcal{A}_n ]$ converges in probability to $0$, then $X_n \to 0$ in probability. Prove that the converse is false.

2. Let $\{X_i\}_{i=1}^{\infty}$ be a collection of iid random variables. If $f$ is a tail-measurable function, show that $f$ is a constant.

3. a. If $X$ is a random variable with continuous distribution and $B$ is such that $\Prob(B) > 0$, show that

   $$\E[ X | B ] = \frac{1}{\Prob(B)} \int X 1_B d\Prob$$

   b. (From textbook) Let $(X,Y)$ be an absolutely continuous random varaible with piecewise-continuous density $f(x,y)$. Prove that for every non-negative measurable $h \colon \R \to \R$,

   $$E[ h(X) | Y ] = \frac{ \int_{-\infty}^{\infty} h(x) f(x,Y) dx}{ \int_{-\infty}^{\infty} f(x,Y) dx} \quad \almostsurely$$

   Even though $\Prob(Y = y) = 0$ for all $y \in \R$, use the preceding to justify the classical definition,

   $$P(X \leq a | Y = y) = \frac{\int_{-\infty}^a f(x,y)dx}{\int_{-\infty}^{\infty} f(x,y)dx} \quad \forall a \in \R$$

4. a. If $X$ is a martingale and $\psi$ is convex, then $\psi(X)$ is a submartingale if $\psi(X_n) \in L^1(\Prob)$ for all $n$. b. If $X$ is a submartingale, then $\psi(X)$ is a submartingale if $\psi$ is nondecreasing in addition to convex and integrable.

5. Suppose $X_m$ is a submartingale bounded in $L^1$. Show that

   $$\lim_{m \to \infty} E[X_m] = \sup_m \E[ X_m ]$$