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!

Processors speeds are no longer growing at the rate we've grown accustomed to. Moore's law states that computers double in speed every 18 months. Moore's law is still alive and well, but we just need to find alternate ways to speed up computers. That's where multi-core programming comes into play. The idea behind it is that 2 heads are better than one and in the right situation 2 processors can work on the same problem to solve it twice as fast. Parallel programming is becoming increasingly important these days and there are many different flavors of it including distributed computing, shared memory computing, and GPU computing. Today I am going to focus on shared memory computing, or using multi-core computers rather than many single core computers. This blog post is intended to serve as a beginners guide to parallel programming with Java. It is recommended that the reader have some java experience and is familiar with some of the features of Java 8 (namely lambda exp…

If you have taken an introductory computer science course, you've probably seen the binary search algorithm - an algorithm to efficiently find the index of an item in a sorted array, if it exists. You might not have heard of interpolation search, however. Interpolation search is an alternative to binary search that utilizes information about the underlying distribution of data to be searched. By using this additional information, interpolation search can be as fast as $O(log(log(n)))$, where $n$ is the size of the array. In this post I am going to talk about two implementations of interpolation search. First, I will discuss the algorithm as described on Wikepedia, then I will describe my own version of the algorithm that has a better worst case time complexity than the first and performs better in practice than the traditional binary search and interpolation search algorithms.
The Basic Idea
Interpolation search models how humans search a dictionary better than a binary search, be…

Suppose you have a 2d numpy array and you want to remove duplicate rows (or columns). In this blog post, I'll show you a trick you can use to do this more efficiently than using np.unique(A, axis=0). This algorithm has time complexity $ O(\max(n \log{n}, n m)) $ for an $ n \times m $ matrix, and works almost surely. By "almost surely" I mean that it is a randomized algorithm that works correctly with probability $1$. To find the unique rows of a matrix $A$, the algorithm works by generating a random vector $x$ of real numbers, computing the dot product $ y = A x $, then analyzing the unique elements of $y$. The indices of unique elements in $y$ is the same as the unique row indices in $A$ with probability $1$. Below is an example to demonstrate how it works:

nice

ReplyDeleteFree Game

Steam Keys

Free Steam Keys

Game Giveaway

Game Steam Giveaway

Free Steam Game Giveaway