A Turn-Based Game Related to the Last-Success-Problem
- PDF / 330,145 Bytes
- 9 Pages / 439.37 x 666.142 pts Page_size
- 51 Downloads / 167 Views
A Turn-Based Game Related to the Last-Success-Problem J. M. Grau Ribas1
© Springer Science+Business Media, LLC, part of Springer Nature 2019
Abstract There are n independent Bernoulli random variables with parameters pi that are observed sequentially. We consider the following sequential two-person zero-sum game. Two players, A and B, act in turns starting with player A. The game has n stages, at stage k, if Ik = 1, then the player having the turn can choose either to keep the turn or to pass it to the other player. If the Ik = 0, then the player with the turn is forced to keep it. The aim of the game is not to have the turn after the last stage: that is, the player having the turn at stage n wins if In = 1 and, otherwise, he loses. We determine the optimal strategy for the player whose turn it is and establish the necessary and sufficient condition for player A to have a greater probability of winning than player B. We find that, in the case of n Bernoulli random variables with parameters 1/n, the probability of player A winning is decreasing with n toward its limit 1 1 2 − 2 e2 = 0.4323323 . . .. We also study the game when the parameters are the results of uniform random variables, U[0, 1]. Keywords Last-success-problem · Odds-theorem · Optimal stopping · Optimal threshold Mathematics Subject Classification 60G40 · 62L15 · 91A05 · 91A25 · 91A60
1 Introduction The last-success-problem (LSP) is the problem of maximizing the probability of stopping on the last success in a finite sequence of Bernoulli trials. There are n Bernoulli random variables which are observed sequentially. The problem is to find a stopping rule to maximize the probability of stopping at the last “1.” This problem has been studied by Hill and Krengel [3] and Hsiau and Yang [4] for the case in which the random variables are independent and was simply and elegantly solved by T.F. Bruss in [1] with the following famous result. Theorem 1 (Odds-Theorem, T.F. Bruss [1]) Let I1 , I2 , . . . , In be n independent Bernoulli random variables with known n. We denote by (i = 1, . . . , n) pi the parameter of Ii ; i.e., ( pi = P(Ii = 1)). Let qi = 1 − pi and ri = pi /qi . We define the index
B 1
J. M. Grau Ribas [email protected] Departamento de Matemáticas, Universidad de Oviedo, Avda. Calvo Sotelo s/n, 33007 Oviedo, Spain
Dynamic Games and Applications
s=
n ri ≥ 1 ; max 1 ≤ k ≤ n : nj=k r j ≥ 1 , if i=1 1,
otherwise.
To maximize the probability of stopping on the last “1” in the sequence, it is optimal to stop on the first “1” that we encounter among the variables Is , Is+1 , . . . , In . The optimal win probability is given by ⎛ ⎞
n n ⎝ ⎠ V ( p1 , . . . , pn ) := qj ri . j=s
i=s
In this paper, we propose a turn-based game related to this problem. There are n independent Bernoulli random variables Ii with parameters pi that are observed sequentially. We consider the following sequential two-person zero-sum game. Two players, A and B, act in turns starting with player A. The game has n stages, at stage k, if Ik = 1, then the player
Data Loading...
