You may have heard of the "infinite monkey theorem". It states: if you take a monkey, give it a typewriter and an infinite amount of time, sooner or later it will type out the complete text of Hamlet.[1]
It's said that this theorem emerged during 19th-century debates about evolution. Proponents of evolution supposedly argued that human descent from apes, like other low-probability events, is possible – you just need to allow enough time.
I began my talk about low-probability events with this example at an informal seminar for graduate students at UCLA. I'll share this talk with you as well. My story will have several parts; the first part is dedicated to Buridan's principle.
A safety-critical system is one whose failure could result in death or serious harm to human health. Examples include nuclear power plants, airplanes, railway crossings, and pacemakers. In the aviation industry, the guidelines want death to be an extremely improbable failure condition and those are defined as having a probability on the order of 10−9 or less. So, a safety-critical system should be designed to cause no more than one death per billion hours of operation. Engineers work hard at this, calculating all these nanomorts per hour. When reading about this, a natural question arises – why can't the risk simply be reduced to zero? Is there really such a significant gap between 0 and 0.000000001?
Buridan's ass
It turns out this gap exists, and it's substantial. The problem is that the laws of classical physics are continuous. As Feynman said in the introduction to his famous lecture series: "All things are made of atoms – little particles that are in perpetual motion, attracting each other when they are a little distance apart, but repelling upon being squeezed into one another". The interactions between these atoms can be modeled with various laws. Atoms experience forces and move according to Newton's laws. They interact with the electromagnetic field, which also interacts with itself according to Maxwell's equations. All these laws share one property – they are continuous. If we continuously move some parameter, such as the initial position of an atom, its position after 10 seconds will depend on this parameter continuously.
From this simple observation follows the paradox of Buridan's ass. The French philosopher Jean Buridan reportedly claimed that if a hungry donkey is placed at an equal distance from two haystacks, it won't be able to choose which stack to approach and will eventually die of hunger[2].
In the equal distances formulation, the paradox is easily resolved. Buridan's ass, naturally being French, would instinctively follow right-hand traffic rules and go to the right haystack. But there's a more serious problem!
Theorem 1: If for some initial position the donkey ends up at the left haystack after a minute, and for some other initial position it ends up at the right haystack, then on the interval between these positions there exists an initial position of the donkey for which after a minute it won't end up at either haystack.
Proof: the donkey is a physical mechanism subject to the laws of classical physics. Therefore, the position of the donkey after a minute depends continuously on its initial position.[3] If for any initial position the final position were at either the left or right haystack, then there would exist a nonconstant continuous function from the interval [0,1] to a space of two points {0,1}, which is impossible according to the intermediate value theorem. Q.E.D.
I find this statement astonishing! An application of the intermediate value theorem to philosophy! I'm surprised that few people have heard of it, even among my mathematician friends with the broadest horizons. We can extend this statement and show that there is an initial position for which the donkey will starve to death. This position doesn't have to be in the middle, as Buridan suggested. But Buridan correctly grasped the essence. If the donkey has an instinct to choose the right pile more eagerly, then the equilibrium point will be to the left of center, where this instinct is precisely balanced by the natural lazy tendency to go to the nearest pile.
Addressing objections
Around this point in text you probably have some objections. You are definitely not alone! A lot of people voice objections [LW(p) · GW(p)], many of them later correct themselves. Write yours in the comments to be disproved!
Apparently, Theorem 1 first appeared in Leslie Lamport's (well-written) paper "Buridan's Principle". He notes that people, upon hearing about Buridan's principle, tend to propose mechanisms to circumvent it[4]. Usually, they suggest that the donkey, in a situation of indecision, should take some action. Go to the right haystack. Don't drive onto the crossing. Calculate whether there is more or less than a minute until the train arrives. But this simply pushes the decision one step back. The donkey must determine whether it is "in indecision". And this decision is also impossible to make in finite time.
All proposed mechanisms, of course, don't work if they don't challenge the initial premises of the theorem. And the premises are quite weak – we only assumed that: physics is classical, that tme and space are continuous, and that there are initial positions for which the final positions end up in different components. And if these premises are true, then no mechanism whatsoever, with doors, gears, coins, magnets, or electronics, can resolve the paradox.
This theorem shows that complete safety is impossible; there can only be a very small probability of danger. Even the probability of starving to death surrounded by food is not zero. What can be said about other unsafe places – traffic lights or railway crossings? Depending on the initial speed and position of the car, within a limited time before a train approaches, the driver must decide whether to cross or to wait until the train passes. As you can understand, here the driver must make a choice between two discrete options in a limited time. And if the initial position of the car and the gears in the driver's head are unfortunate, they will be hit by the train. The merciless intermediate value theorem states that for any configuration of gears – that is, for any principle the driver might use – there's a chance they will be hit by the train.
For example, a barrier at a railway crossing doesn't guarantee one hundred percent safety but merely postpones the problem one step. If a driver is in an indecision about whether to drive under the barrier, they may fall into Buridan's trap and be crushed by the barrier when it lowers. Or they will remain between the barriers. And then an accident with the train will occur.
On February 3, 2015, at 6:26 PM, a car driven by a 49-year-old woman was traveling northwest on Commerce Street in Valhalla, New York, toward a railroad crossing. The driver entered the crossing area and stopped. Then she moved further beyond the boundary and stopped near the railway tracks. The crossing warning system activated, and the barrier came down, hitting the rear of the car. The woman got out of the car, inspected the barrier, then returned to the car and drove onto the tracks...
Jacobs speculates:
There are many ways to explain this driver’s behavior. Perhaps she felt she was already committed to crossing the tracks; perhaps she was just running on autopilot and did not comprehend the danger facing her. Buridan’s principle was not the only, or perhaps even the determining factor in this accident. But the driver’s behavior does look a bit like what would happen if she were having trouble judging whether she had enough time to cross.
A more familiar and perhaps more plausible example of the Buridan phenomenon is the decision of whether to stop or speed through a traffic light that has just turned yellow. It’s easy to waffle between the two options, only coming to a conclusion by slamming on the brakes or screeching through the intersection, risking running a red light. Again, there are other interpretations of this behavior, but the difficulty of figuring out in time whether you have enough time is a real one.
Literature on Buridan's paradox
The idea of Buridan's paradox is so incredible that you can only believe it if someone very authoritative tells you about it. For example, if you read about it in a children's book. For instance, in the wonderful book "What is Mathematics?" by Courant and Robbins, the following problem by H. Whitney is described.
Suppose that over some finite time interval a train travels along a straight line segment from station A to station B. It is not assumed that the motion occurs at a constant speed or with constant acceleration. On the contrary, the train can move in any way: with accelerations, decelerations; even instantaneous stops or partial reverse movements before eventually arriving at station B.
But one way or another, the train's movement throughout the entire time interval is assumed to be known in advance; in other words, a function s=f(t) is given, where s is the distance of the train from station A, and t is the time counted from the moment of the train's departure. A solid heavy rod is attached by a hinge to the floor of one of the cars, which can move without friction around an axis parallel to the axes of the cars, forward and backward—from floor to floor. Let the train's movement be such that, having touched the floor, the rod will subsequently remain lying on it, that is, it will not "bounce" up again.[5]
The question is as follows: is it possible at the moment of the train's departure to place the rod in such an initial position, i.e., to give it such an angle of inclination, that throughout the entire journey it does not touch the floor, being subject only to the influence of the train's movement and its own gravity?
As you might guess, this is a special case of Buridan's principle, and so the required initial position exists. The book provides a solution that, naturally, uses the intermediate value theorem. But then the reasoning becomes more interesting from a mathematical point of view! In an exercise, the authors ask to generalize the statement to the case when the train moves along an arbitrary curve in a plane, and the rod can fall in any direction, i.e., the rod has two degrees of freedom.
If the rod can rotate on the hinge not like an elbow but like a shoulder, there is still an initial position in which the lever will not fall during the entire trip. However, we still need the condition that, once fallen, the rod will not rise again.
The key point of the proof is a lemma from the proof of Brouwer's fixed point theorem. It states that there is no mapping from a disc to its boundary that maps all boundary points to themselves. Specifically, we need a strengthening that allows the restriction of the mapping to the boundary to be homotopic to the identity mapping. This can be proven directly by topological reasoning, or one can use the machinery of algebraic topology and calculate homologies, arriving at a contradiction. Surely other theorems from algebraic topology can be turned into theorems about the impossibility of guaranteeing decision-making in finite time in some complex topological configuration space.
In Lamport's paper, the reasoning about Brouwer's theorem is presented in connection with another configuration. In the chapter "Flying asses[6]", Lamport explains why an airplane cannot guarantee avoiding even a stationary balloon in finite time.
Lamport, as far as I understand, was most interested in methods of combating Buridan's paradox in electronics. He worked on solving the arbiter problem – devising a way to determine which of two signals arrived first. In the "Computer asses" chapter, he discusses metastability in electronic computer components. As we know, zeros and ones run inside a computer. At the level of electrical circuits that make up the computer, this means that the voltage at the output of all components in the computer is either 0 volts or 5. There are various electronic components that take as input the outputs of other components and, according to some rules, produce a new voltage value, which will also be 0 or 5 volts. For example, this is done by logical gates AND, OR, NOT, and these gates are sufficient to build a computer. You can literally do this in games like Nandgame and Turing Complete.
So, if you apply the right potential difference between 0 and 5 volts to the inputs of an AND or OR gate, according to the intermediate value theorem, you can achieve any output between 0 and 5 volts. And this incorrect state will propagate further through components into the computer's brain. This state is called metastability. In a properly constructed computer, metastability usually doesn't penetrate too far and fades out after a few cycles. But Buridan's principle says that by properly selecting the output of an external computer device, you can drive the computer crazy. Moreover, external devices will sometimes produce such outputs even without malicious intent, because pressing a key cannot instantly transition the output from 0 to 5 – in a continuous world, the voltage at the output rises gradually and passes through a metastable phase.
Why don't we encounter Buridan's principle every day? Why isn't such a powerful principle known to everyone from childhood and not even taught in university mathematics programs? The answer is that Buridan's paradox usually occurs with exponentially small probability!
Exponentially small probability
Consider the simplest model of two people trying to pass each other in a corridor. Two people are walking toward each other and realize they will collide. They can pass either by "left sides" or by "right sides". Let's temporarily move away from the continuity inherent in Buridan's paradox and say that people make decisions in steps. At each step, a person has a 50% probability of moving to the right, and a 50% probability of moving to the left. If people make asymmetric movements, they have thus agreed on which side to pass. If they make symmetric movements, they take another random step, until they get lucky.
Let the step time be Δt, then over time t, tΔt steps will occur, and they will not be able to make a decision in this time with probability 2−tΔt. If we take Δt as the average human reaction time, 0.2 seconds, then in one second, people will not be able to pass each other in 132 cases, in 2 seconds with a probability of 11024, and they will need 10 seconds in only 10−15 cases. It's not surprising that none of us has met a person in life whom it's impossible to pass, like your own reflection in a mirror. And even more so, no one has died of hunger because of this, like the poor imaginary donkey. The "reaction time" of a tossed coin or a balanced rod is on the order of fractions of a second. Due to such quick reactions, coins, unless they fall into a crack in the asphalt, eventually stop rolling on their edge and choose a side to fall on.
The exponential nature of probability might explain why most accidents happen when one of the drivers is drunk. If two drivers at an intersection are trying to solve the arbiter problem in limited time t, and due to intoxication the reaction time Δt has doubled, then the exponent in the accident probability is halved. If in a normal situation the accident probability was 10−12 or one in a trillion, then with doubled reaction time and unchanged movement speed, the probability becomes 10−6 or one in a million – much riskier!
Computer reaction times are much shorter than human ones. Therefore, metastability inside computers usually lasts only a few nanoseconds, and external inputs to the computer undergo a brief stabilization "quarantine" before being used in calculations.
Final remarks
In quantum mechanics, there are laws that violate continuity. Nevertheless, low-probability events manifest themselves even more vividly there, and quantum mechanics cannot resolve Buridan's paradox as shown in the Lamport's paper.
Finally, I'll tell you about the fate of paper. Due to its paradoxical and implausible nature, Science reviewers were divided on whether it was a paper of great philosophical importance or an elaborate prank. Nature reviewers dismissed this paper, proposing mechanisms to resolve the paradox. Charles Molnar, who noticed this paradox independently, said that his paper was rejected by a reviewer on the grounds that, if this problem existed, it would be important enough for all experts in electrical engineering to know about it. And the reviewer was an expert and had not heard of the problem, therefore the problem didn't exist.
In the next post, we'll discuss when low-probability events do occur. When a computer confuses pandas and gibbons, and a superhero loses in an unequal battle with an ordinary pole.
In 2002, researchers from Plymouth University received a £2,000 grant to study the literary creativity of monkeys. The monkeys wrote only 5 pages, mostly consisting of the letter S. Then the alpha male began hitting the keys with a rock, and other monkeys followed his example, defecating on the typewriter. The typewriter ultimately jammed.
Aristotle cited the assertion that "a man, equally hungry and thirsty, and placed between food and drink, must necessarily remain where he is and starve to death". However, he cited it as an example of an absurd sophistical idea while Buridan treated it seriously.
Why should this function be continuous? Technically, for the examples I mentioned (Newton's laws of motion, Maxwell equations) we are given an explicit system of ordinary differential equations. We need an assumption that the differential equations of our system are Lipschitz in all the variables with the Lipschitz constant Lf. It is usually true for the equations people use to describe the world on a basic level. Then we utilize a Picard–Lindelöf theorem to show that the solution to the system exists, but its proof actually gives us more – it shows that the state of the system at time t is continuous in the initial conditions and even Lipschitz in space, where the Lipschitz constant is expontial in t and Lf. For a formal proof see the paper "Why You Can't Build an Arbiter".
The last sentence is not in the book, but it is needed. Otherwise the problem becomes incorrect as it will permit a case when the continuous map is constant.
