MATH 5050 Homework

HW 4

Problem 0

Simulate a trajectory of Brownian motion on the interval $[0,1]$ on a mesh with $10000$ to $100000$ points. Figure out how to do this by reading the textbook.

Simulate a random walk trajectory with $\pm 1$ increments for $n$ steps. Scale the random walk trajectory so that it compares with a Brownian motion trajectory on $[0,1]$. Try it for $(n=100,1000,10000)$.

Plot trajectories of Brownian motion and the random walk on the same figure.

Problem 1

Let $B(t)$ be standard Brownian motion.

a. Calculate numerically $\int_0^t B(s)\,dB(s)$ for $0\le t\leq 10$. Use the leftmost points of the partition intervals and then the rightmost points. Plot both solutions (using the same copy of Brownian motion, not two independent copies).

b. Based on the plots, which of the two is the right one and why?

c. Calculate $\int_0^t B(s)\,dB(s)$ explicitly (not numerically).

Hint: Use Ito’s formula: $f(Bt.)=f(B(0))+\int_0^t f'(B(s))\,dB(s)+\frac12\int_0^t f''(B(s))\,ds$ with $f(x)=x^2$.

d. If you use the same Brownian motion for the plots in (a) as well as to plot the explicit solution you got in (c), then the latter should match one of the former two. Is this the case? Does this agree with your answer to (b)?

Problem 2

Let $B(t)$ be standard Brownian motion. Let $\lambda$ be a positive constant and let $X(t)=e^{\lambda B(t)}$.

a. Apply Ito’s formula to the function $f(x)=e^{\lambda x}$ to prove that $X(t)$ solves

b. Let $A(t)=E[X(t)]$. Observe that $A(0)=0$. Using the fact that a stochastic integral is a martingale prove that $A(t)=\frac{\lambda^2}2\int_0^t A(s)\,ds$.

c. The equation in (b) says that $A’(t)/A(t)=\frac{\lambda^2}2$. Is this a stochastic differential equation? Integrate both sides (and use $A(0)=0$) to find the formula for $A(t)$.

d. What is the distribution of $B(t)$? Can you compute $E[e^{\lambda B(t)}]$ directly? Does your answer agree with (c)?

HW 3

Due Apr 10

Question 1

Prove the chapman kolmogorov equation. Let $p_t(x,y)$ be the transition density of brownian motion.

1. Show explicitly using the explicit formula for $p_t(x,y)$ that $p_{t+s}(x,y) = \int_{-\infty}^{\infty} p_s(x,z) p_{t}(z,y) dz$
2. Can you show this using the Markov property for Brownian motion, (see page 177 of lawler) $\E[ 1_{A}(B(t+s)) | \mathcal{F}_s ] = \E[ 1_{A}(B(t+s)) | B(s) ]$ Hint: the expectation turns into a probability. To find the density, perhaps it’s better to look at the cdf instead. For example, the probability that the BM is in a set $A$ at time $t$ is an integral over the transition density.

Question 2

Brownian scaling.

1. If $B(t)$ is a BM, then what is the transition density of $a B(t/b)$ for any two constants $a$ and $b$.
2. For any constant $s > 0$, show that $\frac{1}{\sqrt{s}} B(s t)$ is a BM by showing that it satisfies all the requirements of a Brownian motion. Note: This shows BM is self similar. If you scale time and space appropriately (think of this as zooming into the BM trajectory), BM looks the same.
3. We saw the law of large numbers for BM. $\lim_{t \to \infty} \frac{B(t)}{t} = 0$ First use BM scaling to show that $W(t) = t B \left( \frac{1}{t} \right)$ is a BM. Give an alternate proof of the law of large numbers for $W(t)$
4. We saw that $\Prob( B_s = 0 \text{ for some } s \in [1,t] ) = 1 - \frac{2}{\pi} \arctan \left( \frac{1}{\sqrt{t - 1}} \right)$ Use Brownian scaling to find an expression for $\Prob \left( B_s = 0 \text{ for some } s \in [\frac{k-1}{n},\frac{k}{n}] \right)$ Which proof did this formula appear in?

Question 3

