数理解析研究所講究録
第 1864 巻 2013 年 1-3

1
A Typical Lower Bound for Odds Problem inMarkov-dependent Trials 1
Katsunori Ano
Department of Mathematical Sciences
Shibaura Institute of Technology

1Introduction

We study a stopping problem for Markov-dependent trials of the odds problem. It may bedescribed as follows. For a positive integer $N$ , letdenote 0/1 random variables
defined on a probability space. These 0/1 random variables appears according to
non-homogenous Markov chain with the transition probability such that
$X_{1},$ $X_{2},$$\ldots,$$X_{N}$$(\Omega, \mathcal{F}, P)$$P_{i}=(\begin{array}{ll}1-\beta_{i} \beta_{i}\alpha_{i} 1-\alpha_{i}\end{array})$where$\beta_{i}$$:=P(X_{i+1}=1|X_{i}=0),$$\alpha_{i}$,(1)$:=P(X_{i+1}=0|X_{i}=1)\beta_{0}$ $:=P(X_{1}=0)$and. Each and are given. We assume
for all . We’s sequentially and claim that the ith trial is a success if $X_{i}=1$ . We wantto find the optimal stopping rule that maximize the probability of obtaining the last success(we call this event win) and the probability of win.
$N$ in the transition probability,
If $0<\alpha_{i}+\beta_{i}<1$ for all $i=1,2,$
then Hsiau andYang [7] found the optimal rule, but it was not of odds form. Bruss [5] proved that the lower
bound for odds problem in Bernoulli trials is $1/e$ for any sequence of success probabilities,$\alpha_{0}:=P(X_{1}=1)=1-\beta_{0}$observe these$\alpha_{i}$$0<\alpha_{i},$ $\beta_{i}<1$$\beta_{i}$$i$$X_{i}$$\ldots,$$P(X_{i}=1),$$i=1,2,$$\ldots,$$N.$

The main result of this paper is that the asymptotic lower bound of probability of win isalso $1/e$ for any transition probability of Markov chain under a certain condition. think it
is wonderful!
$I$

2Main result

