Math 5050 Quizzes


Quiz 5

A pdf of Quiz 5

Quiz 4

Quiz 4

Quiz 3

Problem 1

Stopping rules. Consider $v(x)$, the optimal stopping problem again.

  1. Let $T$ be the rule that you stop after one step. Is this a valid stopping rule? Justify.
  2. Let $T$ and $U$ be two valid stopping rules. Is $T + U$ a valid stopping rule? Justify.
  3. Let $T$ be the rule that you stop if your next step is into an absorbing state. Is this a valid stopping rule? Justify.

Problem 2

If $T$ is a random variable taking values in $(0,\infty]$, does the following limit exist? If it exists, what is its value?

Problem 3

Consider the biased random walk on ${0,\ldots,N}$ with $p < 1/2$. Assuming that is a martingale, compute where $T = \inf { n > 0 \colon S_n = 0 \OR N }$. Hint: justify the use of the optional sampling theorem here. <div class=pagebreak-before> </div>

Quiz 2

Problem 1

Consider a simple random walk on ${0,1,\ldots}$. This is problem 4.9. $0$ is an absorbing boundary and $f(x) = x^2$ is the payoff.

  • Show that if you do not stop at any $X_n \neq 0$ and continue for one more step, [ \E[ f(X_{n+1} | X_n ] > f(X_n) ] Why does this tell you that you should continue at every non-zero $x$?
  • Write down a generic recursion equation for $v(x)$. Clearly $v(0) = 0$. What is the general solution to this equation? Hint you’ve seen this in 5040 in one of the earlier chapters.
  • We wrote down a theorem that characterizes $v(x)$, what does it say in this situation? What does superharmonic mean for the simple random walk with an absorbing boundary?
  • Now, $X_n$ is recurrent to the origin, and so absorption happens with probability $1$. The optimal strategy tells us to never stop, but this means we will be absorbed into the origin and get $0$ payoff! What’s wrong here?

Problem 2

Let $X_1,X_2,\ldots$ be iid random variables. Consider $M_n = X_1 \cdot X_2 \cdots X_n$ and the filtration $\mathcal{F}_n = \sigma(X_1,\ldots,X_n)$. Under what conditions on $\E[X_i]$ is $M_n$ a martingale?

Problem 3

Consider $S_n = \sum_{i=1}^n X_i$. Compute $\E[ S_n^3 \mathcal{F}_m]$ for $m < n$.

<div class=pagebreak-before> </div>

Quiz 1

Problem 1: optimal stopping of markov chains

Suppose $v(x)$ is the value function of the optimal strategy $T$ with STOP and CONTINUE sets. Is it possible to have

  1. $v(x) > Pv(x)$ on the CONTINUE set? Why or why not?

  2. Is it possible to have $v(x) < Pv(x)$ on the CONTINUE set? Why or why not?

Problem 2

If $P$ is an irreducible Markov chain, what is $v(x)$? Assume some general payout function $f(x)$ on some state space $S$.

Problem 3

Suppose ${u_i}_{i=0}^{\infty}$ is a collection of super harmonic function satisfying $u_i(x) \geq P u_i(x)$ and $u_i(x) \geq C$ for all $i = 0,1,\ldots$ and some constant $C$. Show that $u(x)$ is superharmonic.

Problem 4

Define the state space $S$ and payout function $f$ as follows. Suppose $P$ is a simple random walk with absorbing barriers at $10$ and $0$.

Find the STOP and CONTINUE sets, and justify your answer.