Fettered random walk

[bonanova]

Consider a random walk in the plane where each step is taken, beginning at the origin, in either in the positive x or positive y direction, i.e. either east or north, each choice being made by the flip of a fair coin. The length of each step is 1/2 the length of the previous step, and the first step has length √2. After infinitely many steps have been taken, what is your expected distance from the origin?

Edit: Ignore the original text in pink. Instead,

What is the distance to the origin of the centroid of the possible termination points? You find the centroid of a set of points by averaging respectively their x- and y- coordinates.

First correct answer wins, but style points will be awarded as well.

[plainglazed]

more musings

Spoiler

If you flip the fair coin and it happens to land all heads or all tails you'd travel along the x- or y-axis a distance of 2sqrt(2).  The line segment connecting these two points, (0,2sqrt(2)) and (2sqrt(2),0), describes the endpoints of all random walks.  The centroid of this segment is (sqrt(2),sqrt(2)) which makes sense because after the first step of sqrt(2), all subsequent steps combine for a distance of sqrt(2) thus making the distance from the origin to the centroid the minimum distance.  All points northwest of the segment's centroid and all points southeast are the inverse of one another so either half of the segment can be considered in search of the expected distance travelled.

So we can look along the segment from (sqrt(2),sqrt(2)) (which is the minimum distance from (0,0) and is equal to 2) to (2sqrt(2),0) (which is a maximum); to find the expected distance travelled.  The arithmetic average of these two numbers is sqrt(2)+1.  But that does not jive with the midpoint of this segment which is a distance of sqrt(5) from the origin.  So the distribution along the segment is not linear? And my explanation for my third guess is foolishness and is somewhat debunked above.

I did a simulation which for me means a spreadsheet.  Only sixteen paces (the last was still pretty small at .00004316) and only 100,000 trials and came up with an expected distance of 2.33668.  For me that number leaves no clue as how one might back out an explanation.  Having difficulty understanding how repeated irrational distances could clump at all but I have fractally little maths.  Have found this very interesting and hope someone with better maths can explain.  Thanks bn

 

[bonanova]

Here’s a challenge: I think this puzzle can be solved with almost no math at all. Like, think of a single “what if” question to ask that changes the conditions slightly. 

[Molly Mae]

Well I did a little bit of math...

...which means I'm probably wrong.

So one thing I can logically deduce is that the maximum distance from origin is 2√2.  So I made a right triangle with sides 2√2 and solved for the hypotenuse (4).  Then I bisected the right angle of the triangle to create two more triangles (yay, triangles!).  I know one side is half the length of the hypotenuse of the triangle I cut in half.  I also know that the 90 degree angle I cut in half is 45 degrees, so I have two sides that are length 2.  I don't need to solve for the hypotenuse of this triangle, because that bisector is length 2, and that's what I was looking for.

So my answer is 2.

[plainglazed]

zero style points (for this guess, for now...)

Spoiler

sqrt(2)+1?

 

[plainglazed]

amended answer

Spoiler

sqrt(5) - still lacking style but working on it...

[plainglazed]

or maybe

Spoiler

(2/3)sqrt(10)

after the first two steps you're sqrt(10)/2 from the origin.  continuing on in the same manner you're then an additional sqrt(10)/8 then sqrt(10)/32 then sqrt(10)/128... from the origin.  for every step you take that is not alternating north and east, the inverse of that path balances out?

yeah, so one of those three (not the first though)

[bonanova]

You are both on the right track, but I realize now that I mis-stated the OP. I didn't ask for what I wanted.

What I wanted to get at was the average location, that is the average of all the possible ending location coordinates, more precisely, their centroid, and its distance from the origin. 

That's not the same as the expected distance of the ending points -- which does take sort-of serious math. My bad.

I edited the OP.

[Molly Mae]

In that case...maybe...

I just need to cut my answer in half and say 1.  My distance was where the bisector intersected the hypotenuse of the original triangle with legs of 2

√2.  The center of this isosceles right triangle should be halfway along the bisector (which creates 2 isosceles right triangles).

[Molly Mae]

10 hours ago, bonanova said:

You are both on the right track, but I realize now that I mis-stated the OP. I didn't ask for what I wanted.

What I wanted to get at was the average location, that is the average of all the possible ending location coordinates, more precisely, their centroid, and its distance from the origin. 

That's not the same as the expected distance of the ending points -- which does take sort-of serious math. My bad.

I edited the OP.

 

I feel like my newest answer is wrong, since I believe no walk will ever be less than two. The current plot point I have is (√.5, √.5).  This is almost certainly wrong.

But I think I need to calculate a different triangle, specifically the one that involves the point that is 2√2 distance along the bisector of the original triangle.  

Without actually drawing it out, I'm pretty confident I can say the centroid of this new triangle is (2√2-2)/2 units from origin.

Which means that I did some math.

