Our Trip To Monte Carlo

Gödel’s Lost Letter and P=NP 2019-08-20

Why does randomness help?

Kathryn Farley is my dear wife. She and I are currently on a cruise through the Mediterranean. Our trip started in Barcelona and is stopping daily at various cities as we journey to Rome. “Tough duty,” but we are trying to enjoy it.

Today I wish to talk about our visit to Monte Carlo.

Our ship, the Encore, just docked there Sunday. The day was warm and clear, and we spent some time exploring the city. We did manage to avoid losing any money at the famous casino. Our secret was simple: do not play, do not gamble, do not lose.

Over lunch I started to explain to Kathryn why Monte Carlo is an important city for complexity theorists. I felt a bit like we were at a theory shrine.

Why Randomness Helps

Indeed. I realized that it is not so simple to explain why randomness helps. Kathryn has a Ph.D in theatre. She is smart, is a member of Mensa, but is not a complexity theorist. How do I explain that randomness is powerful? Indeed.

I started to explain, but my examples were lame. I think she got the main idea, but I also think that I did not do a great job. Russell Impagliazzo has a nice explanation on the role of randomness—I wish Russell had been there to help explain randomness to Kathryn.

After lunch I started to think more about the role of randomness. I looked at our friends over at Wikipedia and discovered they had a pretty good page. Some reasons are:

${\bullet }$ Games

Randomness was first investigated in the context of gambling. Dice, playing cards, roulette wheels, all have been studied by those interested in gambling. Clearly, betting on the roll of dice, deal of cards, or spin of the wheel, only makes sense when these actions are unpredictable. Random.

${\bullet }$ Political

Randomness is often used to create “fairness”. For example, in the US and UK, juror selection is done by a lottery.

${\bullet }$ Science

Monte Carlo methods in physics and computer science require random numbers.

${\bullet }$ Cryptography

Random keys for encryption algorithms should be unpredictable. Random. Otherwise, they can be guessed by others. The password “password” is usually not allowed.

${\bullet }$ Arts

Kathryn is interested in the arts: in plays and in painting and other fine arts. Some theories of art claim that all art is random. One thinks of artists like Jackson Pollock with his famous drip paintings. He was a major player in the abstract expressionist movement.

Pseudo or True?

Ken has been paying intensive devotions at the same shrine. As he wrote in the previous post, he has been conducting millions of randomized tests of his new chess model.

Why random? What he needs to do is show that his model will not tend to “cry wolf” by giving a too-high ${z}$ -score to a set of games in a tournament by an honest player. He wants to show that his model is equally tempered no matter the rating of the player. So he runs trials at different rating levels ranging from Elo 1000 for novice players to Elo 2800 which is championship level. To show that the ${z}$ -scores given by his model conform to a normal bell curve, he needs to do 10,000s or 100,000s of tests at each level.

The problem is there just don’t exist enough games. Most large tournaments give only the games played on their “top boards” which use special auto-recording equipment, and the losers on those boards in one round may play on lower boards in the next round. Thus out of about 60,000 player-tournament pairs Ken can track each year, most are only partial samples. So what Ken does is generate “synthetic players” by randomly taking subsets of (say) 9 games—from his data set of 1,000 or so games for each level—and randomly choosing white or black for each game. This is a common resampling technique, and it uses Monte Carlo.

Ken uses pseudo-random generators (PRGs). He starts a C++ library PRG on a seed ${s}$ based on the current time. The fact that the choices are deterministic once ${s}$ is given might allow him to reproduce an entire run exactly (after a model tweak) by preserving the ${s}$ it used. This is a paradox: we might want our “random” bits to be deterministic. Monte Carlo with predestined loaded dice.

From time to time on this blog we have mused about what a world without randomness or with reduced entropy would be like. We were struck a few weeks ago when the noted physics blogger Sabine Hossenfelder wrote about “superdeterminism.” That post provoked a few hundred comments in her blog, as did her post last week on the quantum measurement problem—including long exchanges with Peter Shor. Ken and I don’t know which side to take, but I can say that the side of a ship is a great place to think about possible real effects of these differences.

Open Problems

What is your take on randomness? Do you employ it? How “true” do you need it to be?