Session 1 — Computing with chance
“How many samples does it take to be right?”

The film is shown in class
It will be online here soon.
Transcript
Ulam’s problem
1946. The mathematician Stanislaw Ulam is stuck in bed with a serious illness. To pass the time, he plays solitaire: card games you play alone. Sometimes he wins, often he loses. And one question obsesses him: what is his chance of winning a game?
To calculate it exactly, he would have to go through every way of shuffling the fifty-two cards, and count the ones that lead to a win. But there are so many of these shuffles that their number is sixty-eight digits long. Check them all? No computer in the world could do it.
So Ulam has a very simple idea: instead of calculating, play. Play, say, a hundred games. Count the wins. Divide by a hundred: that’s the proportion of games won. It isn’t his exact chance, but an approximate value: an estimate.
This idea, play and then count, has become one of the most widely used computing methods in the world. It is used to price financial products, to measure the risk insurers carry, to track particles in nuclear reactors, and to draw the light in animated films. It is named after a casino in Monaco: the Monte Carlo method. Why a casino? We’ll come to that.
In this video, you will understand why this idea works, how many tries it takes before you can trust the result, and how to check it. Keep one question in mind: how many games did Ulam have to play to know his chance to within one percent? A hundred? A thousand? More? Write down your answer: we will check it.
A probability is a proportion
Let’s start with the simplest form of chance: a coin. Before you toss it, there’s no way to know whether it will land heads or tails. But we can say one thing: heads has one chance in two. That number, one half, or fifty percent, is called a probability. It’s a number between zero and one that measures how likely an outcome is: zero for impossible, one for certain.
Let’s toss it ten times. One question before we look: in ten tosses, what’s the chance of getting exactly five heads? Take a second.
Here are our ten tosses. Six heads, four tails. Not five. So is the coin cheating?
To find out, let’s look at every possible outcome. In ten tosses, you can get anywhere from zero to ten heads: eleven cases, one column for each. In each column, we stack the sequences that give that result. A sequence is the exact order of the ten tosses: heads, heads, tails, and so on. For zero heads, there is only one sequence: tails, ten times. For exactly five heads, you have to choose which of the ten tosses come up heads: two hundred fifty-two sequences. For six heads, two hundred ten.
In all: two possibilities per toss, ten times in a row, which makes one thousand twenty-four sequences, all equally likely. So the chance of getting exactly five heads is the share of sequences with five heads: two hundred fifty-two out of one thousand twenty-four. Only 24.6 percent, less than one time in four. Six heads: 20.5 percent. Four heads, the same. Six heads or four heads: between them, four times out of ten. So getting six heads is perfectly ordinary: our coin isn’t cheating.
Let’s check with an experiment. A computer can imitate these tosses for us: that’s called simulating. It plays ten thousand series of ten tosses, and drops each series into its column. Remember the colors: orange for what is calculated exactly; blue for what is simulated. The blue bars land right on the orange ones.
Now, one single long series, and let’s track the proportion of heads: the number of heads divided by the number of tosses. To the right, the number of tosses: each tick mark means ten times more. The height is the proportion. After ten tosses: 60 percent. After ten thousand: 50.28 percent. After a million: 50.005 percent. The more we toss, the closer the proportion gets to one half.
This is the law of large numbers: when you repeat an experiment a very large number of times, the observed proportion gets closer to the probability. As a formula: k, the number of successes, divided by N, the number of trials, gives the observed proportion, written p hat. The hat marks a measured value. As N grows, p hat gets closer to p, the true probability.
Watch out for a trap that almost every gambler falls into. People often believe that chance evens out: after a run of tails, heads must be due. That’s wrong: the coin has no memory. Look at the gap between the number of heads and the number of tails: it’s the height of this new curve. If chance evened out, this gap would come back to zero. It doesn’t: after a million tosses, there are ninety-four more heads than tails.
So why does the proportion settle down? Because this gap grows much more slowly than the number of tosses: its usual size follows the square root of that number. The square root of a hundred is ten, because ten times ten makes a hundred. The square root of a million is a thousand. A thousand out of a million: one thousandth, almost nothing. Chance doesn’t even out. It gets diluted. Remember this square root: it will come back.
And to toss a million coins, you don’t even need a coin. A computer can produce numbers that behave just like chance. Four lines of Python: we draw a million numbers between zero and one, we decide that those below one half are heads, and we print the proportion of heads. Answer: 0.500047. That’s exactly what simulating is: letting a machine play out chance for us, very fast and very often.
An area can be counted
A proportion is measured by counting. Here’s the trick that made the method famous: calculating, by counting, a number with nothing random about it. The number π. Take any circle, and divide the distance around it by its width, the diameter: you always get the same number. 3.14159, and digits that never end.
Take a square with sides of length one: its area is one. Let’s throw points into it at random, like darts thrown by a perfectly clumsy player: every spot in the square has exactly the same chance of being hit.
Let’s cut the square in two along its diagonal. Now, a question: what share of the points will land below the diagonal?
Half, of course: this triangle covers half the area of the square. We count one thousand five hundred eighty-two points out of three thousand two hundred: 49 percent. Here’s the rule that makes it all work: the share of the points that land in a region is roughly the share of the area that this region covers. And it reads both ways: counting the points is measuring the area.
Let’s replace the triangle with a quarter disc: the point of the compass in one corner of the square, and a radius equal to the side. We’ve known its area since ancient times. The area of a disc is π times the radius, times the radius. Here the radius is one: the whole disc would have an area of π, and our quarter, π divided by four. About 0.785.
So about 78.5 percent of the points should land in the quarter disc. Let’s count. Two thousand five hundred five points out of three thousand two hundred. Proportion: 0.783.
And now, here’s the twist. Let’s forget that we know π. The area of the quarter disc is π over four, and the points have just measured it: 0.783. So π over four is roughly 0.783, and π is four times that: 3.13. We have just calculated π simply by counting points that landed at random.
3.13 isn’t 3.14 yet. Let’s add points and follow the estimate: to the right, the number of points; the height is the value we find. Ten thousand points: 3.126. A million: 3.1405. A hundred million: 3.1415. The digits do arrive, but more and more slowly. Why so slowly? That’s the big question of this video, and the square root we met earlier will answer it.
Computing π with chance: the idea is an old one. In 1777, the naturalist Buffon publishes this problem: you drop a needle on a wooden floor whose boards are exactly as wide as the needle is long. What’s the chance that it crosses a crack, the gap between two boards? Answer: two divided by π, about 64 percent.
What is π doing on a wooden floor? The number of cracks crossed, on average, depends only on the length of the needle, not on its shape: straight or bent, each little piece keeps the same chances of crossing. So let’s bend a wire into a circle, as wide as a board. Wherever it lands, it crosses exactly twice. Now, the distance around it is π times its width: it is π times longer than the needle. So the needle crosses π times less often: two divided by π.
In 1812, Laplace turns the question around, just as we did with the quarter disc: drop lots of needles, and count. Here, out of four hundred eighty needles, three hundred five cross a crack. That proportion is roughly two over π. So π is roughly two times four hundred eighty, divided by three hundred five: 3.15. But counting by hand takes a long time: the idea will have to wait for computers.
An expected value is an average
So far, we’ve counted successes: heads or not heads, inside or outside. But often, the question isn’t: what chance? It’s: how much, on average? Take a die. If you roll it a very large number of times, what value will the average of your rolls head toward?
In the long run, each face comes up about one time in six. So the average of the rolls gets closer to the average of the six faces: one plus two plus three plus four plus five plus six, divided by six. 3.5. This long-run average is called the expected value. The name is misleading: nobody expects to roll a 3.5 with a die, it’s impossible! The simulation confirms it: after ten thousand rolls, the average is 3.509.
Everything we’ve just done fits into one formula: the formula of the Monte Carlo method. Let’s take it piece by piece.
X is the outcome of chance: the die, the coin, or, tomorrow, the price of a share. f of X is the number we look at in it: the dots on the die, a gain, a loss. E, for expected value: the long-run average of that number, the one we’re after. The wavy sign means: roughly equal. On the right, X one, X two, all the way to X N: N samples, that is, N outcomes produced at random. The big zigzag sign means: add up. We add up f of each sample, and we divide by N.
Read out loud, the formula says: the average we’re after is roughly the average of what we observe by simulating. That’s all. Even the proportion of heads obeys it: we write one for heads, zero for tails, and the average of those ones and zeros is the proportion. So a probability is an expected value like any other.
Let’s see why banks love this formula. A share is a small slice of a company, bought and sold on the stock market. Imagine a share worth a hundred euros today. A call option is a contract that gives you the right, but not the obligation, to buy that share in one year at a fixed price of a hundred euros.
If in one year the share is worth a hundred thirty euros, you buy it for a hundred and you make thirty. If it’s worth eighty, you don’t buy: you make nothing, but you lose nothing either. So this contract can only pay: it isn’t free. How much should you pay for it today?
Everything depends on the price a year from now, and nobody knows it. So let’s do as Ulam did: let’s imagine futures. Each blue line is one possible future for the price: day after day, the computer nudges it up or down, at random. The size of these jolts matches the usual swings of this share. People in finance call it volatility: here, 20 percent per year.
In each future, we compute what the contract pays, its payoff: the final price minus a hundred if that’s positive, zero otherwise. Then we take the average of these payoffs: it’s our formula, where X is a future, and f, the payoff. One last detail: this payoff only arrives in a year. Now, a hundred euros invested at 5 percent become about a hundred and five in a year: so a euro in a year is worth a little less than a euro today. We multiply the average payoff by about 0.95. This is called discounting.
With these sixty futures, we find 8.01 euros. But sixty is too few: sixty other futures would give a different result. With a million futures, the estimate settles down: 10.46 euros. And here’s the judge. In 1973, Fischer Black, Myron Scholes and Robert Merton found an exact formula for this simple contract: the Black-Scholes formula, which would earn a Nobel Prize. It gives 10.45 euros. The simulation lands on it, to within one cent. But when the contract gets more complicated, no formula exists any more. The simulation, though, keeps working.
Same idea for insurers. An insurer starts out with a reserve of money. Day after day, it collects premiums from its customers. Every now and then, it has to pay a claim, an accident or a fire, of unpredictable size. If one day its reserve drops below zero, that’s ruin.
What’s the probability of ruin? Let’s simulate ten thousand futures for this insurer, and count those where ruin happens: five hundred one. That’s 5.0 percent. For this simple model, an exact formula exists: it gives 4.9 percent. Here again, it’s an average: the average of a number that equals 1 when there is ruin, and 0 otherwise.
How many samples?
But 10.46 isn’t 10.45, and 5.0 percent isn’t 4.9. Where does this gap come from? Let’s go back to π. With a thousand points, we find 3.140. With another thousand points: 3.204. And a thousand more: 3.128. Our result changes every time: it is itself drawn at random! So how much can we trust it?
Let’s run the experiment on a large scale. Let’s estimate π with a hundred points, and do it again two thousand times. Let’s line up these two thousand estimates along an axis, each one above its value; those that fall into the same bin stack up. This is a histogram: the taller a bar, the more often that result occurs.
A bell curve appears, centered on π: most estimates land close to the true value, and big errors are rare. This bell curve isn’t special to π. It’s one of the deepest results in probability, the central limit theorem: the average of a large number of samples spreads out along this bell curve, around the true value.
The width of the bell curve is our error. Question: with four times as many points, four hundred instead of a hundred, what happens to the bell curve? Four times narrower? Twice as narrow?
Only twice. With a hundred points, an estimate is typically off from π by 0.16: that’s its typical error. With four hundred points: 0.08. With sixteen hundred: 0.04. Four times as many points, and the error is divided by two.
Why two, and not four? Remember the coin. Each sample is off, sometimes too high, sometimes too low. When we add them up, these errors cancel out, but only partly: a gap remains, and it grows like the square root of the number of samples. With four times as many samples, that gap doubles: the square root of four is two. But to take the average, we divide by four times as many. Two divided by four: the error is divided by two.
Hence the golden rule: the typical error equals sigma, divided by the square root of N, the number of samples. Sigma is the typical error of a single sample; it’s called the standard deviation. For π, a single point gives four if it lands in the quarter disc, zero otherwise: it is typically off from π by 1.64. With a hundred points, we divide by the square root of a hundred, ten: 0.16, the width of our bell curve. And to gain one digit, the error has to be divided by ten: a square root of N ten times bigger, so N a hundred times bigger. That’s why the digits of π arrived so slowly.
For students who want the exact statement of the central limit theorem, here it is, at the bottom of the screen. Everyone else can remember the rule: a hundred times more samples for one more digit.
Now for the guarantee. A bell curve always has the same shape. Let’s measure it with its own unit: the typical error. Within one typical error of the true value, we find about two estimates out of three. Within 1.96 typical errors: 95 percent. That’s where this number comes from, 1.96, which you’ll see everywhere. Ninety-five times out of a hundred, our estimate lands within 1.96 typical errors of the true value.
Let’s turn the sentence around. A distance reads both ways: if you live less than a mile from the station, the station is less than a mile from your home. In the same way, if our estimate is within 1.96 typical errors of the true value, then the true value is within 1.96 typical errors of our estimate. Now, the true value is unknown to us; the estimate, we know. So let’s draw this interval around the estimate: ninety-five times out of a hundred, the true value is inside.
A practical detail: sigma isn’t known in advance either. We measure it on the samples themselves. For our first thousand points, which gave 3.140, sigma is 1.64. Divided by the square root of a thousand, then multiplied by 1.96: 0.10. So we write: π is 3.14, plus or minus 0.10.
Let’s check the promise. Here are a hundred estimates of π, each with a thousand points, and their hundred intervals. The true value is the orange line. Ninety-six intervals contain it. Four miss it, in red. Such an interval is called a 95 percent confidence interval. Careful: π doesn’t move; it’s the interval that changes with each simulation. The 95 percent describes the method: it is right ninety-five times out of a hundred. With a single simulation, we don’t know whether we’re among the ninety-five or among the five. So, not a certainty, but a risk known in advance.
Let’s go back to the opening question. A game is a sample that equals one if it’s won, zero otherwise. For a sample like that, sigma is at most one half: that’s the case of one chance in two, the most uncertain one. With a hundred games: 1.96 times one half, divided by the square root of a hundred. About 0.10: Ulam would have known his chance to within ten percent, at worst. To get down to one percent, you have to divide the error by ten, so play a hundred times more: exactly 9,604 games. Was your answer close? No human plays ten thousand games of solitaire. But a machine can.
Why finance loves it
Still, one question should be bothering you. To measure an area, you don’t need chance: you can cover the square with a regular grid, ten rows of ten points, and count the ones that fall inside. In a square, that’s even more precise. So why bother with chance?
The answer is one word: dimension. To describe one future of our option, a single number is enough: the price of the share in one year. The futures line up along a line, and ten points cover it. With two shares, from two companies, a future is two numbers, like a point on a map: so far east, so far north. Ten values for one, ten for the other: a hundred points. With three shares, three numbers: a point in a room, height included. A thousand points. The dimension is the number of uncertain quantities it takes to describe a future. And each extra dimension multiplies the grid by ten.
Now, a bank holds shares in far more than three companies. A portfolio of fifty different shares means fifty dimensions: ten, multiplied by itself fifty times. A 1 followed by fifty zeros: ten to the power of fifty points. Roughly the number of atoms in the whole Earth. No computer will ever go through them all.
Chance, on the other hand, doesn’t try to fill the space. It draws complete futures, one by one: with fifty shares, one sample is fifty prices at once. Then one payoff per future, and the average. And the error? Sigma, over the square root of N. Sigma measures how far the payoffs stray from their average; N is the number of samples. The dimension isn’t in there. For the same sigma, a million samples give the same precision with one share or with fifty. That’s the real strength of the method.
This wall is the one Ulam and his friend John von Neumann ran into at Los Alamos, the American atomic weapons laboratory. They had to track neutrons, particles that bounce at random through matter. Each bounce adds uncertain quantities, a direction, a distance: so, more dimensions. And a neutron bounces dozens of times. So they simulate. In 1948, the first calculations are run on the ENIAC, one of the very first computers, with programs written by Klára Dán von Neumann, among others.
That leaves the name. This work is secret: the method needs a discreet name, a kind of code name. Their colleague Nicholas Metropolis suggests Monte Carlo: a nod to an uncle of Ulam’s, who used to borrow money from his relatives to go and gamble at the Monte Carlo casino. And the name fits. A casino doesn’t know what the next game will bring. But over millions of games, it knows what it will win on average. The method does the same: thousands of games of chance, for an average that is almost certain. In 1949, Metropolis and Ulam publish it under that name.
Still, the method has an Achilles’ heel: rare events. Picture one of those insurers that hold enough reserves for ruin to happen, someday, only about once in two hundred. Let’s simulate a hundred futures. How many ruins do you think we’ll see? Most often, none: that happens six times out of ten. And we would conclude, wrongly, that ruin is impossible.
With a thousand futures, we count six ruins: 0.6 percent. But the confidence interval says plus or minus 0.5 percent: the true value could be 0.1 percent just as well as 1.1 percent. In other words, we know almost nothing: everything rests on six futures. It takes a hundred thousand futures to get 0.49 percent, to within 0.04 percent; the exact formula gives 0.475 percent. And of those hundred thousand futures, more than ninety-nine thousand were of no use: ruin doesn’t happen in them. The rarer an event, the more samples it takes to see it often enough.
In a later session, we’ll see how to aim where it counts, to observe the rare event without waiting for it to happen.
What to remember
Let’s recap. First, a probability is a proportion: we repeat chance, and we count. Second, an expected value is an average, and an average can be simulated. Finally, the typical error equals sigma over the square root of N: every result comes with its confidence interval, and we know how right we are.
And all of this fits in seven lines of Python. We draw a million points in the square. We pick out the ones that land in the quarter disc. Their proportion, times four: that’s the estimate of π. Then the confidence interval: 1.96 times sigma, divided by the square root of a million. Result: 3.1407, plus or minus 0.0032. The true value, 3.1416, is right inside.
Predict, simulate, verify. That’s the whole method, and it’s the thread running through this course. In the next session, a question that sounds impossible: can we divide the error by thirty, without taking a single extra sample?
Subtitles (.vtt): English
