1
$\begingroup$

The random walks start at $(x,y)=(0,0)$ on an infinite chessboard which covers the whole upper plane. Let's say $(0,0)$ is white.

Random walk 1: At every step, I always go up one square, and either one square to the left or to the right with probability $1/2$ for each. (so the displacement occurs only on white squares)

After many random walks 1 stopped at step $t$, the final values of $x$ (position of the end of the paths) are stored and their standard deviation $\sigma_1$ is computed

Random walk 2: On each square of the chessboard, a normal number following $N(0,1)$ is placed randomly. An algorithm computes for every connected path of $t$ steps on white squares the sum of the Gaussian numbers encountered and chooses the path whose corresponding sum is minimal. The end values of $x$ are stored and their standard deviation $\sigma_2$ is computed, for many random walks of length $t$ (the same amount of samples than for random walk $1$).

Should $\sigma_1$ and $\sigma_2$ differ ?

Context: I am asking this question because I was tasked to design an algorithm which picks the path minimizing the sum of Gaussian numbers, and wanted to check my results with a simpler problem which I think is equivalent. I programmed the two algorithms, and get different values for the $\sigma_i$, although I can't see how a significant difference can be justified.

Actually, for the random walk $1$, I didn't need to even code anything, I could solve it using combinatorics too. A random path is basically picked uniformly. All paths have the same length, but there are more paths leading to an end position close to the center. Computing the probabilities I can infer $\sigma_1$ easily.

In random walk $2$, the setting seems to be the same... there can only be one path minimizing the sum, and each path has the same length, so every path has the same probability to be chosen. Using the combinatorics argument, $\sigma_2$ should be the same as $\sigma_1$

So, are my maths wrong or is my algorithm faulty ?

$\endgroup$
  • 1
    $\begingroup$ The title has already been corrected, but for future reference, for the plural of scenario refer to english.stackexchange.com/questions/11775/… $\endgroup$ – David K Nov 11 '16 at 14:31
  • 1
    $\begingroup$ In RW2 do you restrict the paths to simple paths or are the paths allowed to cycle (between squares with negative gaussians). Also, are the steps restricted to squares that share a corner? $\endgroup$ – A.G. Nov 12 '16 at 3:18
  • $\begingroup$ @A.G Good point, no they don't cycle. At every step, it always go forwards one square and goes either right or left. The shape of the paths are like RW1, but the probability laws aren't the same $\endgroup$ – Evariste Nov 12 '16 at 10:43
2
$\begingroup$

Answering self:

$\sigma_2>\sigma_1$

The two problems are not equivalent because in random walk $1$, a random path is chosen uniformly among the possible ones, but not in random walk $2$

Indeed, in random walk $2$, despite being the same length, they cross and share Gaussian numbers, especially near the center. So one single number will affect several paths at the same time (either favorably or unfavorably), and cause the walk to either avoid or be attracted to the center, widening the variations of the ending positions.

$\endgroup$
1
$\begingroup$

This is a partial answer. In RW1 the end point will be $(X,t)$ where $X=\sum_1^t Y_k$ and the $Y_k$'s are independent random variables with $P(Y_k=-1)=P(Y_k=1)=1/2$. The variance of each of the $Y_k$'s is $1$ and therefore $$ \sigma_1=\sqrt{t}. $$

$\endgroup$
  • $\begingroup$ Yes, thanks for pointing that out. I was using the combinatorics argument mainly to try and find $\sigma_2$ since I can't find an easy way to compute it because of correlations, but it seems like it isn't valid and I get numerically $\sigma_2 \approx 2/3$ $\endgroup$ – Evariste Nov 12 '16 at 11:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.