2018/12/13 by Ribas, José María Grau
Computer Science · Mathematics · #Optimization and Search Problems #Distributed systems and fault tolerance #Markov Chains and Monte Carlo Methods
paper · pdf · doi:10.48550/arxiv.1812.05381
There are n independent Bernoulli random variables with parameters pi that are observed sequentially. Two players, A and B, act in turns starting with player A. Each player has the possibility on his turn, when Ik=1, to choose whether to continue with his turn or to pass his turn on to his opponent for observation of the variable Ik+1. If Ik=0, the player must necessarily to continue with his turn. After observing the last variable, the player whose turn it is wins if In=1, and loses otherwise. 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 towards its limit (1)/(2) - (1)/(2 e2)=0.4323323.... We also study the game when the parameters are the results of uniform random variables, U[0,1]