A Coin Flip by Any Other Name…
Consider the following graph.
If we remove each edge with independent probability 1 / 2 , 1/2, 1/2, what is the probability that there is still a path from the top to the bottom vertex?
Since the removal of each subset of edges is equally likely, this kind of question is equivalent to counting the subsets of edges that we can remove without disconnecting two vertices. How easily we crunch through this enumeration depends on how we manage to decompose the problem.
However, suppose we learn that the probability of a path remaining in this particular graph is exactly 1 / 2. 1/2. 1/2. Forget combinatorics—something strange is happening! In fact, it turns out that our special case can be solved with a "duality" trick, illustrated below. (Click the graph to generate a new random configuration.)
There will be a path between the top and bottom nodes exactly when there is no path between the left and the right nodes. Furthermore, the top-to-bottom and left-to-right graphs are the same and, once identified, have the same distribution of missing edges. In other words, we have found a rearrangement of the outcomes of our random process—the subsets of missing edges—that swaps the event that a path exists with the event that no path exists. Since this rearrangement preserves probability, it follows that each event must have probability 1 / 2. 1/2. 1/2. (I learned this beautiful idea from this mathpages article.)
Let's take a look at another suspicious problem. Suppose we choose four points on the unit circle. What is the probability that the origin lies in their convex hull? (Again, click for random configurations.)
As it turns out, the answer is again exactly 1 / 2. 1/2. 1/2. If you're skeptical, you can press the "play" icon above to resample the experiment at high speed. (The black lines under the bar graph delineate the ± 3 σ \pm 3 \sigma ±3σ interval that the empirical proportion should stay within about 99 % 99\% 99% of the time for large n n n.)
In my experience, things don't happen with even odds unless they have a very good reason to, and that reason is usually a symmetry. For example, a coin will land heads as often as it lands tails because it is approximately symmetric, and there is no reason for the laws of physics to privilege one side of a symmetric coin so long as we have given it enough energy to make its initial condition approximately irrelevant.
Is there any appropriate symmetry in the problem of the four points? In such questions, it is important to have a degree of faith. Of course there is a symmetry; symmetry is everywhere! Unfortunately, symmetry does occasionally work in mysterious ways, and here it is not exactly obvious.
... continue reading