Randomness

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.

To calculate, you'll mostly care where the center of the needle lies, and what choice of angles would cause it to intersect with the slats.

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 2 \pi).  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…

Randomly generated triangle with 1000 points

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.

Again, with 100,000 points.

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:

100,000 points choosing from four vertices, instead of three.

Here is MATLAB code for generating the fractal triangles, for those interested:

function gasket(rad,n,d)
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))];
end
scatter(point(:,1),point(:,2),d,'k','filled')
axis off
end

Advertisements

7 comments on “Randomness

  1. lkovalev says:

    Another approach to Buffon needle problem is to convince yourself that the shape of the needle does not matter as long as you count the number of intersections it makes with the lines. (E.g., break the needle in pieces; note that for each piece the expected number of intersections is proportional to its length; glue the pieces together in some way and observe that the expectations add up.) Then, bend the needle into a circle of diameter 1/pi in. This will give 2 intersections with probability 1/pi.

  2. […] In yesterday’s post a fractal was made by repeatedly moving a point halfway to a randomly selected vertex of a triangle, and I noted that the same magic does not happen with four vertices.  How young and foolish I was then! […]

  3. lkovalev says:

    Also, being sick excuses you for the remark “after your first few points, each point you mark will be inside the Sierpinski triangle”. Since the triangle has zero measure, with probability 1 none of the points you mark will ever enter it. They will just hang out nearby.

    Hope you’re getting better.

    • lkovalev says:

      More precisely: with probability 1 your initial point is not in the gasket, and if the initial point is not there, the others won’t be either.

  4. […] after yesterday’s post (which was a response to the post of two days ago), I found a few more cool things with this method of generating fractals.  In particular, we take […]

  5. […] so I can in fact post it here.  It uses recursion to again generate the Sierpinski gasket from the flurry of fractal posts I had earlier, though this is a deterministic approach.  What it does is takes a column of points […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s