# Random walk with decreasing step size

I have to make simulation of a random walk that gets smaller and smaller. Each step the x-axis gets rescaled 1/2 and y-axis by 1/Sqrt. So one needs more and more steps to get to the end.

So one should get:

n = 0: {{0, 0}},
n = 1: {{0, 0}, {1, 1}}
n = 2: {{0, 0}, {1/2, 1/Sqrt}, {1, 2/Sqrt}}
n = 3: {{0, 0}, {1/4, 1/2}, {1/2, 1)}, {3/4, 1/2}, {1, 1}}


(at n = 4, one would need 9 steps etc.)

However, I had a problem with defining what the next step should be. My code (now it works) :

randomWalk1000[x_] :=
For[n = 0, n < x, n++,
If [n == 0, path := {{0, 0}}];
If[n == 1, path := {{0, 0}, {1, 1}}, stepsize = 1;];
If[n > 1,
path = Transpose[{path[[All, 1]]/2, path[[All, 2]]/Sqrt}];
For[i = 1, i <= 2^(n - 2), i++,
step = RandomChoice[{-1, 1}];
stepsize /= Sqrt;
path1 := Last[path];
AppendTo[
path, { 1/2 + (i/2^(n - 2))*1/2 , path1[] + stepsize*step}]]];
Print[path]]


Perhaps this will help:

randomSteps[n_] := RandomChoice[{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}, n];
stepScales[n_] := NestList[{0.5, Sqrt[2.]} # &, {1, 1}, n - 1];
path[n_] := Accumulate[randomSteps[n] stepScales[n]]


In each step you choose a direction which is one of {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}. Then in each step the axes have a certain lengths, which can be computed recursively. For the five first steps they are {{1, 1}, {0.5, 1.41421}, {0.25, 2.}, {0.125, 2.82843}, {0.0625, 4.}}, as computed by stepScales. The actual step is the chosen direction times the length of the axis. So for example a step {-1, 0} at $n = 4$ would be {-0.25, 0} based on the previous list. Finally, Accumulate adds the steps together to get the path.

• Shouldn't´t the step scale in y-direction be 1/Sqrt ? Apr 17 '17 at 15:59
• @mgamer The question states that "Each step the x-axis gets rescaled 1/2 and y-axis by Sqrt". Apr 17 '17 at 16:07
• Uuups, you´re right - I only saw the "1/Sqrt" in the code of the OP and did not look carefully enough at the question ;-) Apr 17 '17 at 16:45
• Thanks. No, you're right, I made I typo, it should be 1/sqrt(2). But I think this is not quite the answer I was looking for, because the values of the x-axis should never be negative, as I am aiming to get a limit of brownian motion (in the direction from 0 to 1). So the last element of the list should always be {1, x}. Also the step rate should be increasing : 1,2,3,5,9,17.. number of steps = 2^(n-1) +1. So when n=5, one needs 17 steps to get to the end. Apr 17 '17 at 18:37
• @snowflake1980 Please try to adapt my code and tell me what problems you can't solve, rather than telling me what the solution should be. Or edit the question and describe the algorithm you want to implement in detail. Apr 17 '17 at 19:55