• 0

Expected value?

Question

Posted · Report post

A long time ago, I posted a problem about an ant in a circle with a diameter of 3 meters. The ant would go 1 meter in a random direction, rest, and go 1 meter in another random direction and repeat this process until it got out of the circle. What is the expected number of 1-meter steps the ant takes before escaping. It was never fully solved and I just recently got back to it and thought of this question: assume f(x) is the expected distance from the center after x steps. Is the answer to the original question merely when does f(x) become greater than 3?

0

Share this post


Link to post
Share on other sites

6 answers to this question

  • 0

Posted · Report post

If there is no directional bias, and that applies to both orientation and size of the step, then we expect the excursions of the ant to average out to zero. In fact, the probability in both one and two dimensions is unity that the ant will come back again [and again] to his starting point.

But between these visits to his origins the ant will wander away in one direction or another, and after any particular number of steps, he will be some expected distance away from his starting point. We would expect this distance to increase, but not necessarily in a linear fashion, with the number of steps taken.

The way we calculate this expected travel distance is to average a quantity that is always positive. That quantity is the square of the distance. Let's assume, just to explain how this works, that the ant travels in one dimension, along the x-axis; his steps are of length |s|, where s is the individual step vector, which may or may not be constant for each step; and that left and right motions are equally probable.

Again, if we consider the distance itself, equaling the sum of N random (vector) excursions to the left or right with equal probability, that average will tend to zero. That's just what we mean by unbiased. But if we average the square of the distance after N steps, we get a slew of product terms to find the average of. The product terms are of two types: [1] the squares of the individual step distances and [2] all the pairwise products of two different step vectors. The first type are always positive. Those of the second type are either positive or negative, in equal numbers, and they cancel out.

Thus, if dN = s1 + s2 + s3 + ... + sN is the (vector) distance the ant has traveled after N steps,

Then the averages of that distance, and of its square, are,

  • <dN> = <s1> + <s2> + <s3> + ... + <sN> = 0 + 0 + 0 + ... + 0 = 0.

  • <dN2> = <s12> + <s22> + <s32> + ... <sN2> = <s2> + <s2> +<s2> + ... + <s2>

    = N<s2>, if s varies from step to step.

    = N|s|, if |s| is constant.

    = N, if |s| = 1.

We don't want an estimate of the square of the distance, so we take the square root.

That gives us the root-mean-squared [RMS] traveled distance.

dRMS = sqrt(<dN2>) = sqrt(N<s2>)

In the present example, |s| = sqrt(<s2>) is constant and = 1.

dRMS = sqrt(<dN2>) = sqrt(N)

This is the desired formula.

The ant will have traveled an expected distance dRMS = 3 after taking 32 = 9 steps.

It may not seem intuitive, but this result also applies in two and three dimensions.

-------------------

Edit: Rereading the OP, I see the diameter is 3 meters.

So the ant has to travel 1.5 meters. This will take on average 2.25 steps.

Or maybe you meant radius of 3 meters..

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

If there is no directional bias, and that applies to both orientation and size of the step, then we expect the excursions of the ant to average out to zero. In fact, the probability in both one and two dimensions is unity that the ant will come back again [and again] to his starting point.

But between these visits to his origins the ant will wander away in one direction or another, and after any particular number of steps, he will be some expected distance away from his starting point. We would expect this distance to increase, but not necessarily in a linear fashion, with the number of steps taken.

The way we calculate this expected travel distance is to average a quantity that is always positive. That quantity is the square of the distance. Let's assume, just to explain how this works, that the ant travels in one dimension, along the x-axis; his steps are of length |s|, where s is the individual step vector, which may or may not be constant for each step; and that left and right motions are equally probable.

