May 24, 2020
Math is all about making connections. What makes something that was built from a few statements taken to be true, and blossomed into everything that governs how we perceive nature? The answer: connections. We can make a few statements taken to be true in arithmetic, say, and develop a whole branch of mathematics out of it, and in parallel, do the same thing independently for, say, probability. What makes everything truly click, and for humankind to pick up on the whole math thing, is how independent branches of math form a coherent picture in the end.
Consider the following brain-teaser:
\begin{equation} \left(1 - \frac{1}{2}\right) \times \left(1 - \frac{1}{3}\right) \times \left(1 - \frac{1}{4}\right) \times \dots \times \left(1 - \frac{1}{N}\right) = \quad ? \end{equation}
Hint: don't expand the binomials. Instead, evaluate each one to arrive at the following: \begin{align} ? &= \left(1 - \frac{1}{2}\right) \times \left(1 - \frac{1}{3}\right) \times \left(1 - \frac{1}{4}\right) \times \dots \times \left(1 - \frac{1}{N}\right) \\ &= \left(\frac{1}{2}\right) \times \left(\frac{2}{3}\right) \times \left(\frac{3}{4}\right) \times \dots \times \left(\frac{N-1}{N}\right) \\ &= \frac{1}{N} \\ \end{align}
Because each fraction except for the first and last one will have its numerator cancelled out by the previous denominator. This is known as telescoping.
I hope you find it pretty neat. Of course, if that was it, I wouldn't be making this post. Now, let me introduce to you something that I have been doing during the quarantine:
Sorry to disappoint, but if I am stuck inside, and I have my phone with me, I'll play games. Pubg (Player Unknown's Battleground) Mobile is one of the most popular gaming apps out there today. It followed the footsteps of its PC counterpart that came out in 2017 and changed the gaming world forever with the popularization of the Battle Royale genre (I wouldn't say it invented it, because games like H1Z1 preceeded Pubg, but I digress). For those of you that were not familiar with Battle Royale, it is a type of game named after the Japanese novel-turned-into-movie of the same name that focuses on survival. N players drop into a battleground and fight to death Hunger Games style against a shrinking battle zone, until there is only one survivor--the Chosen One, who is the winner and gets the glorious prize of--a chicken dinner.
(Yes that was a flex.)
Alright, back to the main topic. Why did I bring up Pubg Mobile? Well, as I was playing it, I couldn't help but think, what is the probability of me winning? I mean, of course it would depend on how skilled I am, which I must admit, is not as good as some of the players out there and those streamers you see on Twitch, Huya, Douyu, etc. (but I do try my best each game!). However, let's simplify things here and supposed all players on the battleground are equally skilled. If two players clash, it will be a coin flip who gets eliminated and who gets to live to fight another fight. Then it dawned on me thanks to the beauty of symmetry. If there are N players, then of course my probability in that case would be 1/N. This is because if all players are equally skilled, then no player is special and you, me, and everyone else trying to survive would all be equally likely to get that chicken dinner, hence the probability is 1/N. However, let's figure out the answer another way, as if there is one thing math has taught me, it's that there are always other ways to get the answer.
Let's take a step back and really make sure we have the model explicitly stated. Let's consider a space with N particles floating around it, and we will assume at most two particles will collide and the same time. When two particles collide, each one will have a 1/2 probability of being annihilated, and the other particle will survive. We are interested in the probability of a particular particle in the space being the sole survivor. By symmetry we know the answer is 1/N, but can we use the model to figure out the answer stochastically? The answer is yes. Please see the stochastic chart below:
Here for brevity, I named the particle as "you", and denoted the clash of two particles as a "duel". Then, the rule of survival for you is pretty simple: move on N-1 times to be the sole survivor, as there will be N-1 duels in the space of N particles, as each duel eliminates exactly 1 particle. To move on from a stage, you must satisfy the following conditions:
Which is pretty self-explanatory. If you get picked for a duel and lost it at any stage, then you are eliminated. If you survive for N-1 stages, then you will be the sole survivor.
So let's do some math! First, let us calculate the probability of you moving on from stage k, where k is the number of particles remaining. Obviously k starts at N and goes down to 2. When k = 1, you are the sole survivor. We will denote this probability as \(P_k\)(move on).
Whew! That's a lot of math. Let us stop and digest everything here. First of all, as the stochastic chart showed, the probability of you moving on to the next stage, with k particles remaining, is the probability that you get picked for the duel and win it, OR, you did not get picked. In the former case, the probability is as shown in the first term of the second equation line. What we have here is 1/2 denoting the probability that you would win the duel, which is the equally-likely setup for the model, and the probability that you would get picked. Now, how many duel pairings are there? The answer: k choose 2. If you would like a refresher for the choose function, please see the blog post Simplicity from Sophistication and Sophistication from Simplicity. Out of those pairings, how many would contain you? The answer: k-1, as you have potentially k-1 duel mates. The second term is the probability that you would NOT get picked, which is simply 1 - (probability that you would). At the end of the day, combining with the fact that k choose 2 evaluates to k(k-1)/2, we have our answer: \(P_k\)(move on) = 1 - 1/k.
Now, let's continue the journey and figure out the probability that you would be the sole survivor. This probability is simply the probability that you survive all N-1 stages of duel selection and dueling (if you get selected), and if at the end of N-1 rounds, you are still aliving and kicking, you would be the sole survivor. The probability is as follows:
The last equation can be evaluated via the brain-teaser telescoping trick mentioned at the beginning of the post. This probability makes sense as it should be from symmetry point of view.
What I have shown to you is that math is connected. You can make axioms that estabilish the field of arithmetics, and independently do the same for probability, and the beauty of math makes everything connected, and in the end, everything makes sense.