Uncategorized

Stop Poking Me With That Needle

Let’s change things up a bit and take a detour into probability.

The most familiar notion of probability is optimized for your sock drawer: there are finitely many possibilities, all equally probable, and the probability of some event is just the ratio of the number of favorable cases to the number of possible cases.

It’s no surprise, then, that the first encounter with a problem like the following can be jarring:

Suppose we have a floor made of parallel strips of wood, each the same width, and we drop a needle onto the floor. What is the probability that the needle will lie across a line between two strips?

This is the famous Buffon’s Needle problem, and the main hurdle is that there are hidden infinities. For instance, the floor is effectively unbounded, so the count-and-divide approach is not going to work.

Now, there are plenty of solutions to this problem available online and elsewhere, so simply reaching a correct answer is not that interesting.  Instead, I’m going to use this problem and another to illustrate a general technique for solving a class of similar problems.

We’ll need just a few definitions from probability theory:
Experiment
Outcome
Event
Sample space

The idea is to exploit symmetry to vastly shrink the complexity of the problem we need to explicitly solve, while still yielding a general solution. The following is the guiding principle (which we’ll refer to as **):

Say we are interested in the probability of an event A in a random experiment. If we can partition the sample space into a set of mutually exclusive and exhaustive events such that the probability of A is the same conditional on each event in the partition, then that shared probability is also the probability of A in the experiment as a whole.

We could prove that, but it shouldn’t be a big stretch of intuition once we unpack things:

  1. Mutually Exclusive: Any two events of the partition must not share any outcome.
  2. Exhaustive: Every outcome of the experiment must be contained in at least one event in the partition.
  3. Probability of A is the same conditional on each event in the partition: No matter which event of the partition we assume will occur, we get a fixed probability of A also occurring.

The upshot is that given such a partition we can solve the whole problem by considering only one event of the partition, because the probability of the event of interest is the same in either case.

Suppose I know that all bank branches have the same probability of being out of lollipops, and I’m capable of calculating that probability for my local bank. Then without considering anyone else’s bank I can find the probability that a random person walking into their local bank will find no lollipops. That’s true whether there are 1, 10, or infinitely many banks.

Outside of extremely contrived examples, a subtle part of applying this principle can be arguing that the probability of the event of interest is in fact the same conditional on each event of the partition, when you’ve typically only explicitly calculated that probability conditional on one such event. One needs to check that the things that differentiate the elements of the partition have no effect on the likelihood of the event of interest.

Let’s now solve two problems using this sort of argument. The first requires no calculus. The second brings us back to Buffon’s Needle, and both are in this awesome book.

Coin in Square


In a common carnival game a player tosses a penny from a distance of about 5 feet onto the surface of a table ruled in 1-inch squares. If the penny (3/4 inch in diameter) falls entirely inside a square, the player receives 5 cents but does not get his penny back; otherwise he loses his penny.  If the penny lands on the table, what is his chance to win?

Saying that the penny definitely lands on the table is equivalent to saying that the table is infinite; the point is we don’t know the extent of the table but know it follows some sort of repeating pattern.

Consider the event that the penny lands with its center inside of a particular square.  Since this event always occurs for exactly one square per trial of the experiment, and it’s clear that only the coin’s position relative to that square matters, our partition arises pretty naturally. If we enumerate the squares on the table as S_1, S_2,…, S_n and E_i is the event that the penny’s center lands inside of S_i, then we can partition the sample sample space into the events E_1, E_2,…, E_n and see that the criteria are met for applying **.

Now we just consider a single square and calculate what fraction of its area can be occupied by the penny’s center without the penny going outside the square.  It’s not too hard to see that the acceptable area is a square with side length 1 – (((3/4)/2) * 2) = 1/4, which means our probability is

Special Case of Buffon’s Needle


A table of infinite expanse has inscribed on it a set of parallel lines spaced 2a units apart. A needle of length 2b (smaller than 2a) is twirled and tossed on the table. What is the probability that when it comes to rest it crosses a line?

This is the case of Buffon’s Needle where the needle is not large enough to cross two lines.

We can quickly see that the position of the needle along an axis parallel to the lines doesn’t matter.  And similar to the previous problem, the needle’s center will always be between two adjacent lines.  We can go further and say that the center will always be closest to a particular line, within a units.

So consider the event that the needle is closest to a particular line, with an arbitrary position on an axis parallel to the lines.  Let the lines be enumerated as L_1, L_2, … and E_i be the event that the needle is closest to L_i.  The events E_1, E_2, … comprise an appropriate partition for applying **, allowing us to only consider a single line.

The calculation for the desired probability after partitioning happens to be more complicated than in the previous problem, but hopefully the similarities in strategy are clear.

Let’s put an x-axis parallel to our line and a y-axis perpendicular, with the line at y=0.  We can place the needle below, rather than above, the line without loss of generality.  Now think of the experiment as (uniformly) randomly choosing both a y-coordinate between -a and 0 for the needle’s center and an angle Θ for the needle to make with the horizon (in radians).

IMG_1588 copy

A nice way to visualize the set of of all possibilities is as a rectangle with side lengths  and a, the lengths of the intervals in which Θ and can lie, respectively.  We want to find the fraction of the area of that rectangle which corresponds to the needle crossing the line.

For a particular Θ and y the needle crosses the line if

and so we have the following picture:

IMG_1587 copy

Our probability is the ratio of the area of the shaded region to the area of the whole rectangle:

One fun thing about that result is it means that one can estimate    by actually doing repeated trials of this experiment (not that it’s a particularly good way of doing so).


That’s it. No longer do you need to let random experiments with infinite but highly symmetric sample spaces keep you up at night! Long needles, Laplace’s Needle, and Buffon’s NOODLE await.

-Nowell Closser

Discussion

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