Again, if we consider the distance itself, equaling the sum of N random (vector) excursions to the left or right with equal probability, that average will tend to zero. That's just what we mean by unbiased. But if we average the square of the distance after N steps, we get a slew of product terms to find the average of. The product terms are of two types: [1] the squares of the individual step distances and [2] all the pairwise products of two different step vectors. The first type are always positive. Those of the second type are either positive or negative, in equal numbers, and they cancel out.

Thus, if dN = s1 + s2 + s3 + ... + sN is the (vector) distance the ant has traveled after N steps,

Then the averages of that distance, and of its square, are,

  • <dN> = <s1> + <s2> + <s3> + ... + <sN> = 0 + 0 + 0 + ... + 0 = 0.

  • <dN2> = <s12> + <s22> + <s32> + ... <sN2> = <s2> + <s2> +<s2> + ... + <s2>

    = N<s2>, if s varies from step to step.

    = N|s|, if |s| is constant.

    = N, if |s| = 1.

We don't want an estimate of the square of the distance, so we take the square root.

That gives us the root-mean-squared [RMS] traveled distance.

dRMS = sqrt(<dN2>) = sqrt(N<s2>)

In the present example, |s| = sqrt(<s2>) is constant and = 1.

dRMS = sqrt(<dN2>) = sqrt(N)

This is the desired formula.

The ant will have traveled an expected distance dRMS = 3 after taking 32 = 9 steps.

It may not seem intuitive, but this result also applies in two and three dimensions.

-------------------

Edit: Rereading the OP, I see the diameter is 3 meters.

So the ant has to travel 1.5 meters. This will take on average 2.25 steps.

Or maybe you meant radius of 3 meters..

I keep coming up with the same answer using the exact same math, but when I simulate it on the computer, it takes greater that 2.25 steps for r=1.5m (takes about 3.5 steps) and greater than 9 steps for r=3m (takes about 11.4 steps).

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

Mathemagician, on 30 Jan 2013 - 21:37, said:

A long time ago, I posted a problem about an ant in a circle with a diameter of 3 meters. The ant would go 1 meter in a random direction, rest, and go 1 meter in another random direction and repeat this process until it got out of the circle. What is the expected number of 1-meter steps the ant takes before escaping. It was never fully solved and I just recently got back to it and thought of this question: assume f(x) is the expected distance from the center after x steps. Is the answer to the original question merely when does f(x) become greater than 3?

I can't find a neat analytic solution for the problem of finding the expected number of steps until the ant leaves the circle, though it could be done by simulation or numerical approximation. This puzzle, however, asks a different question...

Assume f(x) is the expected distance from the center after x steps. I think that the answer in general is that the expected number of steps to escape the circle is not the same as the x for which f(x) >= 3. The differences between the simulations and bonanova's method already hint at this.

Let's consider a different simpler example to see how these two quantities are different. Consider an ant on the x-axis at the origin (0,0). Let's say that every step, the ant either stays still with probability (999/1000) or moves to the right by 1000 unit with probability (1/1000). We want to know the expected number of steps until the ant passes the marker 3 units away at location (3,0).

The expected distance away from the center for after 1 step is (999/1000 * 0 + 1000 * 1/1000 ) = 1. Also, in general, the expected distance after x steps is x, (i.e., f(x) = x ).

If expected number of steps to pass the marker is the same as the x for which f(x) >= 3, the ant should pass the point (3,0) within 3 step. But we know that is not true. In fact, it will take the ants 1000 steps in average to pass the point (3,0).

0

Share this post


Link to post
Share on other sites
  • 0

Posted (edited) · Report post

I believe this problem is about a drunk man, not an ant. He takes 1 meter step, falls, gets up makes another step in random direction, and so on.


If there is no directional bias, and that applies to both orientation and size of the step, then we expect the excursions of the ant to average out to zero. In fact, the probability in both one and two dimensions is unity that the ant will come back again [and again] to his starting point.

But between these visits to his origins the ant will wander away in one direction or another, and after any particular number of steps, he will be some expected distance away from his starting point. We would expect this distance to increase, but not necessarily in a linear fashion, with the number of steps taken.

