WEBVTT

1
00:00:01.000 --> 00:00:06.740
1946. The mathematician Stanislaw Ulam
is stuck in bed with a serious illness.

2
00:00:06.780 --> 00:00:12.020
To pass the time, he plays solitaire:
card games you play alone.

3
00:00:12.440 --> 00:00:15.060
Sometimes he wins, often he loses.

4
00:00:15.100 --> 00:00:19.700
And one question obsesses him:
what is his chance of winning a game?

5
00:00:20.253 --> 00:00:24.473
To calculate it exactly, he would have
to go through every way of shuffling

6
00:00:24.513 --> 00:00:28.513
the fifty-two cards,
and count the ones that lead to a win.

7
00:00:28.853 --> 00:00:31.893
But there are so many of these
shuffles that their number

8
00:00:31.933 --> 00:00:34.673
is sixty-eight digits long.

9
00:00:35.093 --> 00:00:39.213
Check them all? No computer
in the world could do it.

10
00:00:40.191 --> 00:00:44.871
So Ulam has a very simple idea:
instead of calculating, play.

11
00:00:44.911 --> 00:00:47.091
Play, say, a hundred games.

12
00:00:47.131 --> 00:00:52.051
Count the wins. Divide by a hundred:
that's the proportion of games won.

13
00:00:52.091 --> 00:00:56.551
It isn't his exact chance,
but an approximate value: an estimate.

14
00:00:57.277 --> 00:01:00.817
This idea, play and then count,
has become one

15
00:01:00.857 --> 00:01:04.397
of the most widely used
computing methods in the world.

16
00:01:04.437 --> 00:01:09.337
It is used to price financial products,
to measure the risk insurers carry,

17
00:01:09.377 --> 00:01:14.537
to track particles in nuclear reactors,
and to draw the light in animated films.

18
00:01:14.897 --> 00:01:19.737
It is named after a casino in Monaco:
the Monte Carlo method.

19
00:01:20.177 --> 00:01:23.037
Why a casino? We'll come to that.

20
00:01:24.416 --> 00:01:27.716
In this video, you will
understand why this idea works,

21
00:01:27.756 --> 00:01:33.696
how many tries it takes before you can
trust the result, and how to check it.

22
00:01:33.736 --> 00:01:38.876
Keep one question in mind: how many games
did Ulam have to play to know his chance

23
00:01:38.916 --> 00:01:40.616
to within one percent?

24
00:01:40.656 --> 00:01:43.036
A hundred? A thousand?

25
00:01:43.076 --> 00:01:46.756
More? Write down your answer:
we will check it.

26
00:01:47.985 --> 00:01:51.785
Let's start with the simplest
form of chance: a coin.

27
00:01:51.825 --> 00:01:56.125
Before you toss it, there's no way to know
whether it will land heads or tails.

28
00:01:56.165 --> 00:02:00.385
But we can say one thing:
heads has one chance in two.

29
00:02:00.745 --> 00:02:05.405
That number, one half, or fifty percent,
is called a probability.

30
00:02:05.445 --> 00:02:10.125
It's a number between zero and one
that measures how likely an outcome is:

31
00:02:10.165 --> 00:02:13.765
zero for impossible, one for certain.

32
00:02:14.359 --> 00:02:16.439
Let's toss it ten times.

33
00:02:16.479 --> 00:02:19.719
One question before we look:
in ten tosses,

34
00:02:19.759 --> 00:02:22.559
what's the chance
of getting exactly five heads?

35
00:02:22.599 --> 00:02:23.759
Take a second.

36
00:02:25.794 --> 00:02:27.274
Here are our ten tosses.

37
00:02:27.314 --> 00:02:29.154
Six heads, four tails.

38
00:02:29.194 --> 00:02:31.494
Not five. So is the coin cheating?

39
00:02:32.123 --> 00:02:35.523
To find out, let's look
at every possible outcome.

40
00:02:35.563 --> 00:02:40.883
In ten tosses, you can get anywhere
from zero to ten heads: eleven cases,

41
00:02:40.923 --> 00:02:42.483
one column for each.

42
00:02:42.523 --> 00:02:46.863
In each column, we stack
the sequences that give that result.

43
00:02:46.903 --> 00:02:52.363
A sequence is the exact order of the ten
tosses: heads, heads, tails, and so on.

44
00:02:52.403 --> 00:02:57.043
For zero heads, there is only
one sequence: tails, ten times.

45
00:02:57.083 --> 00:03:02.183
For exactly five heads, you have to choose
which of the ten tosses come up heads:

46
00:03:02.223 --> 00:03:04.763
two hundred fifty-two sequences.

47
00:03:04.803 --> 00:03:07.283
For six heads, two hundred ten.

48
00:03:08.023 --> 00:03:12.463
In all: two possibilities per toss,
ten times in a row,

49
00:03:12.503 --> 00:03:17.163
which makes one thousand twenty-four
sequences, all equally likely.

50
00:03:17.203 --> 00:03:21.323
So the chance of getting exactly
five heads is the share of sequences

51
00:03:21.363 --> 00:03:27.083
with five heads: two hundred fifty-two
out of one thousand twenty-four.

52
00:03:27.683 --> 00:03:32.083
Only 24.6 percent,
less than one time in four.

53
00:03:32.123 --> 00:03:35.023
Six heads: 20.5 percent.

54
00:03:35.063 --> 00:03:36.843
Four heads, the same.

55
00:03:36.883 --> 00:03:41.243
Six heads or four heads:
between them, four times out of ten.

56
00:03:41.283 --> 00:03:46.383
So getting six heads is perfectly
ordinary: our coin isn't cheating.

57
00:03:47.361 --> 00:03:49.061
Let's check with an experiment.

58
00:03:49.101 --> 00:03:54.721
A computer can imitate these tosses
for us: that's called simulating.

59
00:03:54.761 --> 00:03:58.001
It plays ten thousand
series of ten tosses,

60
00:03:58.041 --> 00:04:00.681
and drops each series into its column.

61
00:04:00.721 --> 00:04:04.361
Remember the colors: orange
for what is calculated exactly;

62
00:04:04.401 --> 00:04:06.641
blue for what is simulated.

63
00:04:06.681 --> 00:04:10.101
The blue bars land right
on the orange ones.

64
00:04:11.815 --> 00:04:17.135
Now, one single long series,
and let's track the proportion of heads:

65
00:04:17.175 --> 00:04:20.135
the number of heads divided
by the number of tosses.

66
00:04:20.175 --> 00:04:25.815
To the right, the number of tosses:
each tick mark means ten times more.

67
00:04:25.855 --> 00:04:27.475
The height is the proportion.

68
00:04:27.855 --> 00:04:30.335
After ten tosses: 60 percent.

69
00:04:30.375 --> 00:04:33.535
After ten thousand: 50.28 percent.

70
00:04:33.575 --> 00:04:37.815
After a million: 50.005 percent.

71
00:04:37.855 --> 00:04:42.675
The more we toss, the closer
the proportion gets to one half.

72
00:04:43.174 --> 00:04:47.774
This is the law of large numbers: when you
repeat an experiment a very large number

73
00:04:47.814 --> 00:04:51.974
of times, the observed proportion
gets closer to the probability.

74
00:04:52.014 --> 00:04:58.254
As a formula: k, the number of successes,
divided by N, the number of trials,

75
00:04:58.294 --> 00:05:01.794
gives the observed proportion,
written p hat.

76
00:05:01.834 --> 00:05:04.114
The hat marks a measured value.

77
00:05:04.154 --> 00:05:09.014
As N grows, p hat gets closer to p,
the true probability.

78
00:05:09.853 --> 00:05:13.233
Watch out for a trap that almost
every gambler falls into.

79
00:05:13.273 --> 00:05:17.833
People often believe that chance
evens out: after a run of tails,

80
00:05:17.873 --> 00:05:22.673
heads must be due. That's wrong:
the coin has no memory.

81
00:05:22.713 --> 00:05:27.053
Look at the gap between the number
of heads and the number of tails:

82
00:05:27.093 --> 00:05:29.453
it's the height of this new curve.

83
00:05:29.493 --> 00:05:33.613
If chance evened out,
this gap would come back to zero.

84
00:05:33.653 --> 00:05:40.013
It doesn't: after a million tosses, there
are ninety-four more heads than tails.

85
00:05:40.507 --> 00:05:42.947
So why does the proportion settle down?

86
00:05:42.987 --> 00:05:47.587
Because this gap grows much more
slowly than the number of tosses:

87
00:05:47.627 --> 00:05:51.267
its usual size follows
the square root of that number.

88
00:05:51.817 --> 00:05:57.207
The square root of a hundred is ten,
because ten times ten makes a hundred.

89
00:05:57.637 --> 00:05:59.867
The square root
of a million is a thousand.

90
00:05:59.907 --> 00:06:04.687
A thousand out of a million:
one thousandth, almost nothing.

91
00:06:04.727 --> 00:06:06.467
Chance doesn't even out.

92
00:06:06.507 --> 00:06:11.387
It gets diluted. Remember this
square root: it will come back.

93
00:06:12.599 --> 00:06:16.419
And to toss a million coins,
you don't even need a coin.

94
00:06:16.459 --> 00:06:20.439
A computer can produce numbers
that behave just like chance.

95
00:06:20.979 --> 00:06:25.679
Four lines of Python: we draw
a million numbers between zero and one,

96
00:06:25.719 --> 00:06:28.919
we decide that those
below one half are heads,

97
00:06:28.959 --> 00:06:31.439
and we print the proportion of heads.

98
00:06:31.479 --> 00:06:35.479
Answer: 0.500047.

99
00:06:36.119 --> 00:06:41.299
That's exactly what simulating is:
letting a machine play out chance for us,

100
00:06:41.339 --> 00:06:43.519
very fast and very often.

101
00:06:44.773 --> 00:06:46.853
A proportion is measured by counting.

102
00:06:47.433 --> 00:06:51.993
Here's the trick that made the method
famous: calculating, by counting,

103
00:06:52.033 --> 00:06:54.713
a number with nothing random about it.

104
00:06:54.753 --> 00:07:00.553
The number π. Take any circle, and divide
the distance around it by its width,

105
00:07:00.593 --> 00:07:04.133
the diameter:
you always get the same number.

106
00:07:04.173 --> 00:07:09.093
3.14159, and digits that never end.

107
00:07:10.919 --> 00:07:14.939
Take a square with sides
of length one: its area is one.

