Q: Is there an algorithm for us to use in order to guess where a one dimensional random walk could end?
Let’s say we took N random steps in one dimension. I have to assign something for these steps so that we can distinguish each and every one of the steps. I’ll call the first step a1. In this case I can call;
second step: a2,
third step: a3,
forth step: a4,
Nth step: aN.
In the previous article I’ve mentioned that there are two possible values for every step: +1 or -1. I’ve also said that probabilities of these values are equal to each other and precisely ½. Now I can use all this information to calculate the average value each random step has.
In order to do that I can use arithmetic mean: Add both numbers together and divide the total into two. Let me show the arithmetic mean of a1 as <a1>. Then we get the following result:
Average value of a random step in one dimension is 0.
<a1> = 0
<a2> = 0
<a3> = 0
<aN> = 0
Summation of all the average values of N random steps would show us how far we are from the starting point. Let u be the distance from the starting point after N random steps. Then:
u = <a1> + <a2> + <a3> + … + <aN> = 0 + 0 + 0 + … + 0 = 0.
This result says that after taking N random steps in one dimension we should expect to stop at the starting point. This is a paradox because even if it is very small there is a possibility that all N steps could have the value (for instance) +1. In that case u would be +N. But our math shows us that if we increase the number of steps we would eventually end up at the starting point.
More Beautiful Mathematics Needed
This answer is not pleasing to neither to us nor to the mathematicians whom are dealing with this problem. Because 0 is only one of the many possibilities: Not the only possibility.
It would be better if we found an interval for the answer. We can use mathematical manipulations to achieve that.
Two possible outcomes for each step is either +1 or -1 and we just assigned a1 to the value of first step. Let me take the square of a1: It will be +1 in both cases. If I take the square of every one of them:
a12 = 1
a22 = 1
a32 = 1
aN2 = 1
Distance from the starting point was assigned to u. Now let’s square u. It will be a relatively long equation as follows:
u2 = (<a12> + <a22> + <a32> + … + <aN2>) + 2 (<a1a2> + <a1a3> + <a1a3> + … + <a1aN> + <a2a3> + … + <a2aN> + … )
First part of the equation makes N.
All the terms in the second part of the equation are equal to each other. That is why it will be enough if I calculate only one of the terms. Let me first calculate a1a2 so that I can take its average and find <a1a2>:
As you can see from the picture second part of the equation makes 0. Then square of the distance from the starting point is u2 = N. Take square root of both sides and we get our answer: +√N and -√N.
This result means that after taking N random steps in one dimension, one would stand at any point between +√N and -√N. For instance if one takes 100 random steps in one dimension, that person would be √100 = +/- 10 steps away from the starting point.
M. Serkan Kalaycıoğlu