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

Question

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.

Answer 1

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}^\infty\frac{2n-1}{(2n!)} & = \sum_{n=1}^\infty\left(\frac{1}{(2n-1)!}-\frac{1}{(2n!)}\right) \\ & = \sum_{n=1}^\infty\frac{(-1)^{n+1}}{n!} \\ & = 1-\sum_{n=0}^\infty\frac{(-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.

Answer 2

You're on the right track.

For $0\le a \le 1,$ let $p(a)$ be the chance of losing when it's your turn and $a$ is the largest value drawn so far. In order to lose (a) you have to draw a number $x$ between $0$ and $a$, making certain your chances of losing, or (b) you draw $x \ge a$ then your opponent, faced with the new value $x,$ must win, which she does with probability $1 - p(x).$ We have to average these possibilities over all the possible values of $x,$ giving the recursion

$$p(a) = \int_0^a \mathrm{d}x + \int_a^1 (1-p(x))\,\mathrm{d}x = 1 - \int_a^1 p(x)\,\mathrm{d}x.\tag{*}$$

At the outset, $a=0,$ it's your turn, and therefore you want to find the chance of winning, which is $1-p(0).$

Let $P(a) = \int_a^1 p(x)\,\mathrm{d}x.$ This is a differentiable function with derivative $P^\prime(a) = -p(a).$ In these terms $(*)$ becomes

$$-P^\prime(a) = 1-P(a).$$

Since $p(a)\lt 1$ for most $a,$ $P(a) \lt 1$ for all $a,$ allowing us to divide both sides by $1-P(a),$ giving

$$\frac{\mathrm d}{\mathrm{d}x} \log(1-P(a)) = \frac{-P^\prime(a)}{1-P(a)} = 1.$$

Integrating both sides and using $P(1)=0$ gives the unique solution $P(a) = 1 - \exp(a-1).$ Taking the derivative yields

$$p(a) = -P^\prime(a) = e^{a-1}.$$

The solution therefore is $1-p(0) = 1-e^{-1} \approx 0.632.$

Answer 3

Here's a basic solution:

$$P[\text{player A wins}] = \sum_{n=1}^\infty P[\text{player A wins on draw } 2n]$$

$P[\text{player A wins on draw } 2n]$ is the probability that a random permutation of a set of $2n$ distinct numbers has the first $2n - 1$ in ascending order and the last is not maximal. How many such permutations exist?

There are $2n - 1$ possibilities for a non-maximal final element and, conditional on that, one ascending ordering of the others, i.e.,

$$P[\text{player A wins on draw } 2n] = \frac{2n - 1}{(2n)!}$$

A little algebra gives

$$P[\text{player A wins}] = \frac{1}{1!} - \frac{1}{2!} + \frac{1}{3!} - \frac{1}{4!} + ...$$

This alternating sum of reciprocal factorials might look familiar:

$$\exp(-1) = 1 - \frac{1}{1!} - \frac{1}{2!} + \frac{1}{3!} - \frac{1}{4!} + ...$$

thus

$$P[\text{player A wins}] = 1 - \exp(-1)$$

Answer 4

You need to make use of the fact that the probability of being greater than the maximum of a set of iid random variables is equivalent to being greater each one of those individual random variables. This allows you to rephrase the maximum as a product. See the (flipped) derivation here https://stats.stackexchange.com/a/32353/60065

Answer 5

The solution is provided in Devroye's Non-uniform random variate generation [open access] book as the basis to Von Neumann's exponential random generator: