I'd like to share a problem which was covered in 3blue1brown's lockdown math lecture series and I found particularly delightful. This post is adapted from a talk I've given to year 12 further maths students in my sixth form, as the solution contains only A level maths content and I wanted to give a flavour for the abstractions of university maths. I promised myself not to recycle content from 3B1B as I believe he's the best maths educator on the internet and there's nothing I can add but this problem wasn't covered in full animated detail and I'd like to talk about measure theory. The problem goes as follows:
"2 numbers are randomly (independently) chosen between 0 and 1. We divide them and round down the number to the integer below. What is the probability that the resulting integer is even?"
Or, for the maths symbol lovers like myself (rookie latex error italicising the mod):
Firsly I'd like to clarify what I mean when I say "randomly chosen between 0 and 1". "All numbers are equally likely to be chosen" is unfortunately not strong enough: more precisely, I mean that the probability that I pick a number between a and b (0<a<b≤1) is b-a. This should make sense though: I throw a dart at a numberline and the probability I land in some interval is just the length of that interval. [[This is called a uniform distribtion, similar to a rod with uniform density where the mass of a section is proportional to its length.]]
So how could we visualise 2 numbers being uniformly distributed between 0 and 1? Instead of picturing 2 points being chosen randomly on a numberline, I could choose a point at random in the unit square! Now the probability I choose a point in a certain region is the area of that region![[this relies on independence of the choices.]] We know a little bit about probability but we know a lot more about finding areas! So we just need to indentify the set of points in the square with coordinates (x,y) for which y/x rounds down to an even integer.
Maybe we haven't encountered this rounding down malarkey before [[called the floor function]]. Can we reformulate/find an alternative characterisation? Yes: if a number rounds down an integer, that means it's greater than or equal to that integer but strictly less than the next integer. Specifically
A number x rounds down to an integer k if and only if k ≤ x < k+1
Now what if y/x rounds down to k? Then
y/x rounds down to k means that k ≤ y/x < k+1
Now multiplying by x [[which is positive so preserves the direction of inequality]] gives
kx ≤ y < (k+1)x
There are 3 letters going on so let's keep track of what each one is doing: x and y can be any number between 0 and 1 and (x,y) is the coordinate of a point in the square, while k is any integer. Let's try a few values of k to get a feeling for the regions described. k = 0 corresponds to the region
0 ≤ y < x
Which describes a triangle in the lower right corner of our square:
What about for k = 1? This corresponds to the region
x ≤ y < 2x
Which describes a wedge bounded by the lines y = x, y = 2x and y = 1
Now what happens as I increase k? I get a family of wedges (an insult I'm reticent to use), becoming steeper and thinner, getting closer to the y axis. But remember I'm asking about rounding down to an even number so I only care about the case when k is even. This looks like the collection of triangles
I've only drawn the first few but since there are infinitely many even numbers, there's a triangle for each even number and our challenge is to find the shaded area. This means finding the area of each triangle and adding them all (infinitely many of them) together.
The largest triangle is half the square, corresponding to the case y<x, which is equally likely as x<y. For the next one we'll use the fact that it has height one and try to find the base. The base is the difference between the intersections between the lines y = 2x and y = 3x with the line y = 1. Plugging y = 1 into each equation gives x = 1/2 and x = 1/3 respectively, so the length of the base is 1/2 - 1/3. Then the area is
base x height / 2 = (1/2 - 1/3)/2
The next triangle goes similarly, where we find the intersection of the line y = 1 with the lines y = 4x and y = 5x, giving a base of 1/4 - 1/5. Hopefull that is enough to spot the pattern, that the n-th triangle which intersects the line y = 1 at 2 different points will have base 1/2n - 1/(2n+1) and height 1. Then we can write our total area as a sum, factoring out the half:
Now we just need to figure out what this sum equals... Noticing that it almost alternates plus/minus we're instead going to consider
Now the massive nerds like me well-versed in series might recognise this one as ln(2) ~ 0.691. I normally hate when solutions pull out magic tricks like this but I think, given this solution is in danger of exceeding a coffee, I'm going to save the proof of this one for another post. So how do we relate this number to our original sum and hence the answer to the problem? Multiplying S_2 by a half and adding it to S, we see that all the terms except the first cancel!
Leaving us with:
Or approximately 0.65. I don't know about you but I find this a delightful result, with the guest appearance of a seemingly unrelated logarithm. This is where 3B1B leaves his solution but I do believe I have something to add in the next post which is an explanation as to why we can saunter so seemlessly between the worlds of probabilities and areas, across the bridge of measure theory. As always I'm very open to feedback, either in the comment section or at my email finlaywhitton@outlook.com, whether about the solution, the structure or how to integrate latex into html!
Comments
Post a Comment