A bit of a random walk...

[Logophobic]

Concerning Fox 217 from http://www.8foxes.com

A random process on the plane is defined as follows:
It starts from point 0. Then the following point is generated in a
randomly-selected direction, 1 unit apart from the previous one.
The process stops the first time 1 (or more) closed area(s) is obtained.
What is the average number of steps taken?

Specifically, what is the probability that a closed area will be created in three steps?

[Villanon]

[Deleted]

[Milk]

Nice to see you back Logo.

My guess is...
2 * (1/6 * 5/24 + 1/12 * 1/12)
= 1/12

[03myersd]

Going to go for what seems like a well educated guess here:

Imagine an equilateral triangle with sides of length 1. 1 vertex is the centre of a unit circle, which means 2 sides are the radius of the circle, with the 3rd side a chord.

Take 1 step. This is one of the sides of the triangle representing the radius. In order to create a closed space in 3 moves you need to have the angle with the next step 60 degrees or less which gives a probability of 1/6. However you need to remember that you can also mirror this configuration which gives a 1/4 chance for step 2.

For step 3, you also need an angle of less than 60 degrees (relative to the second line) which gives a probability of 1/6.

P = 1/3 * 1/6 = 1/18

I have no idea if this is correct, but it seems about right.

[Milk]

I'm quietly confident with 1/12. An equilateral triangle marks a pivotal point between two distinct parts of the solution. I've hidden some of my working on the line below 'My guess is...'

[Logophobic]

That's a good guess, Milk. My data from trial runs to find an answer to the original question predicts just that, I just didn't have the math to prove it. Have I overlooked something simple?

03myersd, only one angle needs to be less than 60 degrees. For example, if the first angle is 30 degrees, the second can be as much as 75 degrees.

[jemidiah]

The general question is very difficult. There are so many variables to account for, and different ways for intersections to come about....

I agree with Milk. An equilateral triangle is the transition point between two triangle types, and the answer is 1/12.


Say the origin is at (1, 0), and the first walk takes you to (0, 0). [These assumptions don't change the probability.] Now move with a reference angle A, so the next step takes you to (cosA, sinA). If you draw out the triangle, it's clear that the situation is symmetrical about the horizontal axis, so we may say A is chosen uniformly from [0, tau/2] (tau = 2pi). Moreover, for A between tau/4 and tau/2, there can be no solutions.

Suppose tau/6 <= A <= tau/4. Draw a circle around (cosA, sinA) of radius one, and you'll find its intersection points with the (0, 0)-(1, 0) line have a central angle of tau/2 - 2A. Finally, for A <= tau/6, the second intersection point is to the right of the point (1, 0), which does not give an intersection. We need to compute the central angle between the ray connecting (cosA, sinA) to (0, 0) and that connecting (cos, sinA) to (1, 0).

To compute it, drop a perpendicular from (cosA, sinA) to the line between (0, 0) and (1, 0). This creates two triangles. The half of the central angle on the leftmost triangle is just tau/4 - A. The half of the central angle on the rightmost triangle is harder to compute. The bottom (horizontal) leg has length 1 - cosA, and the left (vertical) leg has length sinA. The relevant angle is then arctan([1-cosA]/sinA), which happens to be A/2 in this angle range. The central angle in total is tau/4 - A + A/2 = tau/4 - A/2.

In summary, for a given A in [0, tau/2], the next angle can be chosen from [0, tau], but only the following angle range sizes make an intersection:

R(A) is given by...
0<= A <= tau/6: tau/4 - A/2
tau/6 <= A <= tau/4: tau/2 - 2A
tau/4 <= A <= tau/2: 0


The chance of getting a self-intersection is just the average of R(A)/tau, which can be computed from elementary calculus as

1/(tau/2) * integral from 0 to tau/2 of R(A)/tau dA
= 2/tau^2 * integral from 0 to tau/2 of R(A) dA
= 2/tau^2 *
[integral from 0 to tau/6 of (tau/4 - A/2) dA
+ integral from tau/6 to tau/4 of (tau/2 - 2A) dA
+ integral from tau/4 to tau/2 of 0 dA]
= ...
= 1/12

[Logophobic]

Thank you, jemidiah. I had the solution visualized, I just couldn't do the math.

I wonder if this could also be solved with vectors?

[jemidiah]

What do you mean by "solved with vectors"? Do you want to replace the calculus with vectors, or to replace the arctan bit with vectors?

Mostly my solution used geometry. I'm certain there's a quick geometric derivation of the angle I calculated by "arctan([1-cosA]/sinA) = 2A"; I just didn't take the time to find one. The calculus is also unnecessary, but is similarly convenient. Finding the average of a line segment can be done "by hand" easily enough, but I usually make errors when doing that sort of calculation by hand. (I typed my final set of integrals into Wolfram Alpha.)

Maybe you want to replace the geometry with vector manipulations. You could recast my proof in that language, but it's clunky.

[Logophobic]

In your solution, the third segment starts at (cosA, sinA) and needs to cross (0, 0)-(1, 0). From a different view, we could have the third segment start at (1, 0) and needing to cross (0, 0)-(cosA, sinA). We have thus defined two vectors and ask, given each a random direction, what is the probability of these two vectors cross? Does that make sense?

[Milk]

Can't answer in terms of vectors

I looked at it a little differently in places I think to Jem, not sure this counts as a proof though.

If the angle between step 1 and step 2 (A) is > 0° and <= 60° then the possible positions of step 3 bisect the full range of step 1. Because all the steps are of equal length and because the range goes from the origin of step 1 to the origin of step 2 the angle of this range (B) can be given by (180° - A)/2.
this is nice because there is a linear relationship between A and B so we can pluck the average B = (180° - (60° + 0°)/2)/2... B = 75°

If A is > 60° and < 90° then possible step 3 positions no longer bisect the full length of step 1 but again because the steps are equal, step 3 starts to bisect step 1 at the point where the angle between step 1 and step 3 = A so now we can say B = (180° - 2 * A) which again is linear so we can take the average again B = (180° - 2 * (90 + 60)/2)... B = 30°

If A is > 90° then no triangle can be formed.

Multiply by 2 for Symmetry and convert degrees to fractions of TAU...

30° = 1/12, 60° = 1/6, 75° = 5/24

2 * (1/6 * 5/24 + 1/12 * 1/12) = 1/12

[Logophobic]

That is something simple! I did not overlook the linear relationship between A and B, but I missed the connection between that and the averages. Very nicely done!

[jemidiah]

In your solution, the third segment starts at (cosA, sinA) and needs to cross (0, 0)-(1, 0). From a different view, we could have the third segment start at (1, 0) and needing to cross (0, 0)-(cosA, sinA). We have thus defined two vectors and ask, given each a random direction, what is the probability of these two vectors cross? Does that make sense?

Yes, I think I see what you're asking. I actually computed that probability [it's R(A)/tau], which works for all similar pairs of vectors from translation, rotation, and scale invariance. That is, given two segments [vectors, if you want] connected end-to-end, where the smaller angle between them is A and the length of each vector is the same, the probability that randomly (uniformly) sticking another segment [vector] on to the end of the second segment of the same length intersecting the first segment is R(A)/tau, using my R(A) function above.