108
00:07:15.339 --> 00:07:20.759
Let's throw points into it at random, like
darts thrown by a perfectly clumsy player:

109
00:07:21.199 --> 00:07:25.579
every spot in the square has exactly
the same chance of being hit.

110
00:07:26.178 --> 00:07:29.318
Let's cut the square
in two along its diagonal.

111
00:07:29.358 --> 00:07:34.018
Now, a question: what share of the points
will land below the diagonal?

112
00:07:35.593 --> 00:07:40.513
Half, of course: this triangle
covers half the area of the square.

113
00:07:40.943 --> 00:07:44.713
We count one thousand five
hundred eighty-two points out

114
00:07:44.753 --> 00:07:49.033
of three thousand two hundred: 49 percent.

115
00:07:49.433 --> 00:07:52.093
Here's the rule that makes it all work:

116
00:07:52.133 --> 00:07:56.813
the share of the points that land in
a region is roughly the share of the area

117
00:07:56.853 --> 00:07:58.453
that this region covers.

118
00:07:58.493 --> 00:08:03.453
And it reads both ways: counting
the points is measuring the area.

119
00:08:04.488 --> 00:08:07.248
Let's replace the triangle
with a quarter disc:

120
00:08:07.288 --> 00:08:10.548
the point of the compass
in one corner of the square,

121
00:08:10.588 --> 00:08:12.828
and a radius equal to the side.

122
00:08:13.328 --> 00:08:16.068
We've known its area since ancient times.

123
00:08:16.108 --> 00:08:20.208
The area of a disc is π times
the radius, times the radius.

124
00:08:20.828 --> 00:08:26.368
Here the radius is one: the whole disc
would have an area of π, and our quarter,

125
00:08:26.408 --> 00:08:28.228
π divided by four.

126
00:08:28.268 --> 00:08:30.868
About 0.785.

127
00:08:31.633 --> 00:08:37.753
So about 78.5 percent of the points
should land in the quarter disc.

128
00:08:37.793 --> 00:08:41.193
Let's count. Two thousand
five hundred five points out

129
00:08:41.233 --> 00:08:43.333
of three thousand two hundred.

130
00:08:43.373 --> 00:08:47.333
Proportion: 0.783.

131
00:08:47.822 --> 00:08:49.542
And now, here's the twist.

132
00:08:49.582 --> 00:08:51.442
Let's forget that we know π.

133
00:08:51.882 --> 00:08:54.902
The area of the quarter
disc is π over four,

134
00:08:54.942 --> 00:08:59.242
and the points have
just measured it: 0.783.

135
00:08:59.282 --> 00:09:05.182
So π over four is roughly 0.783,
and π is four times that:

136
00:09:05.222 --> 00:09:07.102
3.13.

137
00:09:07.642 --> 00:09:12.682
We have just calculated π simply
by counting points that landed at random.

138
00:09:14.290 --> 00:09:18.170
3.13 isn't 3.14 yet.

139
00:09:18.210 --> 00:09:23.690
Let's add points and follow the estimate:
to the right, the number of points;

140
00:09:23.730 --> 00:09:26.070
the height is the value we find.

141
00:09:26.470 --> 00:09:28.381
Ten thousand points: 3.126.

142
00:09:28.421 --> 00:09:31.169
A million: 3.1405.

143
00:09:31.209 --> 00:09:35.690
A hundred million: 3.1415.

144
00:09:36.050 --> 00:09:39.110
The digits do arrive,
but more and more slowly.

145
00:09:39.150 --> 00:09:43.330
Why so slowly? That's
the big question of this video,

146
00:09:43.370 --> 00:09:46.770
and the square root we met
earlier will answer it.

147
00:09:48.520 --> 00:09:52.120
Computing π with chance:
the idea is an old one.

148
00:09:52.160 --> 00:09:57.100
In 1777, the naturalist
Buffon publishes this problem:

149
00:09:57.680 --> 00:10:02.740
you drop a needle on a wooden floor whose
boards are exactly as wide as the needle

150
00:10:02.780 --> 00:10:08.160
is long. What's the chance that it crosses
a crack, the gap between two boards?

151
00:10:08.580 --> 00:10:13.126
Answer: two divided by π,
about 64 percent.

152
00:10:13.166 --> 00:10:15.606
What is π doing on a wooden floor?

153
00:10:15.646 --> 00:10:20.786
The number of cracks crossed, on average,
depends only on the length of the needle,

154
00:10:20.826 --> 00:10:26.186
not on its shape: straight or bent,
each little piece keeps the same chances

155
00:10:26.226 --> 00:10:31.266
of crossing. So let's bend a wire
into a circle, as wide as a board.

156
00:10:31.306 --> 00:10:34.686
Wherever it lands,
it crosses exactly twice.

157
00:10:34.726 --> 00:10:38.666
Now, the distance around it
is π times its width:

158
00:10:38.706 --> 00:10:40.826
it is π times longer than the needle.

159
00:10:40.866 --> 00:10:46.026
So the needle crosses π times
less often: two divided by π.

160
00:10:46.386 --> 00:10:49.886
In 1812, Laplace turns
the question around,

161
00:10:49.926 --> 00:10:55.326
just as we did with the quarter disc:
drop lots of needles, and count.