Show that $B^2_t -t$ is a Martingale using the Markov property of Brownian motion. Suppose a $B(0) = x$ on the interval $[0,a]$ where $0$ and $a$ are absorbing boundries. Let $T$ be the absorption time. Use the stopping theorem to find $\E[ T] $ and $\Prob( B(T) = 0)$. Justify all your steps and the use of the stopping theorem.

Question 4

Let $B(t) = ( B_1(t), \ldots, B_n(t))$ be a vector of independent one dimensional BMs. $u(x,t) = \E_x[ f(B(t) ]$ where $f \colon \R^d \to \R$ is a smooth function, and $\E_x$ denotes the expectation. Show $\frac{\partial}{\partial t} u(x,t) = \sum_{i = 1}^d \frac{\partial^2}{\partial x^2_i} u(x,t)$ using Taylor’s theorem.

Question 5

Multidimensional Gaussians. Let $Z = (Z_1,\ldots,Z_n)$ be $n$ iid Gaussian random variables.

1. Show that their joint density function is given by $p(z_1,\ldots,z_n) = \frac{1}{ \left( 2\pi \right)^{d/2} } \exp\left( - \frac12 \sum_{i=1}^n z_i^2 \right)$
2. Consider the random vector $Y = A Z$, where $A$ is a symmetric matrix. Show that the joint density function of $Y$ is given by $p(y_1,\ldots,y_n) = \frac{\det(A^{-1})}{ \left( 2\pi \right)^{d/2} } \exp \left(- \frac12 \sum_{i=1}^n (\vec{y}^T A^{-2} \vec{y} ) \right)$ where $\vec{y}^T$ is a the transpose of the column vector $\vec{y} = (y_1,\ldots,y_n)$. We say that such a random vector $Y$ is jointly normal. *Hints: you will need to use a multidimensional change of variables formula. Also use the fact that $A^T = A$. Sometimes, it’s useful for me to write the $i^{th}$ component of $\vec{y}$ as $\vec{y}i = A{ij} \vec{z}_j$ where the repeated index $j$ on the right hand size indicates that it’s being summed over (Einstein’s summation notation).
3. The covariance matrix of a vector $Z = (Z_1,\ldots,Z_n)$ has entries $\operatorname{Cov}(Z_i, Z_j) = \E[ Z_i Z_j ] - \E[ Z_i ] \E[ Z_j ]$ What is the covariance matrix of the vector $Y$ defined in the previous part? Hint: use the independence of $Z$ from part $1$ and $Y = AZ$.
4. What is the covariance matrix of the vector $Y = B(t_1),\ldots,B(t_n)$, where $B$ is a Brownian motion and $0 < t_1 \cdots < t_n$. What is the joint density function of $Z = { B(t_{i+1}) - B(t_{i}) }_{i=1}^{d-1}$? Is $Y$ a jointly normal random variable?
5. Do problem 8.6 now.

Question 6

Can you have a discontinuous BM with the right distributions? Let $U$ be a uniform random variable on $[0,1]$ and let it be independent of a standard BM $B(t)$. Define $X(t) = \begin{cases} B(t) & t \neq U\\ -10 & t = U \end{cases}$ Show that $X(0) = 0$ with probability $1$ and show that for any fixed times $0 < t_1 \cdots < t_n$ $( X(t_2) - X(t_1), X(t_3) - X(t_2), \ldots)$ are independent and jointly Gaussian with the same density function as Brownian motion. Hint What is the probability that $U = t_i$ for some $i = 1,\ldots,n$?

Question 7

Do problems 8.1, 8.3 and 8.4

Question 8

Do problems 8.10, 8.11, 8.12 and 8.15

HW 2

Due Feb 27.

Problem 1

Do problem 1.7, this will be useful later

Problem 2 (sigma algebras)

A $\sigma$ algebra $\mathcal{F}$ is a collection of subsets of a space $\W$ that is closed under the countably many unions, intersection and complements. It also contains the empty- or null-set $\phi$ and the entire space $\W$ itself. That’s all there is to it.

A $\sigma$-algebra generated by a random variable $X$ ($\sigma(X)$) contains all sets of the form ${X \leq a}$.

1. Show that $\sigma(X)$ contains sets of the form ${ X > a }$.
2. What about ${ X = \infty }$? Hint Can you write this as a intersection of a countable number of sets?
3. If $Y$ is independent of $X$, and $E$ is an event (set) in $\sigma(X)$, what can we say about $\Prob( \{ Y \leq a \} \cap E)$
4. $Y$ is “determined by” or “measurable” with respect to some $\sigma$-algebra $\sigma(X)$ if events of the form ${ Y \leq a } \in \sigma(X)$. In other words, all the information about $Y$ is contained in the $\sigma(X)$. If $Y$ is independent of $\sigma(X)$, can ${ Y \leq a} \in \sigma(X)$ for any $a$?

Let $Y$ be independent of mean-zero random variables $X_1,\ldots$, and define $Z_i = Y + X_i$ Let $\mathcal{F}_n$ be the $\sigma$-algebra generated by the random variables $Z_1,\ldots,Z_n$.

1. Is $Y$ measurable with respect to $\sigma(Z_1,\ldots,Z_n) = \mathcal{F}_n$?
2. What happens to $\lim_{n \to \infty} n^{-1} \sum_{i=1}^n Z_i$
3. Let $\mathcal{F}\infty = \sigma(X_1,X_2,\ldots)$. Is $Y$ $\mathcal{F}\infty$ measurable?

Problem 3 (example 2 on page 113)

Redo the example, and fill in the details.

1. Show in particular that $\E[

   M_T

   ] < \infty$

2. Show that $\rho^n (N^2 + n) \to 0$
3. Show that the time to absorption in Gambler’s ruin is given by $\E[T] = a(N-a)$.

Problem 4 (biased gambler’s ruin)

In gambler’s ruin with $p = 1/2$, remind yourself how $\Prob(X_T = N)$ and $\E[T]$ were found in chapter $1$. Compare with the martingale methods we’ve developed to handle this.

• Do problem 5.7 and 5.8 from the text book.

Problem 5

Do problems 5.3, 5.4 and 5.6 from the textbook. Please submit polya’s urn code with the problem.

Problem 6

Do 5.11 and 5.13

HW 1

Due Fri, Feb 3.

Problem 1

Implement an algorithm to find $v(x)$ in the cases when

1. There is only a payoff function
2. There is a payoff function and a cost to play
3. There is a payoff function f, a cost g to play and a discounting factor $\alpha$.

Do problems $4.1$, $4.2$, $4.3$ and $4.4$ from the textbook. In each case, compare your theoretical answer to the numerical answer.

Draw pictures of $v(x)$ in all problems, and compare it with $f(x)$. Use your favorite programming language to do this.

Submit your code.

I will only do theoretical solutions for 4.1 and 4.2. For 4.3 and 4.4 I will just implement the algorithm.

Solution We have $\begin{matrix} S = 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & \\ f = 0 & 2 & 4 & 3 & 10 & 0 & 6 & 4 & 3 & 3 & 0 & \end{matrix}$ We will updated the STOP and GO sets after a few computations. It’s clear at the outset that $\begin{align} STOP & = 0 \quad 4 \quad 10\\ GO & = \end{align}$ Using $v(x) \geq Pv(x)$, we get the following observations:

1. $v(4) = 10$ and hence it must be in the STOP set.
2. $v(3) \geq Pv(3) = (10+4)/2 = 7 > 3$. Hence it must be in the GO set.
3. $v(2) \geq (7 + 2)/2 = 4.5 > 4$. GO.
4. $v(1) \geq v(2)/2 = 4.5/2 = 2.2.5 > 2$. GO.
5. $v(5) \geq (10 + 6)/2 = 8$. Obviously GO.
6. $v(6) \geq (v(5) + 4)/2 = \left( 8 + 4 \right)/2 = 6$. unclear at this point.
7. $v(7) \geq (v(6) + v(8))/2 = (6+3)/2 = 4.5 > 3 $. GO.
8. $v(8) \geq ( v(7) + v(9) ) /2 \geq (4.5 + 3)/2 = 3.25 > 3$. GO.
9. $v(9) \geq v(8)/2$. Unclear.
10. Recomputing $v(6) \geq ( v(5) + v(7))/2 \geq (8 + 4.5)/2 = 6.25 > 6$. GO.

At this stage, we have $\begin{align} STOP & = 0 \quad 4 \quad 10 \\ GO & = 3 \quad 2 \quad 1 \quad 5 \quad 7 \quad 8 \quad 6 \end{align}$ It’s only sort of unclear whether one should have $9$ in the STOP set or the GO set. Suppose $9$ were in the GO set, we would have for $x \in { 5,6,7,8,9 }$ $\begin{align} v(x) & = \E [ f(X_T) | X_0 = x]\\ & = 10 \Prob (X_T = 4 | X_0 = x) + 0 \Prob (X_T = 10 | X_0 = x) \\ & = 10 \Prob (X_T = 4 | X_0 = x) \\ & = 10 \frac{10 - x}{6} \end{align}$ Doing a similar computation with $9$ in the STOP set gives for $x \in {5,6,7,8}$ $v(x) = 10 \frac{9-x}{5} + 3 \left(1- \frac{9-x}{5} \right)$ Both these functions start at $10$ at $x=4$ and decrease linearly. So it’s enough to test them at $1$ value, say $x=9$. It’s easily seen that it’s better to have $9$ in the STOP set.

For the states $x \in { 0,1,2,3,4 }$ we get $v(x) = 10 \frac{x}{4}$ To summarize, we get $\begin{matrix} S = 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ f = 0 & 2 & 4 & 3 & 10 & 0 & 6 & 4 & 3 & 3 & 0 \\ v(x) = 0 & 2.5 & 5 & 7.5 & 10 & 8.6 & 7.2 & 5.8 & 4.4 & 3.0 & 0 \end{matrix}$

Solution 4.2

Here we have two dice rolls $A + B$, that have mean $\E[ A + B ] = 2 \sum_{i = 1 } \frac{i}{6} = 7$ But here, if $A + B = 7$, the payoff is $0$. So let’s compute the average winnings if we roll once and then stop. $\begin{align} u(x) & = \E [ f(X_T) | X_0 = x ]\\ & = \E [ (A + B) 1_{A + B \neq 7} ] \\ & = \E [ A + B ] - \E [ A + B 1_{A + B \neq 7} ] = 7 - 7 \Prob(A + B = 7) \\ & = 7 - \frac{7}{6} = 5 \frac{5}{6} \end{align}$ Again, the optimal strategy is clear: $v(x) = \max \{ f(x), Pv(x) \}$ Since $Pv(x) = u = 5 \frac{5}{6}$, it’s clear that $v(x) \geq \begin{cases} 5 \frac{5}{6} & x \leq 5\\ x & x \in \{ 6,8,9,10,11,12 \}\\ 0 & x = 7 \end{cases}$ We need to write down the probabilities of different winnings: $\begin{matrix} 2& 3& 4& 5& 6& 7& 8& 9& 10 & 11 & 12 \\ \frac{1}{36}& \frac{2}{36}& \frac{3}{36}& \frac{4}{36}& \frac{5}{36}& \frac{6}{36}& \frac{5}{36}& \frac{4}{36}& \frac{3}{36}& \frac{2}{36}& \frac{1}{36} \end{matrix}$ Then the expected winnings are $\begin{aligned} \E[ v(X) ] & \geq \sum_{i=2}^{12} v(i) \Prob(A+B = i)\\ & = \frac{35}{6} \frac{10}{36} + \sum^{12}_{i=6} i \Prob(A+B=i) - 7 \Prob(A + B = 7) \\ & = 6.34 \end{aligned}$ This means that $6$ is in the GO set too! Then, we must have $v(x) \geq \begin{cases} 6.34 & x \leq 6\\ x & x \in \{ 8,9,10,11,12 \}\\ 0 & x = 7 \end{cases}$ Could $8$ be in the GO set too? Note that if for the remaining states ${8,9,10,11,12}$, if $x \in STOP$, then it must be true that $x + 1 \in STOP$ too. So let’s start by assuming that $8$ is in the GO set. In this case, $v(x) = \begin{cases} u & x \leq 6 \OR x = 8 \\ x & x \in \{ 9,10,11,12 \}\\ 0 & x = 7 \end{cases}$ Then, we must have that $Pv(x) = u$ for $x = 2,\ldots,6,8$ (using the characterization that $v(x) = \max(Pv(x),f(x))$). Then, computing $\begin{align} Pv(x) & = u \Prob(X+Y = 2,\ldots,6,8) + \sum_{i=9}^12 i \Prob(X+Y=i)\\ & = u \frac{5}{9} + \frac{100}{36} \\ & = u \end{align}$ Solving for $u$ gives $u = 5$. This certainly cannot be true. So assuming $8$ is in the STOP set, we get $v(x) = \begin{cases} u & x \leq 6 \\ x & x \in \{ 8, 9,10,11,12 \}\\ 0 & x = 7 \end{cases}$ Using $Pv(x) = u$ for $x \leq 6$ again gives $u = 20/3 \approx 6.67$. One simply verifies using $v(x) = \max(Pv(x),f(x))$ that this is the correct answer.

Problem 4.3 and 4.4 I’ll simply do these using computer simulation.

4.3

(a)

$\begin{matrix} S = 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ v(x) = 0 & 2 & 4 & 6.25 & 10 & 7.25 & 6.0 & 4 & 3 & 3 & 0 \end{matrix}$

(b)

$\begin{matrix} S = 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ v(x) = 0 & 2 & 4.14 & 6.72 & 10 & 7.6 & 6.0 & 4.55 & 3.59 & 3 & 0 \end{matrix}$

(c)

$\begin{matrix} S = 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ v(x) = 0 & 2 & 4 & 5.9 & 10 & 6.85 & 6.0 & 4 & 3 & 3 & 0 \end{matrix}$

4.4

(a)

$\begin{matrix} S = 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ v(x) = 3.94 & 3.94 & 4 & 5 & 6 & 0 & 8 & 9 & 10 & 11 & 12 \end{matrix}$

(b)

$\begin{matrix} S = 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ v(x) = 4.87 & 4.87 & 4.87 & 5 & 6 & 0 & 8 & 9 & 10 & 11 & 12 \end{matrix}$

(c)

$\begin{matrix} S = 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ v(x) = 2.68 & 3 & 4 & 5 & 6 & 0 & 8 & 9 & 10 & 11 & 12 \end{matrix}$

Problem 2

Do 4.8 and 4.10. Simulate 4.8 first as instructed.

Solution

4.8

Let us divide the payout by 100 so that you get paid $1,2,\ldots,11$ each time you play. We will view this as a Markov process on the non-negative integers. $0$ or bankruptcy is viewed as an absorbing state. Suppose the amount of money you hold right now is $x$; then after the next turn, you go to $x + i$ for $i=1,\ldots,11$ with probability $1/12$ and you go bankrupt with probability $0$. Clearly $p(x,y) = \begin{cases} \frac{1}{12} & y = x + i, \quad i=1,\ldots,11\\ \frac{1}{12} & y = 0 \end{cases}$ If you choose to stop right now, then you get to leave with whatever you have; i.e., $f(x) = x$. As before $v(x) = \max\{Pv(x), f(x)\} = \max\{ Pv(x), x\}$ Clearly, there must be an $x_0$ that is the last time you’re in the GO set; then, $x_0 + 1$ must be in the CONTINUE set. If you stop at $x_0 + 1$, you’ll certainly stop at $x_0 + 2$. At this $x_0$, we must have $\begin{aligned} x_0 & \leq Pv(x) \\ & = \sum_{i=1}^{11} p(x,x + i) v(x_0 + i) + 0 \frac{1}{12} \\ & = \sum_{i=1}^{11} \frac{1}{12} (x_0 + i) \\ & = \frac{11}{12} x_0 + \frac{11}{2} \end{aligned}$ Solving this shows that $x_0$ = 66. Clearly, $x_0 + 1 > Pv(x_0 + 1)$. So we know our optimal strategy. We keep rolling until we hit $66$ and then stop. If we go bankrupt, “too bad, so sad, next contestant please”.

Now you somehow have to figure out the solution to $v(x) = \E[ f(X_T) | X_0 = x]$ where $T$ is the first time you reach the stopping set $x_0 \geq 66$ starting at $X$. Note that we must have $v(65) = Pv(65) = \sum_{i=1}^{11} v(65 + i) \frac{1}{12} = 65 \frac{11}{12} + \frac{11}{2} = 65.0833.$ And the same for $v(x) = Pv(x)$, $x \leq 65$. This is shown in the accompanying python code. What I do is to solve for $v(x)$ for $x < 66$ using $v(x) = Pv(x) = \sum_{i=1}^{11} v(x + i) p(i)$ For $x = 65$, we have $v(65) = Pv(65) = \sum_{i=1}^{11} v(65 + i) p(i)$ Note that we know $v(65 + i) = 65 + i$ for $i > 0$! Then we iteratively solve for $v(64)$ $v(63)$ are so on.

Can anyone find an analytic solution for this? It should be possible.

If we started with no money, then we expect to make $\E[ v(X_1) ] = \sum_{i=1}^{11} v(i) \frac{1}{12} = 30.46$ on average. There is another way to figure out this threshold. Suppose we’re allowed to keep the money we make until we hit the threshold. Let $T$ be the number of rolls until we hit the first $12$. Clear $T \sim \Geometric(1/12)$; i.e., $\Prob(T = k) = (1-p)^k p \quad k = 0,$ Then the payout is $\begin{align} \E [ \sum^{T}_{i=0} X_i ] & = \sum^{\infty}_{k=0} \E[ \sum^{k}_{i=1} X_i | T = k ] \Prob(T = k) \\ & = \sum^{\infty}_{k=0} k \E[ X_i | T = k ] (1-p)^k p \end{align}$ After figuring out that $\E[ X_i | T = k ] = 6$ (Hint: compute the conditional distribution of $X_i$ given that it doesn’t take the value $12$), we see that the payout is $6 \E[T] = 6 \frac{(1-1/2)}{1/12} = 66$ If we used the prophet function instead, this is the payout we’d receive on average!

4.10

Let $T$ be the number of rolls before the first $6$ is rolled in the die game. Clearly $\Prob( T = k ) = (1-p)^{k} p \quad k=0,1,\ldots,$ where $p = 1/6$. It’s a geometric random variable.

Now, the payoff function is clearly $\begin{align} u & = \E[ \max_{i=1,\ldots,T-1} X_i ] \\ & = \sum_{k=1}^{\infty} \E[ \max_{1\leq i \leq k - 1} X_i | T = k ] \Prob(T = k) \\ \end{align}$ This is because we stop right before the first time a $6$ is rolled. To compute the conditional expectation, let us compute $\begin{align} \Prob( \max_{1\leq i \leq k - 1} X_i \leq j | T = k ) & = \frac{\Prob( X_i \leq j , T = k, i = 1,\ldots,k-1 )}{\Prob(T = k)}\\ & = \frac{(j/6)^{k-1} p}{(1-p)^{k-1} p}\\ & = \left( \frac{j}{5} \right)^{k-1}. \end{align}$ Here we’ve used the independence of the die rolls. $\begin{align} u & = \sum_{k=1}^{\infty} \E[ \max_{1\leq i \leq k - 1} X_i | T = k ] \Prob(T = k) \\ & = \sum_{k=1}^{\infty} \sum_{j=1}^5 j \left( \left( \frac{j}{5} \right)^{k} - \left( \frac{j-1}{5} \right)^{k} \right) (1-p)^{k} p\\ & = \sum_{j=1}^5 p j \frac{7j - j^2 - (6j - 6 - j^2 + j)}{(6-j)(7-j)}\\ & = \sum_{j=1}^5 j \frac{j}{(6-j)(7-j)}\\ & = 3.55 \end{align}$ Recall that $u = 3$ in the original dice game. See the first part of chapter 3 of Lawler’s book for a discussion of the dice game.

4.10 (b)

This is a messier problem, but still entertaining. Recall $\begin{matrix} S = 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ f = 0 & 2 & 4 & 3 & 10 & 0 & 6 & 4 & 3 & 3 & 0 \end{matrix}$ Let’s start at $1$. You can get absorbed into state 0 or 4, since we know that we must stop when we get tp $4$. Then $v(1) = \begin{cases} 0 & \frac{1}{2} & \text{step left}\\ 4 & \frac{1}{4} & \text{step right, the absorbed into 0}\\ 10 & \frac{1}{4} & \text{step right, the absorbed into 4} \end{cases}$ $v(2) = \begin{cases} 4 & \frac{1}{2} & \text{absorbed into 0}\\ 10 & \frac{1}{4} & \text{absorbed into 4} \end{cases}$ $v(3) = \begin{cases} 4 & \frac{1}{4} & \text{step left, the absorbed into 0}\\ 10 & \frac{3}{4} & \text{step right, the absorbed into 4} \end{cases}$ $v(4) = 10$ $v(5) = \begin{cases} 6 & \frac{1}{6} & \text{absorbed in to 10}\\ 10 & \frac{5}{6} & \text{absorbed into 4} \end{cases}$ $v(6) = \begin{cases} 6 & \frac{4}{6} & \text{absorbed in to 10}\\ 10 & \frac{2}{6} & \text{absorbed into 4} \end{cases}$ $v(7) = \begin{cases} 4 & \frac{1}{4} & \text{hit 10 before 6}\\ 6 & \frac{1}{4} & \text{otherwise}\\ 10 & \frac{1}{2} & \text{hit 4 before 10} \end{cases}$ $v(8) = \begin{cases} 10 & \frac{2}{6} & \text{hit 4 before 10}\\ 6 & \frac{1}{6} & \text{6 before 10, then 10 before 4} \\ 4 & \frac{1}{6} & \text{7 before 10, then 10 before 6}\\ 3 & \frac{2}{6} & \text{7 before 10, then 10 before 6} \end{cases}$ $v(9) = \begin{cases} 10 & \frac{1}{6} & \text{4 before 10}\\ 6 & \frac{1}{4} \frac{2}{6} & \text{6 before 10, then 10 before 4}\\ 4 & \frac{1}{3} \frac{1}{4} & \text{7 before 10, then 10 before 6}\\ 3 & \frac{4}{6} \end{cases}$ We’ve abused notation a little bit, and treated $v(\cdot)$ as a random variable above. But you guys know what I mean, right? Notice that for example $v(9) = \frac{20}{12} + \frac{6}{12} \frac{4}{12} + \frac{24}{12} = \frac{54}{12} = 4$ In problem 4.1, $9$ was in the stop set, and therefore, $\E[v(9)] = 3$. Therefore the “prophet” function obviously does better. The other expectations can be calculated, of course. To summarize $\begin{matrix} S = 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ v(x) = 0 & 3.5 & 4.5 & 8.5 & 10 & 9.33 & 7.33 & 7.55 & 6.0 & 4.0 & 0 \end{matrix}$

Problem 3

Show that if $Y$ is independent of $X_1,X_2,\ldots,X_n$, then $\E[ Y | X_1,X_2,\ldots,X_n ] = \E[Y]$

Solution We know that the definition of conditional expectation is that for any set $A$ that depends only on the variables $X_1,\ldots,X_n$, $\begin{align} \E[ \E[ Y | X_1,X_2,\ldots,X_n ] 1_A ] & = \E[ Y 1_A ]\\ & = \E[ Y ] \E[ 1_A ]\\ & = \E[ Y ] \Prob(A) \end{align}$ since $Y$ and $1_A(X_1,\ldots,X_n)$ are independent. Suppose there is a set $B$ and some $\e > 0$ such that $\E[Y | X_1,X_2,\ldots,X_n ] - \E[ Y ] > \e \quad (X_1,\ldots,X_n) \in B$ Then, using the above, we have $\E[ \E[Y | X_1,X_2,\ldots,X_n ] 1_B ] > \E[ (\E[ Y ] + \e) 1_B ] = (\E[ Y ] + \e) \Prob(B)$ Notice that $B$ depends only on the $X_i$. This is a contradiction and shows that $B$ must have measure $0$ for all $\e$. Similarly we consider the set where $\E[ Y| X_1,X_2,\ldots,X_n ] < \E[ Y]$ and show that it has probability $0$ too. This proves the statement.

Problem 4

Show that $v(x)$ must be concave if you have a simple random walk with absorbing boundaries. What happens when you have reflecting boundaries?

Solution See my handwritten notes here

Problem 5

Complete the proof of the fact that if $u_i(x)$ are superharmonic, then so is $u(x) = \inf_i u_i(x)$.

Solution We’ve done this several times in class now.