Some apologies- I am very sick right now, and so may not be super coherent. Whether this is a good thing or a bad thing is open to discussion?
Reflecting on last week’s post on a probabilistic proof of an optimal Lipschitz extension, I got to thinking about two of my favorite uses of probability in concrete math. The first is a way of calculating pi, called Buffon’s needle, which may be carried out experimentally. The second is a method of constructing the Sierpinski gasket, a famous fractal.
Computing the number pi is hard, as not only is it famously not a fraction (Lambert, 1761), but it is not the root of any polynomial (Lindemann, 1882). The most obvious geometric method, from Archimedes, inscribed and circumscribed a circle with polygons, which then bounds the circumference (which is defined to be ). Using a 96 sided polygon, Archimedes found 223/71 < pi < 220/70.
Here is Buffon’s approach: Suppose you drop a needle onto the floor in a bar (the fact that this is a bar has nothing to do with the rest of the story, it is just how it goes in my head). The needle is 1 inch long, and by some lucky coincidence, the slats on the wood floor are precisely 1 inch wide. So what is the chance that the needle intersects with a joint between slats? Turns out that it converges to 2/pi. The calculation is fairly enjoyable, but one of those activities best done in the privacy of your own home, or during a talk that has failed to capture your complete interest. Or you can bring needles to your next drinking outing…
Also! You can find numerous examples on youtube of “fractal zooms“, since, in theory, a fractal has infinite resolution. One should be able to calculate exactly which points are or are not in a fractal at any scale. I will post more on fractals and Hausdorff dimension in the future I am sure, but for now I want to share a great construction of the Sierpinski gasket. It is easy: pick a random point inside a triangle, and mark that point. Then choose a random vertex of the triangle, move your point halfway to that vertex, and mark the point. Keep repeating this process. It turns out that after your first few points, each point you mark will be inside the Sierpinski triangle.
The figure to the right has 1000 points in the triangle marked, and you can see that the first few choices were bad, as they missed the set, but after three, the rest are all in the fractal set. Also, there is an example below with 100,000 points marked, which at this resolution, looks as good as it is going to get.
Trying again with four points to choose from instead of three brings up no similar magic, which is all the more reason to be delighted at the above result:
Here is MATLAB code for generating the fractal triangles, for those interested:
r1 = rand(1);
r2 = (1-r1)*rand(1);
x = [0,rad*cos(pi/3),rad,0];
y = [0,rad*sin(pi/3),0,0];
point = zeros(n,2);
point(1,:) = [r1*x(2)+(1-r1-r2)*x(3),r1*y(2)+(1-r1-r2)*y(3)];
vert = randi(3,n,1);
for j = 2:n
point(j,:) = .5*point(j-1,:) + .5 * [x(vert(j)),y(vert(j))];