162
00:10:55.366 --> 00:11:00.946
Here, out of four hundred eighty needles,
three hundred five cross a crack.

163
00:11:00.986 --> 00:11:03.766
That proportion is roughly two over π.

164
00:11:03.806 --> 00:11:07.586
So π is roughly two times
four hundred eighty,

165
00:11:07.626 --> 00:11:11.246
divided by three hundred five: 3.15.

166
00:11:11.666 --> 00:11:17.166
But counting by hand takes a long time:
the idea will have to wait for computers.

167
00:11:19.600 --> 00:11:24.660
So far, we've counted successes:
heads or not heads, inside or outside.

168
00:11:24.700 --> 00:11:27.560
But often,
the question isn't: what chance?

169
00:11:27.600 --> 00:11:29.980
It's: how much, on average?

170
00:11:30.020 --> 00:11:33.960
Take a die. If you roll it
a very large number of times,

171
00:11:34.000 --> 00:11:37.220
what value will the average
of your rolls head toward?

172
00:11:38.899 --> 00:11:42.639
In the long run, each face
comes up about one time in six.

173
00:11:42.679 --> 00:11:46.819
So the average of the rolls gets closer
to the average of the six faces:

174
00:11:46.859 --> 00:11:51.719
one plus two plus three plus
four plus five plus six,

175
00:11:51.759 --> 00:11:53.356
divided by six.

176
00:11:53.396 --> 00:11:57.939
3.5. This long-run average
is called the expected value.

177
00:11:58.419 --> 00:12:05.239
The name is misleading: nobody expects
to roll a 3.5 with a die, it's impossible!

178
00:12:05.279 --> 00:12:09.219
The simulation confirms it:
after ten thousand rolls,

179
00:12:09.259 --> 00:12:12.419
the average is 3.509.

180
00:12:13.459 --> 00:12:16.379
Everything we've just done
fits into one formula:

181
00:12:16.419 --> 00:12:19.099
the formula of the Monte Carlo method.

182
00:12:19.699 --> 00:12:21.419
Let's take it piece by piece.

183
00:12:21.877 --> 00:12:27.397
X is the outcome of chance: the die, the
coin, or, tomorrow, the price of a share.

184
00:12:27.437 --> 00:12:33.197
f of X is the number we look at in it:
the dots on the die, a gain, a loss.

185
00:12:33.237 --> 00:12:37.177
E, for expected value:
the long-run average of that number,

186
00:12:37.217 --> 00:12:40.897
the one we're after.
The wavy sign means: roughly equal.

187
00:12:40.937 --> 00:12:46.857
On the right, X one, X two,
all the way to X N: N samples,

188
00:12:46.897 --> 00:12:50.517
that is, N outcomes produced at random.

189
00:12:50.557 --> 00:12:53.637
The big zigzag sign means: add up.

190
00:12:53.677 --> 00:12:57.157
We add up f of each sample,
and we divide by N.

191
00:12:57.498 --> 00:13:02.918
Read out loud, the formula says: the
average we're after is roughly the average

192
00:13:02.958 --> 00:13:05.498
of what we observe by simulating.

193
00:13:05.538 --> 00:13:11.098
That's all. Even the proportion
of heads obeys it: we write one for heads,

194
00:13:11.138 --> 00:13:16.458
zero for tails, and the average
of those ones and zeros is the proportion.

195
00:13:16.498 --> 00:13:20.578
So a probability is an expected
value like any other.

196
00:13:22.481 --> 00:13:25.031
Let's see why banks love this formula.

197
00:13:25.441 --> 00:13:30.551
A share is a small slice of a company,
bought and sold on the stock market.

198
00:13:30.911 --> 00:13:33.851
Imagine a share worth
a hundred euros today.

199
00:13:33.891 --> 00:13:38.811
A call option is a contract that gives
you the right, but not the obligation,

200
00:13:39.321 --> 00:13:43.491
to buy that share in one year
at a fixed price of a hundred euros.

201
00:13:43.936 --> 00:13:47.316
If in one year the share
is worth a hundred thirty euros,

202
00:13:47.356 --> 00:13:50.676
you buy it for a hundred
and you make thirty.

203
00:13:50.716 --> 00:13:56.696
If it's worth eighty, you don't buy: you
make nothing, but you lose nothing either.

204
00:13:56.736 --> 00:14:00.536
So this contract can only pay:
it isn't free.

205
00:14:00.576 --> 00:14:02.856
How much should you pay for it today?

206
00:14:03.293 --> 00:14:07.733
Everything depends on the price
a year from now, and nobody knows it.

207
00:14:07.773 --> 00:14:11.693
So let's do as Ulam did:
let's imagine futures.

208
00:14:11.733 --> 00:14:16.413
Each blue line is one possible future
for the price: day after day,

209
00:14:16.453 --> 00:14:20.073
the computer nudges it up
or down, at random.

210
00:14:20.483 --> 00:14:24.173
The size of these jolts matches
the usual swings of this share.

211
00:14:24.213 --> 00:14:29.890
People in finance call it volatility:
here, 20 percent per year.

212
00:14:29.930 --> 00:14:34.990
In each future, we compute what
the contract pays, its payoff:

213
00:14:35.030 --> 00:14:39.310
the final price minus a hundred if
that's positive, zero otherwise.

