Solution: ‘Perfect Randomness’

In last month’s Insights column, we explored randomness in mundane objects such as a combination bicycle lock and a hexagonal jigsaw puzzle, before debating the philosophical underpinnings of randomness and whether perfect randomness exists in the world. It was wonderful to see so many illuminating comments from readers. Let’s look at the solutions to the puzzles before enjoying those comments.

Puzzle 1: Random Combinations

This puzzle was originally stated as follows:

Consider a simple combination bike lock like the one shown in the picture. It has three rotating discs, each of which has 10 digits embedded in numerical order. When the three discs are rotated to produce the set combination — 924 — the lock opens. When you want to lock it again, you have to scramble the digits so that they are far away from the set combination. But what does far away mean in this context? If you move each disc the maximum amount, which is five positions away, you get the number 479. But it would be easy for a tinkerer to find this position by accident, simply by moving all five discs in sync and seeing if the lock opened. Imagine that the tinkerer has enough time to try five possible combinations. In each instance, our potential thief tries out the lock after doing each of the following operations:

1. Turning a single disc a random amount.
2. Grabbing hold of any two discs and turning them some random amount in sync.
3. Grabbing hold of all three discs and turning them some random amount in sync.
4. Turning two discs different amounts.
5. Turning all three discs different amounts.

Our puzzle question is: If the code to open the lock is 924, what set of scrambled numbers is most resistant to this random tinkering, and how many such combinations are there? What’s the probability that the code will be found?

This problem was stated somewhat ambiguously, and in response to reader comments I clarified that the thief turns the lock back to its initial state after every step. Abhinav Deshpande nicely analyzed this puzzle under the assumption that the “random amount” in the first three actions is not zero, and the “different amounts” in actions 4 and 5 are necessarily unequal. However, as Xin Yuan Li pointed out, under the latter assumption, if we set the lock such that two of the discs are turned the same amount and the third one is turned a different amount, resulting in a combination such as 036, then the thief will never succeed in cracking the lock, because none of the actions cover this configuration.

The solution below is based on a clarification I made that in actions 4 and 5 the discs are not necessarily turned the same amount. Also, we will assume that in actions 1 to 3, it is possible for the thief to turn the specified discs all the way around (a turn of 10 — or zero — digits, returning the disc or discs to the initial position). With these assumptions in place, let’s calculate the probability of each of the thief’s actions. One thing to note is that any action that the thief may perform randomly on a disc to reach a particular number is potentially reversible by performing a complementary, equiprobable action on the same disc. Thus, there is a probability of 1 in 10 that moving the leftmost disc randomly will get us from 924 to 624, and there is also a 1 in 10 probability that moving the same disc randomly will get us back from 624 to 924. This is true whether we move one, two or all three discs randomly. So in order to determine how many scrambled positions will allow the thief to solve the lock by doing a particular action, we can conveniently start from the set position (924) and count how many three-digit combinations can be reached with that action.

1. Starting from 924 and turning a single disc, you can reach three-digit combinations of the form x24, 9x4 and 92x, where x represents any of the 10 digits. There are 10 of each of these. However, the original combination 924 is redundantly included in the last two forms as well, so there are a total of 10 + 9 + 9 = 28 such combinations. If the lock is scrambled to any of these combinations, the thief has a 1/28 chance of opening the lock with this action.
2. Turning two discs in sync makes possible combinations of the form 9##, #2# and ##4, where the two # signs represent the amount (the same for both) that those two discs are turned from their original setting. As above, there are 28 such combinations, again giving a 1/28 chance of success.
3. Turning all three discs in sync allows access to the 10 combinations resulting from global turns of 1 to 10 digits — 035,146, 257, 368, 479, 580, 691, 702, 813 and 924 — giving a 1/10 chance of success.
4. Turning two discs randomly, but not necessarily the same amount, gives access to all combinations with a 9 as the first digit (numbers 900 or greater), all combinations with a 2 in the middle (x20s), and all combinations that end in 4. There are 100 of each of these. However, 10 of the x20s were already counted with the 900s, and there are also 10 combinations ending in 4 in the 900s and nine others among the x20s. So the total number of combinations is 300 − 10 − 19 = 271 for this step, with a 1/271 chance of success.
5. Turning all three discs at random allows access to any three-digit combinations, each time with a 1/1,000 chance of success.

Updated on September 30, 2019: The following paragraph has been modified to incorporate a correction pointed out by the reader “cornflower”:

