Dice Game with 1 die and Payoff Function Imagine a dice game where you may repeatedly roll a die until you either decide to stop, or roll a 1, with the following payoff function (where k is the number on the die),
$f(k) = 0$ when $k=1$
$f(k) = k^2$ when $k>1$
So if on your nth roll you land $1$, you go home with nothing. If on your $n$th roll you land a $4$, you get $16$ USD, and can either decide to roll again or go home with the $16$ USD. 
My question: how should I set up the optimal stopping problem, after I have written down the transition matrix (making this into a Markov Process with each state space corresponding to the number I land)? Any hints would be appreciated, thank you
 A: Suppose you have rolled a $4$, which gives a payout of $16$, should you roll again?
The probability of getting a $j \in \{4,5,6\}$ later in the game is rolling  $n$ times a $2$ or $3$ and then a $j$ for any $n \in \mathbb{N}$, which gives
$$\mathbb{P}(\textrm{getting a }j)=\sum_{n=0}^\infty \frac{1}{3^n} \frac{1}{6}= \frac{1}{6} \frac{3}{2} = \frac{1}{4}.$$
So you have a $\frac{1}{4}$ chance of getting a lower payoff, and a $\frac{3}{4}$ chance of getting a better or equal payoff, which gives a payoff of 
$$ \frac{1}{4} ( 16+25+36) = \frac{77}{4} > 16.$$
So it seems like you should continue rolling.
If you get a $5$, at the same way you get by continuing to roll an average payoff of
$$ \frac{1}{3}(25+36) = \frac{61}{3} < 25.$$
So if you get a $5$, you should stop. 
Thus the optimal strategy is to keep rolling till you have at least rolled a $5$, and then stop.
A: Obviously, if you roll a $6$ at any time, you should stop, with value $\$36$.
If you roll a $5$, you can either stop (with value $\$25$), or continue until you roll either a $1$ or a $6$ (both equally likely).  If you terminate on a $1$ (with probability $1/2$), you win nothing; if you terminate on a $6$ (with probability $1/2$), you win $\$36$.  The value of continuing is therefore $36/2 = \$18$.  Since this is less than $\$25$, you should stop on a $5$.
If you roll a $4$, you can either stop (with value $\$16$), or continue until you roll a $1$, a $5$, or a $6$ (all equally likely).  The value of continuing, reasoning analogously with the previous paragraph, is $25/3+36/3 = \$20.33+$.  Since this is greater than $16$, you should continue on a $4$.
Similar reasoning shows that you should continue on a $2$ or a $3$, also.  (It may be of interest to note that the value of rolling a $4$ should be counted as $61/3$, not $16$, though it does not affect the decision.)