214
00:14:39.890 --> 00:14:45.130
Then we take the average of these payoffs:
it's our formula, where X is a future,

215
00:14:45.170 --> 00:14:47.270
and f, the payoff.

216
00:14:47.310 --> 00:14:51.250
One last detail:
this payoff only arrives in a year.

217
00:14:51.290 --> 00:14:56.750
Now, a hundred euros invested at 5 percent
become about a hundred and five in a year:

218
00:14:56.790 --> 00:15:01.510
so a euro in a year is worth
a little less than a euro today.

219
00:15:01.550 --> 00:15:05.810
We multiply the average
payoff by about 0.95.

220
00:15:05.850 --> 00:15:07.690
This is called discounting.

221
00:15:08.059 --> 00:15:12.219
With these sixty futures,
we find 8.01 euros.

222
00:15:12.959 --> 00:15:18.299
But sixty is too few: sixty other
futures would give a different result.

223
00:15:18.339 --> 00:15:23.759
With a million futures,
the estimate settles down: 10.46 euros.

224
00:15:23.799 --> 00:15:25.519
And here's the judge.

225
00:15:25.559 --> 00:15:31.379
In 1973, Fischer Black,
Myron Scholes and Robert Merton found

226
00:15:31.419 --> 00:15:36.099
an exact formula for this simple contract:
the Black-Scholes formula,

227
00:15:36.139 --> 00:15:38.539
which would earn a Nobel Prize.

228
00:15:38.579 --> 00:15:41.359
It gives 10.45 euros.

229
00:15:41.399 --> 00:15:44.679
The simulation lands on it,
to within one cent.

230
00:15:45.019 --> 00:15:50.219
But when the contract gets more
complicated, no formula exists any more.

231
00:15:50.259 --> 00:15:53.059
The simulation, though, keeps working.

232
00:15:54.475 --> 00:15:56.035
Same idea for insurers.

233
00:15:56.075 --> 00:15:58.735
An insurer starts out
with a reserve of money.

234
00:15:59.075 --> 00:16:02.455
Day after day, it collects
premiums from its customers.

235
00:16:02.495 --> 00:16:06.955
Every now and then, it has to pay
a claim, an accident or a fire,

236
00:16:06.995 --> 00:16:09.195
of unpredictable size.

237
00:16:09.235 --> 00:16:13.553
If one day its reserve drops
below zero, that's ruin.

238
00:16:13.593 --> 00:16:15.213
What's the probability of ruin?

239
00:16:15.253 --> 00:16:18.473
Let's simulate ten thousand
futures for this insurer,

240
00:16:18.513 --> 00:16:22.433
and count those where ruin
happens: five hundred one.

241
00:16:22.473 --> 00:16:24.673
That's 5.0 percent.

242
00:16:25.413 --> 00:16:31.353
For this simple model, an exact
formula exists: it gives 4.9 percent.

243
00:16:31.853 --> 00:16:36.293
Here again, it's an average: the average
of a number that equals 1 when there

244
00:16:36.333 --> 00:16:38.773
is ruin, and 0 otherwise.

245
00:16:41.364 --> 00:16:47.904
But 10.46 isn't 10.45,
and 5.0 percent isn't 4.9.

246
00:16:47.944 --> 00:16:49.744
Where does this gap come from?

247
00:16:49.784 --> 00:16:54.644
Let's go back to π.
With a thousand points, we find 3.140.

248
00:16:55.224 --> 00:16:59.384
With another thousand points: 3.204.

249
00:16:59.424 --> 00:17:03.424
And a thousand more: 3.128.

250
00:17:03.464 --> 00:17:07.524
Our result changes every time:
it is itself drawn at random!

251
00:17:07.884 --> 00:17:09.924
So how much can we trust it?

252
00:17:10.497 --> 00:17:13.297
Let's run the experiment on a large scale.

253
00:17:13.337 --> 00:17:18.537
Let's estimate π with a hundred points,
and do it again two thousand times.

254
00:17:19.177 --> 00:17:24.417
Let's line up these two thousand estimates
along an axis, each one above its value;

255
00:17:24.457 --> 00:17:27.637
those that fall into
the same bin stack up.

256
00:17:27.677 --> 00:17:32.997
This is a histogram: the taller a bar,
the more often that result occurs.

257
00:17:33.579 --> 00:17:39.559
A bell curve appears, centered on π: most
estimates land close to the true value,

258
00:17:39.599 --> 00:17:41.959
and big errors are rare.

259
00:17:41.999 --> 00:17:45.019
This bell curve isn't special to π.

260
00:17:45.379 --> 00:17:49.879
It's one of the deepest results
in probability, the central limit theorem:

261
00:17:49.919 --> 00:17:54.659
the average of a large number of samples
spreads out along this bell curve,

262
00:17:54.699 --> 00:17:56.239
around the true value.

263
00:17:58.026 --> 00:18:00.306
The width of the bell curve is our error.

264
00:18:00.346 --> 00:18:05.506
Question: with four times as many points,
four hundred instead of a hundred,

265
00:18:05.546 --> 00:18:07.886
what happens to the bell curve?

266
00:18:07.926 --> 00:18:09.886
Four times narrower?

267
00:18:09.926 --> 00:18:11.526
Twice as narrow?

