A place to share my thoughts and ideas with the world.
Math Puzzle: Rich Get Richer?
Get link
Facebook
X
Pinterest
Email
Other Apps
-
Today I'm going to talk about a math problem whose answer is simultaneously simple and unintuitive. Here is the problem statement:
You have a urn that has $1$ red ball and $1$ blue ball. You repeatedly remove one ball from the urn randomly, then put two balls of the same color back into the urn. How does this system behave over time? Specifically, what is the probability that at some point the urn will contain exactly $r$ red balls and $b$ blue balls?
If you want to see my solution, go ahead and expand the solution tab. Otherwise, you can try to figure it out for yourself. Also, if you have other interesting questions you want to ask about this system, feel free to post them in the comments below.
Intuitively, this seems like a "rich get richer" problem", in that the long term behavior of the system depends on how "lucky" we are in the early stages (i.e., how many red and blue balls we pick). For example, if we pick mostly red balls, then we'd expect the long term behavior to be overwhelmed by red balls, and the same goes for the blue balls. However, if the proportion starts off nearly equal for each color, we'd expect it to remain nearly equal long term. That was my initial intuition, but maybe yours is different. Anyway, I will now show that the initial intuition contradicts the mathematics.
First notice that one way to get to $r$ red balls and $b$ blue balls is to pick a red ball $r-1$ times then a blue ball $b-1$ times. Picking $r-1$ red's in a row occurs with probability:
$$ \frac{1}{2} \cdot \frac{2}{3} \dots \frac{r-1}{r} $$
and following that up with $b-1$ blues in a row occurs with probability: $$ \frac{1}{r+1} \cdot \frac{2}{r+2} \dots \frac{b-1}{r+b-1} $$
so the overall probability is the product of these two probabilities. Now notice that no matter what sequence of balls we pick, the unreduced denominator will always be the same: $ (r+b-1)! $. Further, if we end up with the same number of red and blue balls, the numerator will be the same (since multiplication is a commutative operation) -- only the order will be different. This means that every way to end up with $r$ red balls and $b$ blue balls is equally likely, and each path has probability:
$$ \frac{(r-1)! (b-1)!}{(r+b-1)!} $$
There are $ \binom{r+b-2}{r-1} = \frac{(r+b-2)!}{(r-1)! (b-1)!} $ such paths, so the marginalized probability of ending up with $r$ red balls and $b$ blue balls is
$$ \frac{1}{r+b-1} $$
This is the answer to the original question, and it means is that every urn with $n$ balls is equally likely.
The answer to this problem turned out to be disappointingly simple. I typically like to solve problems with simple/elegant closed form solutions (e.g., involving e), but this is a little bit too simple I think. I think it was worth blogging about because the math contradicts the intuition (at least for me). Note that you could also solve this problem using induction on the number of balls in the urn, but that would require you to "assume" that every urn will $n$ balls is equally likely, and that would be an unintuitive assumption to make without working out some examples or already knowing the answer.
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 1-6 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 1-dimensional 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 \...
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