Non-Measuable Ghost: Persi’s Halloween Talk

It was a ghostful Monday–a Monday full of non-measurable ghosts.

You’ve probably heard of this one sphere cut into five pieces becomes two spheres story. This Monday Professor Persi Diaconis gave a public Halloween lecture about these ghosts. I would love to share an amazing proof that shows 0.5=0.99 or 0.999 or 0.9999. Well, with some assumptions.

SO!

Let’s assume we can take infinitely many independent and identically distributed random variables. And we, like thousands of mathematicians and non-mathematicians before us, admit that we have the Axiom of Choice. Doesn’t sound too outrageous, right?

OK! Let’s walk through the proof that leads to a terrible, terrible, haunted world.

First of all, we translate the equation 0.5=0.99 into a game. Here are out two famous players: Alice and Bob.

Alice writes down a sequence a_1 \in \{0, 1\}, a_2 \in \{0, 1\}, a_3 \in \{0, 1\}, ..., each number is drawn from an i.i.d. distribution. Bob, without seeing the sequence, specifies one sequence number, for which Alice covers the corresponding  value in her sequence. Then, Alice shows Bob the rest of her sequence. Based on this information, Bob decides what value the unknown should be. Alice wins if Bob makes a wrong guess, and Bob wins if his guess is correct. I hope the formulation makes sense. Notice we’ve already used one assumption to make this game possible.

Now, I claim that since the numbers are i.i.d., Bob has a 50% chance of winning no matter how he makes up the choice. On the other hand, if Bob uses the following strategy, he will have a 99% chance of winning. Therefore, 0.5 = 0.99.

Here’s Bob’s strategy based on the Axiom of Choice. I divide the strategy into steps.

  • Define an equivalence relation between sequences of binary digits.

\{u_n\}_{n=1}^\infty \equiv \{v_n\}_{n=1}^\infty if \exists i such that u_j = v_j, \forall j>i.

  • Bob chooses a unique representative (sequence) for each equivalence class.
  • Define a function n\{u\} such that the value at sequence $\{u\}$ is equal to the smallest i such that \tilde{u}_j= u_j, \forall j > i, where \tilde{u}_j is the class representative.

These are all definitions we need. Next comes the winning strategy.

  • Bob reorganizes the sequence into 100 rows: a_{1}, a_{101}, a_{201}, \cdots \\ a_{2}, a_{102}, a_{202}, \cdots \\ \cdots \\ \cdots \\ \cdots\\ a_{100}, a_{200}, a_{300}, \cdots
  • Bob randomly choose one row, say the 100th row.
  • For the remaining 99 rows, each row represents a sequence that Bob already knows. Therefore, he could look up in his ‘dictionary’, and figure out n\{row_1\}, n\{row_2\}, \cdots, n\{row_{99}\}. Bob picks the maximum of these 99 numbers, k.
  • Bob chooses to cover the kth number in the 100th row.
  • There’s 99% chance that n\{row_{100}\} is smaller than one of n\{row_1\}, n\{row_2\}, \cdots, n\{row_{99}\}. So for 99% chance, Bob can find out Alice’s answer by looking at the kth value of row_{100}‘s representative sequence.

The last step might need a little justification on your own, it should be rather straightforward. To conclude, Bob has a strategy that ensures 99% chance of winning, but he is also destined to a 50% chance of winning. He must be living in a ghost city!

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s