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?

August 20, 2019 11:46 am

Randomness has ontological implications in theology. I believe it is still important as Suppes argued in 1956 that we don’t understand the nature of probability.

“Because of the many controversies concerning the nature of probability and its measurement, those most concerned with the general foundations of decision theory have abstained from using any unanalyzed numerical probabilities, and have insisted that quantitative probabilities be inferred from a pattern of qualitative decisions.”

Studies in the Methodology and Foundations of Science: Selected Papers from …
By Patrick Suppes

Koslow’s suggests that our understanding is similar to Newton’s grasp of mass . . .

“Because of the many controversies concerning the nature of length (mass) and its measurement those most concerned with the general foundations of geometry (mechanics) have abstained from using any unanalyzed numerical lengths (masses), and have insisted that quantitative lengths (masses) be inferred from a pattern of qualitative information.”

from, Quantitativeness in Edoxus, Newton, Maxwell, in, “Philosophical and Foundational Issues in Measurement Theory”, edited by C. Wade Savage, Philip Ehrlich

2. August 20, 2019 12:07 pm

I remember learning of hashing algorithms in my early computer science education. Hash functions often produce a sort of random number in some range. I know they aren’t really random as clearly a hash function is algorithmic and in most applications needs to easy to compute. Still, it just fascinated me that something that was akin to shuffling the deck (loss of order) was helpful in keeping track of information (order regained). It seemed magical.

Later I learned about perfect hash functions which, for a given set of items to be hashed, is guaranteed to produce no collisions. More magic!

• August 21, 2019 3:20 am

Dear Paul Topping:

Thanks for your comment. Yes I agree that it is magical the way hashing works. I like the way you put it: Loss of order yields regain of order. Well said.

Best

Dick

3. August 20, 2019 9:20 pm

I have heard of few things about randomness in CS. Useless because P is BPP, useful because of volume approximation when polytopes presented appropriately and very powerful as in interactive protocols and communication complexity. For quantumness I have only heard more useful because of Shor and seemingly natural squareroot advantage and very powerful as in interactive setting. There seems to be no advantage of randomness in space setting but how about quantumness and space? I do not know if randomness or quantumness helps in space-time tradeoffs or parallel settings and I would suspect quantumness to help here.

• August 21, 2019 9:18 am

Good blog.

4. August 21, 2019 7:49 am

Pollock painted fractals: http://discovermagazine.com/2001/nov/featpollock

August 21, 2019 9:04 am

As someone who has followed chess and Go programming since the 1970s, I’m impressed by the idea of using randomness in (Monte Carlo tree search in) Go. I think it’s one of comp. sci’s great intellectual achievements. Everyone who thought about how to make computers play chess, from Turing on, pretty much came up with the right idea. We all failed miserably for Go. And then Remi Coulom figured out how to make MCTS work for Go, and the rest is history*.

(It apparently also works for Shogi, which is an interesting game in that unlike chess and Go, there’s no inevitably progress towards a result.)

Anyway, as someone who completely ignored randomness in the 20 years I did comp sci sorts of things, randomness is now really kewl.

*: Or will be when the current AI boom fizzles and we can see more clearly what we’re doing. (I have an all-but-thesis in AI, and I’m right about the current AI craze being essentially vacuous.)

August 21, 2019 10:49 am

I think one way to summarize one way randomness is used is to say “randomness helps when the enemy knows your source code.” That is, if you are playing an adversarial game and the opponent knows what strategy you are using it may give them an advantage. But adding randomness to your strategy can defuse this advantage.

One example of course is the case of two player zero-sum games of perfect information. Other examples are cryptography and interactive proofs (where the enemy is the prover). I think even random sampling in statistics can sort of be thought of in this way if you imagine the “enemy” is possible correlations between your method for collecting the sample and the variable you are trying to measure.

Thomas Schelling has also written that randomness in game theory can be seen as a way of turning a discrete set of payoffs into a continuous one.

• August 21, 2019 2:29 pm

Thanks, also DJL above, for the comments tying randomness to games. Regarding “when the enemy knows your source”, I have voiced my belief (as here) that a slightly randomized version of any of the top chess programs could hold a draw at least 20% against any strategy. For a randomized AlphaZero I would go as high as 50% in the draw rate—which would mean no strategy would out-rate it by more than about 200 Elo points after direct play against it.

August 21, 2019 2:25 pm

Another comment on theology . . . when you say, about games, “only makes sense when these actions are unpredictable. Random”, why do you also use this strategy, “Our secret was simple: do not play, do not gamble, do not lose.” Aren’t you kind-of assuming a deterministic, “will eventually lose” belief?