268
00:18:13.485 --> 00:18:18.925
Only twice. With a hundred points,
an estimate is typically off from π

269
00:18:18.965 --> 00:18:23.205
by 0.16: that's its typical error.

270
00:18:23.245 --> 00:18:27.085
With four hundred points: 0.08.

271
00:18:27.125 --> 00:18:30.805
With sixteen hundred: 0.04.

272
00:18:31.145 --> 00:18:35.905
Four times as many points,
and the error is divided by two.

273
00:18:36.248 --> 00:18:38.388
Why two, and not four?

274
00:18:38.428 --> 00:18:43.528
Remember the coin. Each sample is off,
sometimes too high, sometimes too low.

275
00:18:43.568 --> 00:18:48.828
When we add them up, these errors cancel
out, but only partly: a gap remains,

276
00:18:48.868 --> 00:18:52.628
and it grows like the square root
of the number of samples.

277
00:18:53.188 --> 00:18:59.028
With four times as many samples, that gap
doubles: the square root of four is two.

278
00:18:59.068 --> 00:19:02.888
But to take the average,
we divide by four times as many.

279
00:19:02.928 --> 00:19:06.868
Two divided by four:
the error is divided by two.

280
00:19:07.213 --> 00:19:10.453
Hence the golden rule:
the typical error equals sigma,

281
00:19:10.493 --> 00:19:14.193
divided by the square root of N,
the number of samples.

282
00:19:14.793 --> 00:19:17.653
Sigma is the typical error
of a single sample;

283
00:19:17.693 --> 00:19:19.653
it's called the standard deviation.

284
00:19:20.093 --> 00:19:26.273
For π, a single point gives four if it
lands in the quarter disc, zero otherwise:

285
00:19:26.313 --> 00:19:30.173
it is typically off from π by 1.64.

286
00:19:30.693 --> 00:19:36.993
With a hundred points, we divide by
the square root of a hundred, ten: 0.16,

287
00:19:37.033 --> 00:19:38.673
the width of our bell curve.

288
00:19:38.713 --> 00:19:42.733
And to gain one digit,
the error has to be divided by ten:

289
00:19:42.773 --> 00:19:48.173
a square root of N ten times bigger,
so N a hundred times bigger.

290
00:19:48.213 --> 00:19:51.353
That's why the digits
of π arrived so slowly.

291
00:19:52.137 --> 00:19:57.267
For students who want the exact statement
of the central limit theorem, here it is,

292
00:19:57.307 --> 00:19:59.067
at the bottom of the screen.

293
00:19:59.507 --> 00:20:04.387
Everyone else can remember the rule:
a hundred times more samples

294
00:20:04.427 --> 00:20:06.027
for one more digit.

295
00:20:07.513 --> 00:20:11.533
Now for the guarantee.
A bell curve always has the same shape.

296
00:20:11.573 --> 00:20:15.653
Let's measure it with its own unit:
the typical error.

297
00:20:15.693 --> 00:20:18.413
Within one typical error
of the true value,

298
00:20:18.453 --> 00:20:21.833
we find about two estimates out of three.

299
00:20:21.873 --> 00:20:26.393
Within 1.96 typical errors: 95 percent.

300
00:20:26.433 --> 00:20:32.533
That's where this number comes from,
1.96, which you'll see everywhere.

301
00:20:32.913 --> 00:20:39.033
Ninety-five times out of a hundred,
our estimate lands within 1.96 typical

302
00:20:39.073 --> 00:20:41.093
errors of the true value.

303
00:20:41.455 --> 00:20:43.535
Let's turn the sentence around.

304
00:20:43.575 --> 00:20:49.075
A distance reads both ways: if you
live less than a mile from the station,

305
00:20:49.115 --> 00:20:52.215
the station is less than
a mile from your home.

306
00:20:52.255 --> 00:20:57.715
In the same way, if our estimate
is within 1.96 typical errors

307
00:20:57.755 --> 00:21:03.175
of the true value, then the true value
is within 1.96 typical errors

308
00:21:03.215 --> 00:21:10.175
of our estimate. Now, the true value
is unknown to us; the estimate, we know.

309
00:21:10.215 --> 00:21:13.115
So let's draw this interval
around the estimate:

310
00:21:13.515 --> 00:21:17.755
ninety-five times out of a hundred,
the true value is inside.

311
00:21:18.227 --> 00:21:22.307
A practical detail:
sigma isn't known in advance either.

312
00:21:22.347 --> 00:21:24.647
We measure it on the samples themselves.

313
00:21:25.487 --> 00:21:31.527
For our first thousand points,
which gave 3.140, sigma is 1.64.

314
00:21:32.347 --> 00:21:38.887
Divided by the square root of a thousand,
then multiplied by 1.96: 0.10.

315
00:21:38.927 --> 00:21:44.767
So we write: π is 3.14,
plus or minus 0.10.

316
00:21:45.385 --> 00:21:49.485
Let's check the promise.
Here are a hundred estimates of π,

317
00:21:49.525 --> 00:21:53.225
each with a thousand points,
and their hundred intervals.

318
00:21:53.265 --> 00:21:55.845
The true value is the orange line.

319
00:21:56.325 --> 00:21:58.385
Ninety-six intervals contain it.

320
00:21:58.425 --> 00:22:01.065
Four miss it, in red.

