The von Neumann min-max theorem showed that every finite zero-sum two-person game has optimal mixed strategies. More formally, let A be the payoff matrix of a game, then

_{x}min

_{y}x

^{T}Ay = min

_{y}max

_{x}x

^{T}Ay

Andrew Yao used the min-max theorem to prove what we now call the
*Yao Principle*: The worst case expected runtime of a randomized
algorithm for any input equals best case running time of a
deterministic algorithm for a worst-case distribution of inputs.
The Yao principle has proven invaluable for proving upper and lower
bounds for deterministic and probabilistic algorithms.

How can you get a fair coin by flipping a coin of unknown bias? You
use the *von Neumann coin-flipping trick*: Flip the biased
coin twice. If you get heads then tails output HEADS. If you get
tails then heads output TAILS. Otherwise repeat. This
procedure will output HEADS or TAILS with equal probability and if the
bias is not too close to zero or one the expected number of
repetitions is relatively small.

The von Neumann coin flipping trick is the first in a long line of research in complexity extracting random bits from weak random sources.

John von Neumann passed away February 8, 1957 in Washington, DC.

## No comments:

## Post a Comment