All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Square thinking (Posted on 2003-10-19)
On a regular two dimensional coordinate plane, you have a square with side length 1 unit.

Pick a point within the square at random, and from there travel a random but straight direction .5 units.

What is the probability that you end up still within the square?

 No Solution Yet Submitted by Cory Taylor Rating: 4.1250 (8 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 solution | Comment 2 of 12 |
When a point is selected at random, and then a direction in which to travel .5 units, one is selecting a randomly oriented line segment, one of whose ends is at a random position in the square. It is easier to consider the probability distribution (uniform) of the angular orientation of the .5-unit line segment first.

First we must find the probability that the line will extend to the right of the right edge of the square (extended infinitely up and down). The probability that it extends to the left of the left edge will be equal to this, and as they are mutually exclusive, the two can be added together (or the one doubled) to get the probability that the line will extend outside the square to the left or right. By symmetry this will also be the probability that the line will extend either above or below the top or bottom of the square. As we are considering the sides extended indefinitely, the possibility exists that the distal end of the line will be outside the square in both ways, say to the up and right from the upper right corner of the square. So if the probability of being outside the square horizontally is called P(H) and vertically P(V), then the probability of being outside the square altogether must be P(H)+P(V)-P(H and V), as we would have counted the "outside the corners" areas twice by adding the horizontal and vertical probabilities together.

The two probabilities P(H) and P(V) are not independent, as a line which extends outside to the left or right would be more likely to be more horizontal and therefore less likely to extend above or below also, so P(H and V) is not equal to P(H)P(V), the product of the two probabilities.

As the probability of extending to the left is the same as that of extending to the right, let's just consider the latter:

The probability is the same whether the line is sloped up or down, and of course must be to the right. So we can find the average by taking the integral

∫{0 to pi/2} .5 cos θ dθ

and dividing by pi to get the average "danger band" on the right. The reason we divide by pi, rather than pi/2 is that the direction could fully swing out to the left as well, where there is no danger at all of falling off the right edge. Again, the average is the same on the lower semicircle as on this upper, i.e., over -pi to 0 or 0 to pi, and consequently as this is an average, over 0 to 2pi. As the height and the area of the square are both 1, this quotient also serves as the probability, and it comes out to .5/pi.

That's the probability of falling off the right. The probability of falling off the left is equal to that, and they are mutually exclusive so the probability of falling off either left or right is 1/pi, the total of the two.

(The problem so far resembles the Buffon's Needle method of estimating pi--dropping a needle on a lined surface, where the lines run in just one direction--all parallel, and counting how many cross a line, and comparing to the theoretical value.)

The probability of spilling over the top or below the bottom is also 1/pi by the symmetry of the situation.

Now we have to find the probability that the distal end spills over the top or bottom and also falls off to the right or left (in a corner "tic-tac-toe" or "naughts-and-crosses" type extension of the square). As mentioned before, the left-right and top-bottom probabilities are not independent, so we can't just muliply them to get the combined probability.

However we can similarly compute the area of the rectangle in, say the upper right corner of the square, where the initial point would have to fall for the average angle to result in placing it in that upper-right tic-tac-toe area relative to the central square under consideration. That rectangle has a width of .5 cos θ just as mentioned above for the width of the full strip on the right. Its height is .5 sin θ, so the integral over θ is

∫{0 to pi/2} .5 cos θ .5 sin θ dθ

which is also

∫{0 to pi/2} sin(2 θ) / 8 dθ

which comes out to 1/8.

To get the average this time, we must divide by 2 pi, as the whole circle has to be considered this time, as only 1/4 of it has any danger of falling off the corner at all. But of course we still have to multiply by 4 to account for the fact that there are four corners from which to fall out. So (1/8)/(2 pi) multiplied by 4 comes out to (1/4)/pi.

So the overall probability that the endpoint will come outside the square is

P(V)+P(H)-P(V and H)

= 1/pi + 1/pi - (1/4)/pi = 1.75 / pi or approximately .5570423008216342.

A simulation verifies this, using the program:

DEFDBL A-Z
pi = 4 * ATN(1)
FOR i = 1 TO 1000000
x = RND(1)
y = RND(1)
angle = 2 * pi * RND(1)
x = x + .5 * COS(angle)
y = y + .5 * SIN(angle)
ct = ct + 1
IF x < 0 OR x > 1 OR y < 0 OR y > 1 THEN
outside = outside + 1
END IF
NEXT
PRINT USING "####### ####### #.##### #.#####"; outside; ct; outside / ct; SQR(ct * outside / ct * (1 - outside / ct)) / ct

resulting in the statistics:

556944 1000000 0.55694 0.00050
showing the average as .55694 with std. error of the mean .00050, after a million trials.

 Posted by Charlie on 2003-10-19 13:26:40

 Search: Search body:
Forums (0)