A place where share my thoughts and ideas with the world.
Mathematics and Darts!
Get link
Facebook
Twitter
Pinterest
Email
Other Apps

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!
In this post, I will discuss my findings in terms of an optimal strategy for Farkle , which is a dice game of chance. If you are unfamiliar with the game, I encourage you to skim the linked article so that you can better understand this blog post. All of my findings are based on sound mathematical methods and a computer program was used to determine the optimal strategy. Before I begin, let me first state the value of different dice rolls I assumed while developing the strategy. Each 1: 100 points Each 5: 50 points 3 1's: 1000 points 3 2's: 200 points ... 3 6's: 600 points 4 1's: 2000 points ... 4 6's 1200 points 5 1's 3000 points ... 5 6's 1800 points Straight 16 1500 points 3 Pairs (e.g., 22 33 44): 750 points Everything else is considered to be a Farkle (0 points). There are many variants to Farkle, but I like to play by this set of rules. The "game state" of Farkle roll can roughly be characterized by 2 values: the curre
A few weeks ago, I was using a Markov Chain as a model for a Project Euler problem, and I learned about how to use the transition matrix to find the expected number of steps to reach a certain state. In this post, I will derive the linear system that will help answer that question, and will work out specific an example using a 1dimensional random walk as the model. Terminology Before I begin the derivation, let me define some terms. The transition matrix is an \( n \) by \( n \) matrix that describes how you can move from one state to the next. The rows of the transition matrix must always sum to 1. States can either be transient or absorbing . An absorbing state is one that cannot be left once reached (it transitions to itself with probability 1). A transient state is a state that is not an absorbing state. In many problems, it is of general interest to compute the expected number of steps to reach an absorbing state (from some start state). Derivation Let \( p_
In a lot of the recreational math and computer science problems I solve, I try to derive a recurrence relation that describes the situation. These recurrence relations pop up pretty often in counting problems (how many ways can you tile a 2xn grid with 2x1 tiles?) In some cases, I am unable to derive a recurrence relation directly from the problem statement, but still suspect that there exists some recurrence relation. In these cases, I end up solving the problem usin g brute force methods for small input sizes and analyzing/extrapolating the pattern. However, when the relation is obscure, it becomes hard to find. In order to make this process easier in the future, I created a program that can automatically find recurrence relations for arbitrary integer sequences. To use it, simply type in the first few terms of a sequence you are interested in, and it will try to find a recurrence relation for that sequence. There are some constraints on the allowable inputs/outputs which I di
Comments
Post a Comment