Solved – Probability of winning a game where you sample an increasing sequence from a uniform distribution

This is an interview question I got and could not solve.

Consider a two-person game where A and B take turns sampling from a uniform distribution $U[0, 1]$. The game continues as long as they get a continuously increasing sequence. If, at any point, a player gets a number less than the last number (the largest number so far), that player loses. A goes first. What is the probability of A winning?

For example, if the sequence is $0.1 (A), 0.15 (B), 0.2 (A), 0.25 (B), 0.12 (A)$, then A loses.

I think because A has no restrictions on their very first turn while B does, A's chance of winning is higher than 0.5. At any given turn $j$, we're looking at the probability that a newly sampled number is larger than the last sampled number $x_{j-1}$. This is $1 – CDF$ of a uniform distribution, which is just $F(x) = x$, so the probability of getting a larger number on step $j$ is $1 – x_{j-1}$. But I don't know where to go from here. If it were a discrete sampling, I would try to condition on B's last number maybe but here, I'm not sure what to do. I could still condition using integration but I don't know how to also use the information about whether on turn $j$, we are considering A or B or that A went first. My thinking is we use the parity of $j$ but not quite sure how to. Calling A's first turn $j = 1$, we have if $j~mathrm{mod}~2 = 0$ then it's B's turn and if $j~mathrm{mod}~2 = 1$, it's A turn. So if $j~mathrm{mod}~2 = 1$, A loses with probability $x_{j – 1}$ but if $j~mathrm{mod}~2 = 0$, A wins with probability $x_{j – 1}$?

Another thought process I had was to consider the problem graphically. I was picturing a 1 x 1 square where the x and y axis represent A and B's numbers respectively. A samples a number first, which immediately shrinks the "safe" region for B. This continues until one player loses. At each step, the height and width of the unit square take turns decreasing by $x_{j} – x_{j – 1}$. I also recognize that after A's first step, we are essentially back to the same game with just a starting position of $x_1$ instead of $0$, so this might involve setting up a recurrence relation but don't know how.

I'm happy with just hints on how to solve this but I won't mind a solution either.

You can solve this combinatorially, without using calculus. All you need to look at is the probability that the first $n$ samples are in a certain order, and for any particular order this is simply $1/n!$

The game ends after exactly $n$ steps if and only if the first $n-1$ samples are in increasing order, and the last sample is not. The last sample can occupy any of the $n$ positions except the highest, so there are $n-1$ such sequences; hence the probability that the game ends after exactly $n$ steps is $frac{n-1}{n!}$.

And $A$ wins if the game ends after an even number of steps, so $A$'s probability of winning is $$begin{align} sum_{n=1}^inftyfrac{2n-1}{(2n!)} & = sum_{n=1}^inftyleft(frac{1}{(2n-1)!}-frac{1}{(2n!)}right) \ & = sum_{n=1}^inftyfrac{(-1)^{n+1}}{n!} \ & = 1-sum_{n=0}^inftyfrac{(-1)^n}{n!} \ & = 1 – frac{1}{e} end{align}$$

This assumes nothing about the particular distribution of the samples, except that it is continuous. So the answer is the same whatever the distribution.

Similar Posts:

Rate this post

Leave a Comment