321
00:22:01.105 --> 00:22:05.565
Such an interval is called
a 95 percent confidence interval.

322
00:22:05.605 --> 00:22:11.165
Careful: π doesn't move; it's the interval
that changes with each simulation.

323
00:22:11.625 --> 00:22:18.185
The 95 percent describes the method: it is
right ninety-five times out of a hundred.

324
00:22:18.565 --> 00:22:22.785
With a single simulation, we don't know
whether we're among the ninety-five

325
00:22:22.825 --> 00:22:24.485
or among the five.

326
00:22:24.525 --> 00:22:28.505
So, not a certainty,
but a risk known in advance.

327
00:22:30.360 --> 00:22:32.400
Let's go back to the opening question.

328
00:22:32.880 --> 00:22:37.100
A game is a sample that equals
one if it's won, zero otherwise.

329
00:22:37.560 --> 00:22:41.260
For a sample like that,
sigma is at most one half:

330
00:22:41.300 --> 00:22:45.680
that's the case of one chance in two,
the most uncertain one.

331
00:22:46.200 --> 00:22:52.540
With a hundred games: 1.96 times one half,
divided by the square root of a hundred.

332
00:22:53.060 --> 00:22:59.720
About 0.10: Ulam would have known his
chance to within ten percent, at worst.

333
00:23:00.360 --> 00:23:04.160
To get down to one percent,
you have to divide the error by ten,

334
00:23:04.200 --> 00:23:09.340
so play a hundred times more:
exactly 9,604 games.

335
00:23:09.700 --> 00:23:11.320
Was your answer close?

336
00:23:11.360 --> 00:23:14.660
No human plays ten thousand
games of solitaire.

337
00:23:14.700 --> 00:23:16.240
But a machine can.

338
00:23:18.283 --> 00:23:21.363
Still, one question
should be bothering you.

339
00:23:21.403 --> 00:23:24.383
To measure an area, you don't need chance:

340
00:23:24.423 --> 00:23:29.283
you can cover the square with a regular
grid, ten rows of ten points,

341
00:23:29.323 --> 00:23:31.703
and count the ones that fall inside.

342
00:23:31.743 --> 00:23:34.143
In a square, that's even more precise.

343
00:23:34.903 --> 00:23:36.703
So why bother with chance?

344
00:23:37.211 --> 00:23:39.671
The answer is one word: dimension.

345
00:23:39.711 --> 00:23:44.191
To describe one future of our option,
a single number is enough:

346
00:23:44.551 --> 00:23:46.711
the price of the share in one year.

347
00:23:46.751 --> 00:23:50.571
The futures line up along a line,
and ten points cover it.

348
00:23:50.611 --> 00:23:54.631
With two shares, from two companies,
a future is two numbers,

349
00:23:54.671 --> 00:23:58.631
like a point on a map:
so far east, so far north.

350
00:23:58.671 --> 00:24:02.791
Ten values for one, ten for the other:
a hundred points.

351
00:24:02.831 --> 00:24:08.171
With three shares, three numbers:
a point in a room, height included.

352
00:24:08.211 --> 00:24:10.051
A thousand points.

353
00:24:10.091 --> 00:24:14.931
The dimension is the number of uncertain
quantities it takes to describe a future.

354
00:24:14.971 --> 00:24:19.011
And each extra dimension
multiplies the grid by ten.

355
00:24:19.356 --> 00:24:23.336
Now, a bank holds shares
in far more than three companies.

356
00:24:23.376 --> 00:24:28.216
A portfolio of fifty different
shares means fifty dimensions: ten,

357
00:24:28.256 --> 00:24:31.546
multiplied by itself fifty times.

358
00:24:31.586 --> 00:24:36.736
A 1 followed by fifty zeros:
ten to the power of fifty points.

359
00:24:36.776 --> 00:24:39.596
Roughly the number of atoms
in the whole Earth.

360
00:24:39.636 --> 00:24:42.761
No computer will ever go through them all.

361
00:24:42.801 --> 00:24:46.221
Chance, on the other hand,
doesn't try to fill the space.

362
00:24:46.261 --> 00:24:50.501
It draws complete futures,
one by one: with fifty shares,

363
00:24:50.541 --> 00:24:53.281
one sample is fifty prices at once.

364
00:24:53.321 --> 00:24:56.761
Then one payoff per future,
and the average.

365
00:24:56.801 --> 00:25:01.121
And the error? Sigma,
over the square root of N.

366
00:25:01.161 --> 00:25:04.881
Sigma measures how far
the payoffs stray from their average;

367
00:25:04.921 --> 00:25:06.821
N is the number of samples.

368
00:25:06.861 --> 00:25:08.921
The dimension isn't in there.

369
00:25:08.961 --> 00:25:13.981
For the same sigma, a million samples
give the same precision with one share

370
00:25:14.021 --> 00:25:15.801
or with fifty.

371
00:25:15.841 --> 00:25:18.701
That's the real strength of the method.

372
00:25:19.939 --> 00:25:25.819
This wall is the one Ulam and his friend
John von Neumann ran into at Los Alamos,

373
00:25:25.859 --> 00:25:28.219
the American atomic weapons laboratory.

374
00:25:28.959 --> 00:25:33.919
They had to track neutrons, particles
that bounce at random through matter.