There are two sets of “safe” numbers that are most resistant to the thief’s tinkering. Both of these sets are impervious to the first four actions of the thief. They can only be found by the thief on the fifth action, for which, as we saw above, the probability of success is 1/1,000. As Abhinav Deshpande and others noted, you can reach the first set of numbers most resistant to the thief’s tinkering by turning each of the discs different amounts, with none of the discs remaining in the original position. There are 9 × 8 × 7 = 504 such positions. The other set of safe numbers can be reached by rotating two discs in sync a nonzero amount and rotating the third disc by a different nonzero amount. As cornflower states here, “that’s another 3 x 9 x 8 = 216 combinations, making for 720 in total.” Thus, there are 720 combinations you could scramble your lock to that are safer than the rest.

Puzzle 2: From Randomness to Order in Puzzles

Here’s the original question:

Consider solving a puzzle on a hexagonal grid — a honeycomb, similar to the graphene we played with in our last column. The picture on the puzzle consists of a twisting vine. Since the pattern is repeating and self-similar, you cannot be absolutely sure that two neighboring pieces belong together even though they seem to fit visually. In fact, let’s say that for each edge of a given piece, there are three possible pieces that could fit with it. So when two pieces fit together, your confidence that their arrangement is correct can only be 33.33%. However, if you can find another piece that fits with both of your connected pieces, sharing an edge with each, your confidence that this arrangement is correct will be reinforced. Let’s try to quantify how much.

1. You find three pieces that appear to fit together without obvious misalignment in the vine pattern across the shared edges. What is the measure of your confidence that this arrangement is correct?
2. You find a central hexagonal piece surrounded by six others, and they all seem to fit with one another. What’s the measure of your confidence in the correctness of this pattern?

The third part of this puzzle question is open ended and is an attempt to quantify the above difference. Can you come up with a measure of the degree of completeness of a partially solved puzzle? Your method should be able to assign a number between 0 and 100 to any partially completed 10-by-10 hexagonal puzzle. The number should represent a degree of completeness that roughly correlates with the proportion of the final solution that you would expect to be correctly represented thus far.

Abhinav Deshpande answered the first two questions as follows:

1. For three tiles in a triangle-like orientation, we have p = (2/3)³ since there are three edges that can be deleted, and each edge is deleted with probability 2/3. This gives 1 − p = 0.7037, i.e. 70.37% confidence.
2. For a hexagonal arrangement, there are 6 + 6 = 12 edges that can fail, giving 1 − p = 1 − (2/3)¹² = 0.9923 or 99.23% confidence.

Using these confidence numbers, we can set up a simple measure based on the sum of the confidence values of the pieces completed, yielding 100% for the finished puzzle, as follows: Take all completed clusters of two or more connected pieces. Add up the amount of confidence in each individual piece. Thus, for a cluster of three pieces sharing a vertex we get 3 × 0.7037 = 2.11%, and for a completed hexagon we get 7 × 0.9923 = 6.95%. A partially completed puzzle that has three clusters of three pieces and one completed hexagon will thus score 6.95 + 2.11 + 2.11 + 2.11, giving a score of 13.3%. On the other hand, if you have two completed hexagons, your score is 6.95 + 6.95 = 13.9%, even though you have two fewer pieces placed in the second case.

Deshpande took this idea to another level, proposing a measure using logarithms and connecting it to the concept of entropy, which, as he states, is a natural measure of disorder and randomness. His measure for a 10 × 10 grid is n − 100 × (log m)/(log 100), where m is the number of alternative layouts, and n is the total number of tiles already placed. You can read his description of the various advantages of this measure here.

Puzzle 3: Is Perfect Randomness Possible?

The prevailing view is that quantum physics is based on intrinsic, objective and perfect randomness. I invited readers to give their opinions on this philosophical puzzle by joining team B (in the spirit of Niels Bohr) or team E (in the spirit of Albert Einstein). Team B accepts the objective randomness of the quantum world, whereas team E believes that physical randomness is a logical impossibility that reveals our ignorance of deterministic causal events in the sub-Planckian realm. Readers engaged in a spirited debate, with about equal numbers going to bat for each team. Thank you to everyone who contributed. I summarize the key points of the discussion below and present some of my own arguments for the Team E viewpoint.

RRG nailed my motivation for proposing this debate, writing:

In quantum mechanics, if we consider the standard double slit experiment, we can’t predict where any individual particle will hit the screen, but we can predict the probability of where it will hit the screen. And these probabilities can be extremely accurate and reliable. This reliability and accuracy of probabilities is significant evidence that something is causing it.

It is analogous to thermodynamics. We can measure the temperature in a room very accurately without knowing what each molecule of air is doing. Similar to the probabilities in quantum mechanics, the temperature emerges from a deeper level of physics.

My thoughts exactly! Why does a particular particle passing through a double slit impinge on the detector at, say, the upper left of the screen, instead of the lower right? Some causal chain of events (perhaps subspace quantum gravity mass-energy fluctuations) must have caused this particular choice of location in this particular instance. If that’s the case, quantum randomness is not a perfect, objective and magical part of the universe, but a consequence of our ignorance of the underlying physics, just as classical randomness is.

Granted, as Mark Thomas observed, the probability space determined by Planck mass-energy may be huge. It might be large enough to achieve close to perfect randomness in the mathematical Kolmogorov sense (thank you, Ruslan Ciurca, for the link to your description of Kolmogorov complexity and randomness). But if that’s the case, the Schrödinger equation is simply an approximate, ensemble equation and should not be treated as sacrosanct, nor should it form the basis for the currently popular “many worlds” interpretation based solely on considerations of mathematical simplicity. This latter approach has been championed by the physicist Sean Carroll.

Rob McEachern took exception to my statement: “If you knew all the forces that were acting on a flipped coin or a rolled die, you could, with the requisite computing power, predict what the final outcome would be.”

McEachern wrote:

That statement is false. You must also know all the relevant initial conditions. And therein lies the problem. In any complex situation, the information content of the initial conditions, is vastly greater than the information content of the forces, or laws of nature. Consequently, it is vastly more difficult (often impossible, even in principle) to acquire the necessary information regarding the initial conditions, than it is to acquire perfect knowledge of the laws.

I agree that it is impossible to acquire perfect knowledge of initial conditions to infinite decimal places. But I think most physicists would agree that it is possible to achieve the relevant knowledge with the accuracy required for something like a coin flipped indoors, and therefore to predict its outcome in most instances. Of course, this may not be possible if a hurricane-force wind burst into the room and literally initiated chaos. Now, it may be that the aforementioned Planck mass-energy fluctuations are indeed like hurricanes that constantly sow chaos and that this is the true cause of quantum randomness. But even then, in principle, there is a deterministic causal chain. Team E would argue that we’re just ignorant about the details.

As with the other two questions, Abhinav Deshpande gave a superb, balanced, exhaustive and well-reasoned description of the current state of the art in this field, with references to some very good articles. Deshpande correctly states, “I don’t think the founder of relativity was comfortable with [nonlocality] either (even if the nonlocality doesn’t actually permit information transfer faster than the speed of light).” That’s true, but remember that Bell’s theorem was proved a decade after Einstein passed away. Faced with the strong experimental confirmation of the Bell inequality, the modern Team E has no choice but to modify Einstein’s original views and accept that nonlocality is a fact and that “spooky action at a distance” does happen. That means it’s possible that there are supraluminal or extra-spatial connections among the components of an entangled quantum object even though external information transfer is limited by the speed of light as relativity dictates, and the nonlocality never leaks out into the open.

Here’s a vivid image that I have come across: Imagine a lake whose surface is opaque. In it a huge wooden elephant, almost as large as the lake, floats upside down, its four legs sticking up like pillars at the four corners of the lake, while its body lies below the surface where you can’t see it. You initially think that the four pillars are independent objects. But then you find that their movements are perfectly correlated — in fact, entangled. In the same way, entangled particles form a single entity that can span the entire universe, with an internal connection that may be supraliminal or extra-spatial. Related to this is a fascinating idea known as ER = EPR, the cryptic conjecture by the brilliant theoretical physicists Juan Maldacena and Leonard Susskind. The idea is that entangled particles (EPR) are connected by a wormhole, the Einstein-Rosen (ER) bridge. This was originally proposed in the context of black holes, but perhaps it is true for all entangled particles, as I have discussed in a previous Insights puzzle. As Bohm’s theory demonstrates, determinism and quantum mechanics can certainly coexist and defy locality with internal supraluminal connections, without the need for objective randomness.

That’s all for now, but we are not done with randomness yet. This month’s prize goes to Abhinav Deshpande. Many thanks to all who contributed, and see you next month for new Insights.