...2 * (1/6 * 5/24 + 1/12 * 1/12) = 1/12

I believe our methods are equivalent. Yours didn't use calculus or trig (like I said, they're not essential) but we did essentially the same calculations. I'm sure if I wrote out the integral computations the final steps would match up term-for-term.

[Milk]

<snip>we did essentially the same calculations.

Jem, you are much more mathematically minded than I am. There was a bit in the middle that seemed more complex than what I saw. I was careful to insert a weasel worded 'I think'.

[jemidiah]

Just to illustrate the equivalence between our methods, I'll write out my integral calculations. Feel free to skip to the last couple of lines.

2/tau^2 *
[integral from 0 to tau/6 of (tau/4 - A/2) dA
+ integral from tau/6 to tau/4 of (tau/2 - 2A) dA
+ integral from tau/4 to tau/2 of 0 dA]

= 2/tau^2 *
[(tau/4 * A - A^2/4) for A from 0 to tau/6
+ (tau/2 * A - A^2) for A from tau/6 to tau/4]

= 2/tau^2 *
[(tau/4 * tau/6 - (tau/6)^2 / 4)
+ (tau/2 * tau/4 - (tau/4)^2) - (tau/2 * tau/6 - (tau/6)^2)]

= 2 *
[(1/4 * 1/6 - 1/(6*6*4))
+ (1/2 * 1/4 - 1/(4*4))
- (1/2 * 1/6 - 1/(6*6))]

= 2 * (1/6 * (1/4 - 1/24) + (1/8 - 1/16 - 1/12 + 1/36))
= 2 * (1/6 * (1/4 - 1/24) + 1/12 (12/8 - 12/16 - 12/12 + 12/36)
= 2 * (1/6 * (1/4 - 1/24) + 1/12 (3/2 - 3/4 - 1 + 1/3))
= 2 * (1/6 * (1/4 - 1/24) + 1/12 (3/4 - 1 + 1/3))
= 2 * (1/6 * (6/24 - 1/24) + 1/12 (1/3 - 1/4))
= 2 * (1/6 * 5/24 + 1/12 * 1/12)
= ... = 1/12

For comparison, Milk's calculations ended in
2 * (1/6 * 5/24 + 1/12 * 1/12) = 1/12