The way we calculate this expected travel distance is to average a quantity that is always positive. That quantity is the square of the distance. Let's assume, just to explain how this works, that the ant travels in one dimension, along the x-axis; his steps are of length |s|, where s is the individual step vector, which may or may not be constant for each step; and that left and right motions are equally probable.

Again, if we consider the distance itself, equaling the sum of N random (vector) excursions to the left or right with equal probability, that average will tend to zero. That's just what we mean by unbiased. But if we average the square of the distance after N steps, we get a slew of product terms to find the average of. The product terms are of two types: [1] the squares of the individual step distances and [2] all the pairwise products of two different step vectors. The first type are always positive. Those of the second type are either positive or negative, in equal numbers, and they cancel out.

Thus, if dN = s1 + s2 + s3 + ... + sN is the (vector) distance the ant has traveled after N steps,

Then the averages of that distance, and of its square, are,
  • <dN> = <s1> + <s2> + <s3> + ... + <sN> = 0 + 0 + 0 + ... + 0 = 0.
  • <dN2> = <s12> + <s22> + <s32> + ... <sN2> = <s2> + <s2> +<s2> + ... + <s2>
    = N<s2>, if s varies from step to step.
    = N|s|, if |s| is constant.
    = N, if |s| = 1.
We don't want an estimate of the square of the distance, so we take the square root.
That gives us the root-mean-squared [RMS] traveled distance.

dRMS = sqrt(<dN2>) = sqrt(N<s2>)

In the present example, |s| = sqrt(<s2>) is constant and = 1.

dRMS = sqrt(<dN2>) = sqrt(N)

This is the desired formula.
The ant will have traveled an expected distance dRMS = 3 after taking 32 = 9 steps.


It may not seem intuitive, but this result also applies in two and three dimensions.

-------------------

Edit: Rereading the OP, I see the diameter is 3 meters.

So the ant has to travel 1.5 meters. This will take on average 2.25 steps.
Or maybe you meant radius of 3 meters.
.

I don't see how this trip averages out to zero and returns to the same point. Clearly, it is not true for the first step. And the probatillity of getting back to the point of origin on the second step is slight.

post-9379-0-52456400-1361051621_thumb.gi

I am not sure wheter the title I used "Two Dimensional Random Walk" is the conventional name for this problem. Must check the literature, (which I never do.)

Edited by Prime
0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

Oops, forgot another square root. Here is the correction/addition to the previous post.

post-9379-0-81215100-1361062981_thumb.gi

Normally, I try to avoid using integrals and calculus in general. I don't like that branch of mathematics and don't believe in it.

So it is entirely possible I messed up the above formulas. Besides, I have not actually figured out the Integral I used for this solution. But never mind all that. I checked few sources on the internet regarding two-dimensional random walk problem. I did not feel like submerging into the complex math presented there. Imo, those sources used insufficient justification and explanation for the formulas they use. What's interesting, in my brief examination, I did not see my concept of the average increase in distance from any given point with each step in the treatments of Random Walk in Two Dimensions. (As shown on the diagram in my previous post.)

Are there any professional mathematicians here to shed light on this?

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

To reiterate the point Bushindo has made already (post#4.)

There is a difference in average distance from origin after n steps and how many steps are required on average to travel that far. The average distance includes variations where the drunkard has traveled further and then returned. On the other hand, to travel further than 1.5 steps, he must make at least 2 steps. The probability of leaving the area after one step is zero, so the first step does not add anything to the average steps; whereas it does add its full size to the average distance.

One way to run a computer simulation is to make random steps until the drunkard wanders past the designated radius, tally up the steps it took for each experiment and calculate the average. That should show how many steps it takes on average to leave the area.

Another way is to have n steps in each experiment, tally up the distances traveled, calculate the average. That would show the mean distance from origin after n steps.

0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now

  • Recently Browsing   0 members

    No registered users viewing this page.