A place where I turn my thoughts into words and share them with the world.

Math Puzzle: Rich Get Richer?

Get link

Facebook

Twitter

Pinterest

Google+

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.

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:

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…

In order to maximize your probability of beating the streak, you should (1) predict the probability that a batter will get a hit in a given game given the game parameters and (2) determine if it's worthwhile to risk your current streak in order to possibly improve it by 1 or 2 games. In this blog post, I outline my solution to (2). In previous blog posts, I've hinted at what I do to solve (1) and will continue that discussion in a later blog post.

Motivation
When your current streak is short, the optimal strategy is to pick the best player every day, regardless of how likely their probability of getting a hit is (to a certain extent). However, as your streak grows, you have an important decision to consider: is it better to pick the best player today and possibly lose your current streak, or skip picking a player and instead maintain your current streak. Naturally, this decision should be guided by the players probability of getting a hit, as well as the distribution of these …

Best site to find newspapers directory is Librly. Do not wait just find list of newspapers or full best newspapers directory. If you are intrested in top newspapers in world just go to Librly. You will find complete list of newspapers in world contains best newspapers in world

ReplyDeleteSuperb Article, visit mine at

ReplyDeleteAgen DominoAgen PokerAgen ReferralPoker Live