EDIT: And I'm dumb.  I calculated (2√2)² as 8 instead of 4.  I'll recalculate.

Edited April 6, 2018 by Molly Mae

[Molly Mae]

18 minutes ago, Molly Mae said:

  Hide contents

I feel like my newest answer is wrong, since I believe no walk will ever be less than two. The current plot point I have is (√.5, √.5).  This is almost certainly wrong.

But I think I need to calculate a different triangle, specifically the one that involves the point that is 2√2 distance along the bisector of the original triangle.  

Without actually drawing it out, I'm pretty confident I can say the centroid of this new triangle is (2√2-2)/2 units from origin.

Which means that I did some math.

EDIT: And I'm dumb.  I calculated (2√2)² as 8 instead of 4.  I'll recalculate.

And maybe I'm not dumb.  I think this evaluates correctly.

I'll stand by my answer.

 

Except that I'll simplify it to (√2)-1

Edited April 6, 2018 by Molly Mae

[Molly Mae]

29 minutes ago, plainglazed said:

more musings

  Hide contents

If you flip the fair coin and it happens to land all heads or all tails you'd travel along the x- or y-axis a distance of 2sqrt(2).  The line segment connecting these two points, (0,2sqrt(2)) and (2sqrt(2),0), describes the endpoints of all random walks.  The centroid of this segment is (sqrt(2),sqrt(2)) which makes sense because after the first step of sqrt(2), all subsequent steps combine for a distance of sqrt(2) thus making the distance from the origin to the centroid the minimum distance.  All points northwest of the segment's centroid and all points southeast are the inverse of one another so either half of the segment can be considered in search of the expected distance travelled.

So we can look along the segment from (sqrt(2),sqrt(2)) (which is the minimum distance from (0,0) and is equal to 2) to (2sqrt(2),0) (which is a maximum); to find the expected distance travelled.  The arithmetic average of these two numbers is sqrt(2)+1.  But that does not jive with the midpoint of this segment which is a distance of sqrt(5) from the origin.  So the distribution along the segment is not linear? And my explanation for my third guess is foolishness and is somewhat debunked above.

I did a simulation which for me means a spreadsheet.  Only sixteen paces (the last was still pretty small at .00004316) and only 100,000 trials and came up with an expected distance of 2.33668.  For me that number leaves no clue as how one might back out an explanation.  Having difficulty understanding how repeated irrational distances could clump at all but I have fractally little maths.  Have found this very interesting and hope someone with better maths can explain.  Thanks bn

 

 

Oh, derp.  I see that I subtracted the 2 to find the centroid of the triangle when I shouldn't have, since that 2 is definitely part of the distance.  I agree that sqrt(2)+1 is the centroid of that triangle.  If you run more trials, does the expected difference come closer to 2.4142? 

But...I still like an expected end coordinate of (√2, √2) and a total distance of 2.  For any "walk" that chooses directions using X or Y, there's an inverse that swaps Xs with Ys and Ys with Xs.  So I'd expect √2 in one direction and √2 in the other as the average.

10 minutes ago, Molly Mae said:

  Reveal hidden contents

Oh, derp.  I see that I subtracted the 2 to find the centroid of the triangle when I shouldn't have, since that 2 is definitely part of the distance.  I agree that sqrt(2)+1 is the centroid of that triangle.  If you run more trials, does the expected difference come closer to 2.4142? 

But...I still like an expected end coordinate of (√2, √2) and a total distance of 2.  For any "walk" that chooses directions using X or Y, there's an inverse that swaps Xs with Ys and Ys with Xs.  So I'd expect √2 in one direction and √2 in the other as the average.

Missed edit time.  This makes the assumption, though, that the average of two paths which are inverse of each other is 

√2, √2

Edited April 6, 2018 by Molly Mae

[bonanova]

Spoiler

The locus of points equidistant from the origin is a circle, using standard Cartesian distance.

Distance traveled by delta x and delta y (so-called taxicab metric) travel changes the "circle" into a diamond shape of 4 lines, 2 each at 45 degrees and 135 degrees. In the first quadrant it's the line @plainglazed describes, whose centroid (midpoint) is at a (Cartesian) distance of 2 from the origin. That's the answer I originally had in mind -- a result that can be obtained just from the knowledge that the series 1 + 1/2 + 1/4 ... converges to 2.

What I ended up asking for was the average (Cartesian) radius of a Taxicab circle. You can get it by integrating the Cartesian distance to the diagonal line as x goes from 0 to 2 sqrt(2) (which one definitely can't do in one's head) or by simulation, as @plainglazed did. It turns out to be a fundamental constant associated with the parabola -- the parabola's version of pi, if you will.

Which makes sense, because the distance from the origin to the 45-degree line is a parabola if plotted vs angle from 90^o to 0^o.

The exact value is ln{ 1+sqrt(2) } + sqrt(2) = 2.2955871...

@Molly Mae blazed the trail and @plainglazed nailed it.