Mathematics and Darts!

In this blog post I am going to talk about one of my favorite math problems. When I first solved this problem, I developed a method that can be generalized to a lot of other similar problems. The problem is as follows:

Alice and Bob take turns throwing darts at a dartboard (with Alice going first). At each turn, Alice will try to get it closer to the center than Bob's last throw and vice versa. The game ends when one of the players doesn't get it closer than the other player's previous throw. Alice and Bob are equally skilled at throwing darts and they are guaranteed to hit the dart board.
What is the probability that Alice wins?

To help you visualize this problem, I created a simple program in Racket (then compiled it to JavaScript using whalesong.) You can visualize the game being played by pressing the Right Arrow Key (make sure the frame is in focus). You can speed up the simulation by pressing the Space Bar (you can pause the simulation by pressing it again.)

 

In the above simulation, the red circles indicate the location of Alice's throws, and the green circles indicate the location of Bob's throws (the exact location is not shown, only the distance from the center). Alice goes first so she cannot lose on the first turn. Then Bob goes and he must get it within the red circle that Alice just established. If he succeeds, then Alice must get her next throw within the green circle that Bob just established. The score is recorded in the top corners, with Alice's score in the top left and Bob's score in the top right.

If you run the simulation long enough, you'll probably notice that Alice has an advantage in this game. Let's find out why!

Solution

This solution is going to rely on idea's from Probability Theory, Calculus and Differential Equations. The calculus and differential equations in this solution is pretty straightforward, but the derivation of the equations requires some creativity and careful thinking. As a computer scientist, I usually try to think about problems recursively, so naturally that's how I approached this problem.

Let's first normalize this problem, such that the radius of the circle is $1$. The problem doesn't change, but it allows us to think about the problem in a more concrete manner. Now, let's define a function $P(x)$, which denotes the probability that the current player will win given that the current established minimum distance from the origin is $x$. I define this function for the current player rather than for either Alice or Bob because both player's have the same skill level, so we don't need to use a 2 function circular definition. It should be noted that the answer to the original problem is $P(1)$ because Alice goes first and the established minimum distance starts at $1$. It should also be noted that $0≤x≤1$ because $x$ can never increase and the distance cannot be negative. Now let's think about the sub problems that can arise from any current position. I will assume that the distance from the center of the circle for every throw is a uniformly distributed random variable, although as it turns out, the distribution doesn't even matter as long as Alice and Bob are equally skilled. Thus, the probability of losing immediately is $1−x$. Although this may not hold under scrutiny, you can think of this as a base case to the recursive function; if we think of this as a function in a computer program, it provides a way for the function to terminate. When xx becomes arbitrarily small, the probability of losing approaches $1$; this should be pretty intuitive. In general,
$$
P(x) = \int_0^x 1 - P(y) \: dy
$$ The the dart is thrown uniformly from $[0,1]$ this is domain of possible throws for the current player. However, if the distance from the origin $y$, is greater than $x$, then we lose immediately, so we only consider values of $y$ where it's still feasible to win, namely $0≤y<x$. Thus, there is a $x$ probability that the game continues. In order to win, we must throw it closer than $x$ AND the other player must lose; this is where the recursive definition comes into player. The probability that the other player loses with current minimum $y$ is just $1−P(y)$ because winning and losing are disjoint events. Thus, the above integral describes the probability of winning for the current player. How do we solve such an equation? Well, we can transform this problem into a differential equation by applying the second Fundamental Theorem of Calculus. Differentiating both sides with respect to $x$, we get

$$ P'(x) = 1 - P(x) $$ This is an easy differential equation to solve, and it follows immediately that

$$ P(x) = c e^{-x} + 1 $$ Using the fact that $P(0)=0$, we can readily see that $c=−1$. We know $P(0)=0$ because if the established minimum is already at the center of the circle, there is no way to beat it. The answer to the original question is then

$$ P(1) = 1 - \frac{1}{e} \approx 0.63212 $$ which means Alice has a pretty good advantage in this game.  This was a really enjoyable problem and in the process of solving it I learned and derived a whole new method to solve problems! If you enjoyed this blog post, I used a similar idea to solve another Unfair Game!