From: Prophet Steering on 28 Mar 2010 01:23 In Section 3, this problem is generalized to tbe one where the gambler does not persist in the very largest, but rather feels satisfaction provided that his fortune upon stopping is within $m$ units from the largest. More specifically, when the allowance measure is $m$ $($ $m$ is a given positive integer), the gambler seeks an optimal stopping time $\sigma_{m}^{*}$ such that $P_{r} \{X_{\sigma_{m}^{*}}\geq 0\leq n\leq \mathrm{m}\mathrm{a} \mathrm{x}TX_{n}(m1)X_{0}=i\}=\max_{\sigma\in C}P_{r}\{x_{\sigma} \geq 0\leq n\leq T\mathrm{m}\mathrm{a}\mathrm{x}X_{n}(m1)X_{0}=i\} $ . $(1.3)$ Obviously when $m=1$ , this problem is reduced to the one considered in Section 2. It can be shown that there exists an optimal stopping time $\sigma_{m}^{*} $ of the following form; $\sigma_{m}^{*}=\min\{n:X_{n}=0\leq j\leq n\mathrm{m}\mathrm{a} \mathrm{x}X_{j}(m1)$ , $X_{n}<k_{m}^{*}\}$ , where $k_{m}^{*}$ is a positive integer defined as $k_{m}^{*}= \min\{k$ : $\frac{1\theta^{k}}{1\theta^{Nm+1}}\geq \frac{\theta^{k}(1\theta^{m})}{1\theta^{k+m}}\}$ . 2 Stopping on the largest Suppose that we enter a casino having an initial fortune of $x$ units and bet one unit each time. Then we either win one unit with probability $p$ or lose one unit with probability $q=1p$, where $0<p<1$. The gambling process $\{X_{n};n\geq 0\}$ , a Markov chain, continues until it reaches its absorbing states $0$ or $N,$ $\mathrm{b} \dot{\mathrm{u}}\mathrm{t}$ we can stop the process before absorption, if we like. If we decide to stop at time $n$ , then we are said to succeed if $X_{n}= \max_{0}\leq j\leq TXj$ . The objective of the problem is to find a stopping policy that will maximize the probability of success. Suppose that we have observed the values of $X_{0},$ $X_{1},$ $\cdots $ , $X_{n}$ . Then serious decision of either stop or continue takes place at time $n$ when $X_{n}$ is the maximum value observed so far, that is, $X_{n}= \max(x_{0}, x_{1,n}\ldots, x)$ . This decision epoch is simply referred to as state $x$ if $X_{n}=x$ , because, as a bit of consideration shows, the decision depends neither on the values of $X_{0},$ $X_{1},$ $\cdots$ , $X_{n1}$ nor on the number of plays already made. Let $v(x)$ be the probability of success starting from state $x$ , and let $s(x)$ and $c(x)$ be respectively the probability of success when we stop in state $x$ and we continue gambling in an optimal manner in state $x$ ; then from the principle of optimality. $v(x)= \max\{S(X), C(X)\}$ , $0<x<N$ (2.1) where $s(x)=1P_{x}(1, X)$ (2.2) $c(x)=pv(x+1)+q(1s(x1))v(x)$ , $0<x<N$ (2.3) with the boundary condition $v(\mathrm{O})=v(N)=1$ . (2.3) is immediate from (1.2). (2.4) follows because the next possible state visited (after leaving state $x $ ) is either $x+1$ or $x$ depending on whether we win one unit at the next play or lose one unit at the next 150 play but attain state $x$ again before going broke.To solve the optimality equation $(2.2)$ (2.4), we invoke the result of positive dynamic programming (see, for detail, chapter IV of $\mathrm{R}\mathrm{o}\mathrm{s}\mathrm{S}[2])$ . The main result (Theorem 1.2, p.75 of Ross) is that if the problem fits the framework of the positive dynamic programming, then a given stationary policy is optimal $\mathrm{i}\mathrm{f}_{\ell}\mathrm{i}\mathrm{t}\mathrm{S}$ value function satisfies the optimality equation. This gives us a method of checking whether or not a guessed policy can be optimal and is particularly useful in cases in which there exists an obvious optimal policy. Our problem in fact fits the framework of positive dynamic programming with the state being the gamblers fortune, since if we suppose that a reward of 1 is earned if we attain the largest over all and all other rewards are zero, then the expected total reward equals the probability of success. Theorem 2.1 Let $f$ be a stationary policy which, when the decision process is in state $x$ , chooses to stop if and only if $x<x^{*}$ , where $x^{*}= \min\{x$ : $\frac{1\theta^{x}}{1\theta^{N}}\geq \frac{\theta^{x}\theta^{x+1}}{1\theta^{x+1}}\}$ . (2.4) Then $f$ is optimal. Proof Let $v_{f}(x)$ denote the probability of success starting from state $x$ when policy $f$ is employed. Once the decision process leaves state $x(\geq x^{*})$ , it never stops until absorption takes place under $f$ . Thus we soon obtain $v_{f}(x)=\{$ $s(x)$ , $\mathrm{i}\mathrm{f}x<x^{*}$ $P_{x}(Nx, x)$ , $\mathrm{i}\mathrm{f}x\geq x^{*}$ , (2.5) and it is easy to check that $s(x)$ is decreasing in $x$ , while $P_{x} (Nx, x)$ is increasing in $x$ and that $x^{*}$ can be described as $x^{*}= \min\{x : s(x)\leq P_{x}(Nx, x)\}$ . Therefore, to prove $f$ is optimal, it suffices to show that, from $(2.2)(2.4),$ $v_{f}(x)$ given in (2.5) satisfies $v_{f}(x)= \max\{S(X),pvf(x+1)+q(1S(x1))vf(x)\}$ , $0<x<N$. (2.6) We now show this distinguishing among three cases. Case(i): $x<x^{*}1$ Since $v_{f}(x)=s(x)$ , to show the validity of (2.6), it suffices to show that $v_{f}(x)\geq pv_{f}(x+1)+q(1S(X1))v_{f}(X)$ , or $s(x)\geq ps(X+1)+q(1S(_{X1))_{S(}}X)$ , 151 or equivalently $\{s(X)S(X+1)\}+\theta s(x+1)s(x)\geq 0$ , which is immediate since $s(x)$ is nonnegative and decreasing in $x $ . Case(ii): $x\geq x^{*}$ Since $v_{f}(x)=P_{x}(Nx, x)\geq s(x)$ , it suffices to show that $v_{f}(x)\geq pv_{f}(x+1)+q(1S(x1))vf(X)$ , or equivalently $P_{x}(NX, x)\geq pP_{x+1}(NX1, x+1)+qP_{x1}(1, x+1)P_{x}(Nx, x) $ , which in fact holds with equality, because. straigh.$\mathrm{t} \mathrm{f}_{0}\mathrm{r}\mathrm{W}\mathrm{a}\mathrm{r}\mathrm{d} \mathrm{c}\mathrm{a}1_{\mathrm{C}\mathrm{u}}1\mathrm{a}\mathrm{t} \mathrm{i}\mathrm{o}\mathrm{n}'$ . from (.1.2) leads to the following identity; $P_{x}(Nx, x)=pP_{x+1}(Nx1, X+1)+qP_{x1}(1, X1)P(xNX, x)$ . (2.7) It is easy to interpret this identity probabilistically by conditioning on the result of the first play after leaving state $x$ . Case(iii): $x=x^{*}1$ Since $v_{f}(x^{*}1)=s(x^{*}1)$ , it suffices to show that $v_{f}(x^{*}1)\geq pv_{f}(x^{*})+q(1S(X*2))v_{f(1}x*)$, or $s(x^{*}1)\geq pP_{x^{*}}(Nx^{*}, x^{*})+qP_{x^{*}2}(1, X^{*}2)s(X^{*}1)$ , or $s(x^{*}1) \geq\frac{pP_{x^{\wedge()}}NXX*,*}{1qP_{x^{*}} 2(1,x^{*}2)}$ , or equivalently from (2.7) $s(x^{*}1)\geq P_{x^{\mathrm{r}}1}(Nx^{*}+1, x^{*}1)$ , which is obvious from the definition of $x^{*}$ . Thus the proof is complete. 3 Stopping on one of $m$ largest In this section, we are concerned with stopping on one of $m$ largest of the gambling process. That is, we wish to find an optimal stopping time $\sigma_{m} ^{*}$ which satisfies (1.3). Suppose that we have observed the values of $X_{0},$ $X_{1}$ ) $\ldots,$ $x_{n}$ . Then serious decision of either stop or continue takes place at time $n$ if $X_{n} \geq \max_{0\leq j\leq}X_{j}n(m1)$ . We denote this state by $(x, i)$ if $X_{n}=x$ and $X_{n}= \max_{0\leq j \leq}nX_{j}(i1),$ $0<x<N$ $m,$ $i=1,2,$ $\ldots,$ $m$ . Our trial is now regarded as successful if we stop at time $n$ and 152 $X_{n} \geq\max_{0\leq j\leq\tau}X_{j}(m1)$.Let $v_{i}(X),$ $1\leq i \leq m$, be the probability of success starting from state $(x, i)$ , and let $s_{i}(x)$ and $c_{i}(x)$ be respectively the probability of successes when we decide to stop and when we decide to continue in an optimal manner in state $(x, i)$ , then from the principle of optimality, $v_{i}(x)= \max\{s_{i}(x), C_{i}(X)\}$ , $1\leq i\leq m$ , $0<x<Nm$ (3.1) where $s_{i}(x)\equiv s(x)=1P_{x}(m,..x)$ $1\leq Ai\leq m$ (3.2) and $c_{1}(x)=pv_{1}(x+1)+qv_{2}(x\mathrm{i})$ (3.3) $c_{i}(x)=pv_{i1}(x+1)+qv_{i+1}(x1)$ , $1<i<m$ (3.4) $c_{m}=pv_{m1}(X+1)+qP_{x1}(1, X1)vm(x)$ . (3.5) Assume that we choose to be continue in state $(x, i),$ $1\leq i<m$ , if $s_{i}(x)=c_{i}(x)$ . Then as the next lemma shows, we never stop in state $(x, i),$ $1\leq i<m$ . Lemma 3.1 For $1\leq i<m$ , $c_{i}(x)\geq s_{i}(X)$ . Proof. Since, from the definition, $c_{i}(x)\geq ps(x+1)+qS(_{X}1)$ , $1\leq i<m$ , to show $c_{i}(x)\geq s_{i}(x)$ , it suffices to show that ps $(_{X+}1)+qs(x1)\geq s(x)$ , or $\frac{1\theta^{x}}{1\theta^{x+m}}\{p\frac{1\theta^{x+1}}{1 \theta^{x+}m+1}+q\frac{1\theta^{x1}}{1\theta^{x}+m1}\}\geq 0$ . (3.6) Because $p=1/(1+\theta),$ $q=\theta/(1+\theta)$ , after a bit of calculation, the lefthand side of (3.6) becomes $\theta^{2x+m}1(\frac{1\theta^{m}}{1\theta})$ .. $\overline{(\frac{1\theta^{x}+m1}{1\theta})(\frac{1\theta^{x+m}}{1 \theta})(\frac{1\theta^{x+}m+1}{1\theta}\mathrm{I}}$ which is obviously nonnegative and proves (3.6). $\mathrm{t}\backslash $ : i. $\cdot$  $\dot{\mathit{9}}$ . .. . .,$\cdot$ $\cdot$ . From Lemma 3.1, we are only concerned with $\mathrm{t}\mathrm{h} \dot{\mathrm{e}}$ optimal decision in state $(x, m).$ The following lemma expresses $c_{m}(x)$ in terms of $v_{m}(.)$ . Lemma 3.2 Define $P=(1\theta^{m1})/(1\theta^{m})$ . Then, for $x \leq N2m$ , 153 $c_{m}(x)$ $=$ $\{p\theta P+qP_{x1}(1, x1)\}vm(x)$ $+p(1 \theta P)\sum^{N}y=x+12m+1P^{yx1}(1P)v_{m}(y)$ $+p(1\theta P)P^{N}x2m1$ . Proof. Let $p(x, y)$ be the transition probability from state $(x, m)$ to state $(y, m),$ $y\geq x$ . Then straightforward calculation yields $p(x, y).$ $=$ $\{$ $qP_{x1}(1, X1)+p[1P_{x+1}(m1,1)]$ , if $y=x$ $pP_{x+1}(m1,1)[\Pi_{i=0}^{yx}2Px+m+i(1, m1)][1P_{y+}m1(1, m1)] $ , if $x<y\leq N2m+1$ $=$ $\{$ $qP_{x1}(1, X1)+p\theta P$, if $y=x$ $p(1\theta P)P^{y}x1(1P)$ , if $x<y\leq N2m+1$ . The remaining probability $1\Sigma_{y=}^{N2}xp(_{X}m+1, y)=p(1\theta P)P^{N}x2m+1$ corresponds to the probability that the gambling process $\{X_{n}\}$ attains its absorbing state $Nm+1$. Thus the proof is complete. We now have the following identity. Lemma 3.3 For $m\geq 1$ and $x\leq N2m$, $P_{x}(Nm+1x, x)$ $=$ $\{p\theta P+qP_{x1}(1, X1)\}P_{x}(Nm+1x, x)$ $+p(1 \theta P)\sum^{N}y=x+1(2m+1P^{y}x11P)P_{y}(Nm+1y, y)$ $+p(1\theta P)P^{N2}xm1$ . Proof. We can prove this by straightforward calculation from (1.2), but this identity is quite intuitive from Lemma 3.2. We are now ready to prove the main result. Theorem 3.4 Let $f$ be a stationary policy which, when the decision process is in state $(x, m)$ , chooses to stop if and only if $x<x^{*}$ , where $x^{*}= \min\{x$ : $\frac{1\theta^{x}}{1\theta^{Nm+1}}\geq \frac{\theta^{x}\theta^{x+m}}{1\theta^{x+m}}\}$ . 154 Then $f$ is optimal. Proof Let $v_{f}(x)$ denote the probability of success starting from state $(x, m)$ when policy $f$ is employed. Once the decision process leaves state $(x, m)$ for $x \geq x^{*}$ , it never stops until absorption takes place under $f$ . Thus we have $v_{f}(x)=\{$ $s(x)$ , $\mathrm{i}\mathrm{f}x<x^{*}$ $P_{x}(Nm+1x, x)$ , $\mathrm{i}\mathrm{f}x\geq x^{*}$ , (3.7) and it is easy to check that $s(x)$ is decreasing in $x$ , while $P_{x} (Nm+1X, x. )$ is increasing in $x$ and that $x^{*}$ can be described as $x^{*}= \min\{x : s(X)\leq P_{x}(Nm+1x, x)\}$ . Therefore, to prove $f$ is optimal, it suffices to show that $v_{[}(x) $ given in (3.7) satisfies $v_{f}(x)= \max\{s(X), cf(x)\}$, $0<x<Nm+1$, where $c_{f}(x)$ $=$ $\{p\theta P+qP_{x1}(1, X1)\}vf(X)$ $+p(1 \theta P)\sum y=x+1^{+}(N2m1P^{y1}x1P)vf(y)$ $+p(1\theta P)P^{N}x2m1$ We can show this in a similar way as in Theorem 2.1, appealing to Lemma 3.3. Finally we give $V(x)$ , success probability starting from $\mathrm{x} $ units of fortune. Lemma 3.5 Let $P$ be as defined in Lemma 3.2. Then, for $m1\leq x\leq Nm$, $V(x)= \sum^{N2}m+1{}_{r=x}Pm+1yx+m1(1P)vf(y)+P^{Nmx}+1$ . Proof This can be derived easily by conditioning on the first state $ (y, m)$ visited. References [1] Ross, S. M., Dynamic programming and gambling models, adv. Appl. Probab. 6, 593606, 1974. [2] Ross, S. M., Introduction to Stochastic Dynamic Programming. Academic Press, New York, 1983. 155

Pages: 1 Prev: #JVXL VERSION 1.4 Next: The Numbers Surrounding Unsolved Problems May Be Simple and Elegant 