Recall that Ano, Kakie and Miyoshi [3] proved that even thought it is for Markov-dependent
trials, the optimal stopping rule can be expressed as of dds form. Let$0$$p_{ij}:=\{\begin{array}{ll}P(X_{i+1}=1|X_{i}=1, X_{i+2}=0)=(1-\alpha_{i})\alpha_{i+1}, j=i+1,P(X_{i+1}=1|X_{j-1}=0, X_{j+1}=0)=\beta_{j-1}\alpha_{j}, j>i+1,\end{array}$and $r_{ij}=p_{ij}/(1-p_{ij})$ . This is ur key setting inspired by the incredible insight in Ferguson [6]who studied the general dependent sequence ofin odds problem.
$0$$X_{i}$lThis is an abbreviation of the original version.

2Theorem 1 (Ano, Kakie and Miyoshii [3]) Assume thatfor eachMarkov-dependent
non-homogeneoustrials isthestmtegyselectingsingleoptimal
Theforgiven by$0<\alpha_{i},$ $\beta_{i}<1$$\tau^{*}=\min\{i\in \mathcal{N}$$i\in \mathcal{N}.$: $X_{i}=1$ & $\sum_{j=i+1}^{N}r_{ij}<1\}=\min\{i\geq i^{*} : X_{i}=1\}.$

Assume that $X_{1}=1a.s.$ , then the probability of win holds the inequality$P_{N}$(win)$=P_{N}(\alpha_{0}, \ldots, \alpha_{N-1}, \beta_{0}, \ldots, \beta_{N-1})\geq\hslash_{-1}*V_{i^{*}-1},$

where $R_{s}= \sum_{j=s+1}^{N}r_{sj}$ and$V_{s}= \alpha_{s}\prod_{k=s+1}^{N-1}(1-\beta_{k})$.

Next theorem is the main result of this paper.

Theorem 2 Assume that $X_{1}=1,$ $a.s$ . If $R_{s}= \sum_{j=s+1}^{N}r_{sj}$ with $s=i^{*}-1$ , then(i)$P_{N}$(win) $\geq R_{S}V_{S}>R_{s}e^{-R_{s}}.$(ii) If $R_{s}=R_{s(N)}arrow 1$ as $Narrow\infty$ , then$\lim_{Narrow\infty}P_{N}$(win) $>1/e.$

Proof.
(i) By the optimality equation $M_{i}= \max\{V_{i},$ $\sum_{j=i+1}^{N}P_{ij}M_{j}\}$ and since $\sum_{j=i+1}^{N}P_{ij}M_{j}$ isdecreasing in , we have
$i$$P_{N}$(win) $=P_{N}(win|X_{1}=1)$$=:M_{1}= \max\{V_{1},\sum_{j=2}^{N}P_{2j}M_{j}\}$$\geq\sum_{j=s}^{N}P_{sj}M_{j}\geq\sum_{j=s}^{N}P_{sj}V_{j}$,(2). Using $r_{ij}=$
where $V_{i}=P_{N}$ (win by stop at $X_{i}=1|X_{1}=1$ )for $j=i+1;=\alpha_{j-1}\beta_{j}/(1-\beta_{j-1})(1-\beta_{j})$ for $j>i+1$ , we$= \alpha_{i}\prod_{j=i+1}^{N-1}(1-\beta_{j})$$(1-\alpha_{i})\alpha_{i+1}/\alpha_{i}(1-\beta_{i+1})$

have$P_{N}$(win)$\geq\sum_{j=s+1}^{N}\frac{P_{sj}V_{j}}{V_{s}}V_{s}=\sum_{j=s+1}^{N}r_{sj}V_{s}=R_{s}V_{S}.$, where $\tilde{N}=N$ if $N$ is an even integer,(ii) Note thatand $\tilde{N}=N-1$ if $N$ is an odd integer. Since $1-\beta_{k}<1,$$V_{s}= \prod_{k=s+1}^{N-1}q_{sk}/(\prod_{k=s+1}^{\overline{N}-1}(1-\beta_{k}))$$P_{N}$(win)$\geq R_{s}V_{s}=\frac{R_{s}\prod_{k=s+1}^{N-1}q_{sk}}{\prod_{k=s+1}^{N^{-}-1}(1-\beta_{k})}>R_{s}\prod_{k=s+1}^{N-1}q_{sk}.$

3
From $R_{s}= \sum_{k=s+1}^{N}(1/q_{sk}-1)$ , we have $\sum_{k=s+1}^{N}(1/q_{sj})=R_{s}+N-s$ . By the inequality
for arithmetic mean and geometric mean, then$( \prod_{k=s+1}^{N}\frac{1}{q_{sk}})^{\frac{1}{N-s}}=(\frac{1}{\prod_{k=s+1}^{N}q_{sk}})^{\frac{1}{N-s}}\leq\frac{\sum_{k=s+1^{\frac{1}{q_{sk}}}}^{N}}{N-s}=1+\frac{R_{s}}{N-s}$and thus $\prod_{k=s+1}^{N}q_{sk}\geq(1+R_{s}/(N-s))^{-(N-s)}$ . From $(1+R_{S}/(N-s))^{-(N-s)}\downarrow e^{-R_{S}}$as $Narrow\infty$ , it follows that
$P_{N}$

as(win) $>R_{s} \prod_{k=s+1}^{N-1}q_{sk}\geq R_{s}(1+\frac{R_{s}}{N-s})^{-(N-s)}>R_{s}e^{-R_{8}}arrow 1/e,$$Narrow\infty.$$\square$

References[1] ANO K. (2000). Mathematics of Timing–Optimal Stopping Problem (in Japanese).
Asakum publ. Tokyo[2] ANO K., KAKINUMA H. AND MIYOSHI N. (2010). Odds theorem with multiple selection
chances. J. Appl. Probab. 471093-1104.

[3] ANO K., KAKIE N. AND MIYOSHI N. (2010). Odds theorem in Markov-dependent trials
with multiple selection chances. Kokyuroku. RIMS, Kyoto University. 1734212-219.
[4] BRUSS F. T. (2000). Sum the odds to one and stop. Ann. Probab. 281384-1391.
[5] BRUSS F. T. (2003). A note on bounds for the odds theorem of optimal stopping. Ann.
Probab. 311859-1861.
[6] FERGUSON T. S. (2008). The sum-the-odds theorem with application to a stopping gameof Sakaguchi. Preprint.
[7] HSIAU S.-R. and YANG J.-R. (2002). Selecting the last success in Markov-dependent
trials. J. Appl. Probab. 39271-281.

[8] MATSUI T. and ANO K. (2012). Lower bounds for Bruss’ odds problem with multiple
stoppings. arXiv:1204. 5537, 2012.