375
00:25:33.959 --> 00:25:38.859
Each bounce adds uncertain quantities,
a direction, a distance: so,

376
00:25:38.899 --> 00:25:40.419
more dimensions.

377
00:25:40.459 --> 00:25:43.139
And a neutron bounces dozens of times.

378
00:25:43.179 --> 00:25:49.339
So they simulate. In 1948, the first
calculations are run on the ENIAC,

379
00:25:49.379 --> 00:25:55.059
one of the very first computers, with
programs written by Klára Dán von Neumann,

380
00:25:55.099 --> 00:25:56.359
among others.

381
00:25:56.831 --> 00:26:02.451
That leaves the name. This work is secret:
the method needs a discreet name,

382
00:26:02.491 --> 00:26:04.451
a kind of code name.

383
00:26:04.491 --> 00:26:07.851
Their colleague Nicholas
Metropolis suggests Monte Carlo:

384
00:26:07.891 --> 00:26:13.051
a nod to an uncle of Ulam's, who used
to borrow money from his relatives to go

385
00:26:13.091 --> 00:26:15.631
and gamble at the Monte Carlo casino.

386
00:26:16.051 --> 00:26:21.391
And the name fits. A casino doesn't
know what the next game will bring.

387
00:26:21.431 --> 00:26:26.791
But over millions of games,
it knows what it will win on average.

388
00:26:26.831 --> 00:26:30.551
The method does the same:
thousands of games of chance,

389
00:26:30.591 --> 00:26:33.431
for an average that is almost certain.

390
00:26:33.891 --> 00:26:38.911
In 1949, Metropolis and Ulam
publish it under that name.

391
00:26:39.431 --> 00:26:43.291
Still, the method has
an Achilles' heel: rare events.

392
00:26:43.331 --> 00:26:47.551
Picture one of those insurers that hold
enough reserves for ruin to happen,

393
00:26:47.911 --> 00:26:50.551
someday, only about once in two hundred.

394
00:26:51.091 --> 00:26:53.211
Let's simulate a hundred futures.

395
00:26:53.251 --> 00:26:55.791
How many ruins do you think we'll see?

396
00:26:55.831 --> 00:27:00.411
Most often, none:
that happens six times out of ten.

397
00:27:00.451 --> 00:27:04.391
And we would conclude, wrongly,
that ruin is impossible.

398
00:27:04.923 --> 00:27:09.623
With a thousand futures,
we count six ruins: 0.6 percent.

399
00:27:09.663 --> 00:27:15.303
But the confidence interval
says plus or minus 0.5 percent:

400
00:27:15.343 --> 00:27:21.063
the true value could be 0.1
percent just as well as 1.1

401
00:27:21.103 --> 00:27:25.763
percent. In other words,
we know almost nothing:

402
00:27:25.803 --> 00:27:28.783
everything rests on six futures.

403
00:27:28.823 --> 00:27:33.943
It takes a hundred thousand
futures to get 0.49 percent,

404
00:27:33.983 --> 00:27:40.103
to within 0.04 percent;
the exact formula gives

405
00:27:40.143 --> 00:27:42.843
0.475 percent.

406
00:27:42.883 --> 00:27:48.743
And of those hundred thousand futures,
more than ninety-nine thousand were

407
00:27:48.783 --> 00:27:52.643
of no use: ruin doesn't happen in them.

408
00:27:52.683 --> 00:27:57.963
The rarer an event, the more samples
it takes to see it often enough.

409
00:27:58.364 --> 00:28:01.724
In a later session,
we'll see how to aim where it counts,

410
00:28:01.764 --> 00:28:06.104
to observe the rare event
without waiting for it to happen.

411
00:28:07.294 --> 00:28:12.494
Let's recap. First, a probability
is a proportion: we repeat chance,

412
00:28:12.534 --> 00:28:17.114
and we count. Second,
an expected value is an average,

413
00:28:17.154 --> 00:28:19.234
and an average can be simulated.

414
00:28:19.874 --> 00:28:24.134
Finally, the typical error equals
sigma over the square root of N:

415
00:28:24.494 --> 00:28:29.174
every result comes with its confidence
interval, and we know how right we are.

416
00:28:30.134 --> 00:28:33.134
And all of this fits
in seven lines of Python.

417
00:28:33.174 --> 00:28:35.614
We draw a million points in the square.

418
00:28:35.654 --> 00:28:39.334
We pick out the ones
that land in the quarter disc.

419
00:28:39.374 --> 00:28:44.034
Their proportion, times four:
that's the estimate of π.

420
00:28:44.074 --> 00:28:48.154
Then the confidence interval:
1.96 times sigma,

421
00:28:48.194 --> 00:28:50.574
divided by the square root of a million.

422
00:28:52.514 --> 00:28:57.254
Result: 3.1407, plus or minus 0.0032.

423
00:28:57.294 --> 00:29:02.334
The true value, 3.1416, is right inside.

424
00:29:03.809 --> 00:29:06.289
Predict, simulate, verify.

425
00:29:06.969 --> 00:29:11.609
That's the whole method, and it's
the thread running through this course.

426
00:29:11.649 --> 00:29:15.709
In the next session,
a question that sounds impossible:

427
00:29:15.749 --> 00:29:20.529
can we divide the error by thirty,
without taking a single extra sample?
