Zelaron Gaming Forum - Random walk in arbitrary dimension

Zelaron Gaming Forum (http://zelaron.com/forum/index.php)

- Science and Art (http://zelaron.com/forum/forumdisplay.php?f=344)

- - Random walk in arbitrary dimension (http://zelaron.com/forum/showthread.php?t=53891)

Demosthenes

2015-04-18 05:31 PM

Random walk in arbitrary dimension

I'm trying to find the probability distribution for a random walk on a lattice with lattice constant a in arbitrary dimension d. The rules for my walk is that in each step the walker has to move to an adjacent spot on the lattice along one and only one component. My logic is as follows.

My probability distribution ought to be

$\reverse \rho^L_{\vec{r}/a, t/\tau} = \langle \delta_{\vec{R}(t), \vec{r}} \rangle.$

Here, [itex]\vec{r}[/itex] is my final position vector from the starting point of the walk, t is the total time since we started the walk and $\tau$ the time per step. [itex]\vec{R}(t)[/itex] is a random variable consistent with the final position of the walk. [itex]L[/itex] simply indicates that we are on a lattice, and is merely included for consistency with my textbook. The delta-function is a d-dimensional delta function, d being the dimensionality of my lattice. Since the delta-function is normalized the right-hand side should represent the probability distribution of my random walk. Using the Fourier representation of a delta function, and the fact that a multidimensional delta-function is a product of single dimensional delta-functions, I can rewrite my probability distribution as

$\reverse \rho^L_{\vec{r}/a, t/\tau} = \langle \prod_{i=1}^d \int_{- \pi}^{\pi} \frac{dq_i}{2 \pi} e^{iq_i(R_i(t)-r_i)/a} \rangle.$

[itex]R_i[/itex] and [itex]r_i[/itex] represent the ith component of my random variable and the ith component of the position on my lattice whose probability I want to find respectively. I can rewrite [itex]R_i[/itex] as follows:

$\reverse R_i = \sum_j^{t/\tau} \xi_{j,i}.$

Here, my [itex]\xi_{j,i}[/itex] represent the change in [itex]R_i[/itex] on step j. Writing [itex[M=t/\tau[/itex] my probability distribution is therefore

$\reverse \rho^L_{\vec{r}/a, t/\tau} = \prod_{i=1}^d \int_{- \pi}^{\pi} \frac{dq_i}{2 \pi} e^{-iq_ir_i/a} \langle \prod_{j=1}^M e^{iq_i \xi_{j,i}/a} \rangle.$

[itex]\xi_{j,i}/a[/itex] can take on values of +1, 0, or -1 with probability 1/2d, (d-1)/d, and 1/2d respectively. So

$\reverse \langle e^{iq_i \xi_{j,i}/a} \rangle = \frac{e^{iq_i}}{2d} + \frac{d-1}{d} + \frac{e^{-iq_i}}{2d} = \frac{\cos \left( q_i \right) + d - 1}{d}$

$\reverse \rho^L_{\vec{r}/a, t/\tau} = \prod_{i=1}^d \int_{- \pi}^{\pi} \frac{dq_i}{2 \pi} e^{-iq_ir_i/a} \left[ \frac{\cos \left( q_i \right) + d - 1}{d} \right]^M$$

Most of the probability distributions I'v seen for the d-dimensional random walk are based on combinatoric considerations. Can anyone confirm that the logic and final expression for my probability distribution are correct. Also, does anyone have any advice on how to proceed with the final integral? Chruser? WW? Anyone?

Also, I don't know how to do inline latex on Zelaron :( Can one of you guys fix my post for me so that the inline latex shows up?

Demosthenes

2015-04-18 06:52 PM

Computer simulations show my model is only accurate for d=1. I don't understand why. I used Wolfram Alpha to numerically evaluate my integral.

WetWired

2015-04-18 08:36 PM

Unfortunately, I'm not that much of a math nerd. Chruser may have some insight to impart, however. As for the inline latex, all latex is inline on this site. Just use the normal tag.

Chruser

2015-04-19 02:30 AM

$\reverse \int_{-\pi}^{\pi} e^{x(\cos x)^k}\mathrm{d}x$ looks like one of those almost-friendly integrals that end up being analytically untractable. I'd play around with the exponential integral function, or some weighted average thereof, since $\reverse \int e^{e^{ix}}\mathrm{d}x = -i\mathrm{Ei}(e^{ix}) + C.$

Anyway, I like your approach. Have you checked your your first integral numerically (for reasonable values of $\reverse R_i(t)$ and $\reverse r_i$ in at least two dimensions), or just the last one? The first one looks fine, but I tend to become particularly wary when integrating wrt another variable can create a stochastic integral.

My other, dumb 10:15-AM-with-no-sleep guess for a possible culprit is that

$\reverse \langle e^{iq_i \xi_{j,i}/a} \rangle = \frac{e^{iq_i}}{2d} + \frac{d-1}{d} + \frac{e^{-iq_i}}{2d}$ is a too hasty conclusion from the obvious probabilities for each direction above.

Demosthenes

2015-04-19 01:35 PM

Thanks for the comments!

And sorry, it's clear that the way my final expression displays makes its meaning ambiguous. The expression in block parenthesis is not meant to be part of the exponent. Perhaps this makes the integral clearer

$\reverse \rho^L_{\vec{r}/a, t/\tau} = \prod_{i=1}^d \int_{- \pi}^{\pi} \frac{dq_i}{2 \pi} exp \left[-iq_ir_i/a \right] \left[ \frac{\cos \left( q_i \right) + d - 1}{d} \right]^M$$

Does that look any more analytically approachable to anyone? Meh, it probably doesn't matter since my result doesn't hold for anything more than d=1.

It's a little unclear to me how I would find a theoretical average for $\reverse \vec{R}_i$ which is why I haven't used my first integral directly. I simply don't know how to compute it. This is why I introduced the $\reverse \xi$ variables. Perhaps I could compute the average of R by assuming it to be a sum of the $\reverse \xi$ and using the central limit theorem, but then I need both the average and standard deviation of my $\reverse \xi$ . It's also completely possible that what I'm saying is complete gibberish right now, I'm just thinking out loud.

I'm unfamiliar with stochastic integrals, and what difficulties might be introduced when replacing $\reverse R$ with $\reverse \xi$ . I figured that the process is okay, though, since by definition

$\reverse R_i = \sum_j \xi_j,$

and therefore

$\reverse \langle R_i \rangle = \langle \sum_j \xi_{j,i} \rangle = \sum_j \langle \xi_{j,i} \rangle.$

My suspicion is also that my calculation for the average of the exponential is wrong. One possible pitfall in my model is that for fixed j the $\reverse \xi_{j,i}$ are not independent, since only one member of that subset can be nonzero, which I have not accounted for explicitly. I know that for random variables there are sometimes extra terms that need to be added for certain operations that you wouldn't expect, i.e

$\reverse M(A \cup B) = M(A) + M(B) - M(A \cap B)$

where M is the measure of a set. The last term comes up somewhat unexpectedly unless you've thought about that kind of operation before. I'm not sure if there might be something like that in the computation of the exponential average that I might not have accounted for. That's something I can look into.

The alternative solution I'm considering trying is to decompose my R vector a little differently. I'm thinking of having a single $\reverse \xi_j$ per step ranging from 1 to 2d. I can then write

$\reverse R_i = \sum_j \delta_{(\xi_j, 2i-1)} - \delta_{(\xi_j, 2i)}$ .

This means that $\reverse R_1$ would increment by +1 if $\reverse \xi_j=1$ and -1 if $\reverse \xi_j=2$ , $\reverse R_2$ would increment by +1 if $\reverse \xi_j=3$ and -1 if $\reverse \xi_j=4$ and so on. This should decompose my R correctly as far as I can tell, and should get rid of any dependency issues that come up since there is only one $\reverse \xi$ per step. I'll try this later today and let you know if it works. I'll also look into how to calculate the average of a sum of mutually dependent variables.

Thanks again, guys.

Chruser

2015-04-19 09:11 PM

Quote:

Originally Posted by Demosthenes (Post 705196)

And sorry, it's clear that the way my final expression displays makes its meaning ambiguous. The expression in block parenthesis is not meant to be part of the exponent. Perhaps this makes the integral clearer

$\reverse \rho^L_{\vec{r}/a, t/\tau} = \prod_{i=1}^d \int_{- \pi}^{\pi} \frac{dq_i}{2 \pi} exp \left[-iq_ir_i/a \right] \left[ \frac{\cos \left( q_i \right) + d - 1}{d} \right]^M$$

It wasn't really ambiguous, I just fucked up. Not that you probably need that integral, but it looks like a straightforward application of Euler's formula and the multinomial theorem, if I'm reading it correctly... Something like (using k instead of i as the iteration variable in the product to prevent it from being mixed up with the imaginary unit)

$\reverse I = \int_{- \pi}^{\pi} \frac{dq_k}{2 \pi} exp \left[-kq_kr_k/a \right] \left[ \frac{\cos \left( q_k \right) + d - 1}{d} \right]^M = \frac{1}{2\pi (2d)^M}\int_{-\pi}^{\pi}e^{\Omega q_k} (A + B + C)^M\mathrm{d}q_k = \frac{1}{2\pi (2d)^M}\int_{-\pi}^{\pi}e^{\Omega q_k} \sum_{n_1 + n_2 + n_3 = M} {M \choose n_1, n_2, n_3} A^{n_1}B^{n_2}C^{n_3}\mathrm{d}q_k $

where

$\reverse \Omega=-k r_k/a,\, A = e^{i q_k},\, B = e^{-i q_k},\, C = 2(d-1).$

Pushing the $\reverse e^{\Omega q_k}$ factor inside the summation sign, then switching the order of summation and integration shouldn't be an issue since they've both got finite bounds, so you get (if I didn't mess up the algebra, too...)

$\reverse I = \frac{1}{2\pi (2d)^M}\sum_{n_1+n_2+n_3=M}{M \choose n_1,n_2,n_3} \frac{(2d-2)^{n_3}}{Q} (e^{\pi Q} - e^{-\pi Q}),$

where

$\reverse Q = -kr_k/a + (n_1-n_2)i.$

If the $\reverse i$ factor was meant as the imaginary unit instead, the result isn't very different. I don't particularly like mixing capital pi with capital sigma notation, but it seems hard to avoid without combinatorial arguments sometimes.

Demosthenes

2015-04-19 09:54 PM

I tried using my new expansion for R. Got the same result, as expected. I figured I'd carry out the math though to check for the possibility of there being some hidden term or factor that pops out. So, either my final integral in the original post is correct or I'm messing up my expectation algebra somewhere.

For some reason I never considered doing a multinomial expansion, but that definitely seems to be the way to go. Your evaluation of the integral even appears like what I'd expect the combinatoric solution to be, which is promising. I'm wondering if perhaps I messed up entering my integral expression into the numerical integrator.

Could someone else possibly check the final numerical integral in the original post for me using $\reverse r_i/a = n_i$ , where $\reverse n_i$ is the ith point on the lattice whose probability we're looking for. Just to make sure I'm not doing something incredibly stupid. I will post some code that the numerical evaluation can be checked against.

The code is as follows

Code:

#include <stdio.h>

#include <stdlib.h>

#include <time.h>



int main(void)

{

        int trialPoint[] = {1,1,1,1}; // Enter the point whose probability you want to find

        int maxStep = 10; // Maximum number of steps per walk

        int trials = 10000000; // Number of walks

        

        int dimension = sizeof(trialPoint)/sizeof(trialPoint[0]); // lattice dimension

        int lattice[dimension]; // Holds the value of where you are in each component of lattice

        

        srand(time(NULL));

        

        int counter = 0; // Holds number of trials that end at desired point

        

        for(int trial = 0; trial<trials; trial++)

        {

                for(int i = 0; i<dimension; i++) // Sets initial position on lattice to (0,0,0,...)

                {

                        lattice[i]=0;

                }

                

                // Following segment of code steps forward or backwards in a single dimension per loop

                for(int step = 0; step<10; step++) 

                {

                        int forwardBackward = rand()%2;

                        int component = rand()%dimension;

                        if(forwardBackward==1)

                        {

                                lattice[component]++;

                        }

                        else

                        {

                                lattice[component]--;

                        }

                        

                }

                

                // Check to see if end-position on lattice is desired position set in trialPoint array

                // If so, counter variable is incremented

                int match = 1;

                for(int i = 0; i<dimension; i++)

                {

                        if(lattice[i]!=trialPoint[i])

                        {

                                match = 0;

                                break;

                        }

                }

                if(match == 1)

                {

                        counter++;

                }

        }

        

        printf("%d/%d simulated probability\n", counter, trials);

        

        return 0;

}

This code simulates the random walk. The only thing you should need to modify in the code is if you want to change the trial point, you can do so in the first line in the main function. The code can handle arbitrary dimensions, so feel free to change it to any dimension as needed. You can also modify the number of steps a walk takes per trial and the total number of trials in the following two lines respectively. Note, that the code assumes that the trial point is the lattice-point number with respect to the origin, and doesn't take the lattice constant a into consideration. That is why I recommend evaluating the following integral:

$\reverse \rho^L_{\vec{r}/a, t/\tau} = \prod_{i=1}^d \int_{- \pi}^{\pi} \frac{dq_i}{2 \pi} e^{-iq_in_i} \left[ \frac{\cos \left( q_i \right) + d - 1}{d} \right]^M.$

All you have to do is supply the $\reverse n_i$ , where $\reverse n_i = trialPoint[i-1]$ i.e. and so on. The i in the exponential of the integral is indeed the imaginary unit. If someone could run my code and compare the answer with the numerical integral provided above, it'd be much appreciated. When I tried it, the answers did not coincide except for d=1. Also, M in the equation is maxStep from the code, and d is dimension of the lattice.

Chruser

2015-04-20 12:06 AM

The integral seems fine for d=1 (both for obvious inputs, like a probability of 1/2 for the point x=1 after one step, and less obvious ones simulated by your program).

For d=2 dimensions, a simple case for which the distribution seems to fail is the point $\reverse \vec{r}=(1,1)$ and M=2 steps, which should yield a probability of 1/8 (each walk corresponds to a word of length 2 in the alphabet {U,D,L,R}. There are 16 such words in total, of which only UR and RU correspond to a desired walk). In this case, the integral becomes

$\reverse \frac{1}{2\pi}\int_{-\pi}^{\pi}e^{-iq_i}\left[\frac{\cos(q_i) + 1}{2}\right]^2\mathrm{d}q_i = \frac{1}{4}$ for $\reverse i\in\{1,2\},$ so the product is $\reverse \frac{1}{16}\,\neq\,\frac{1}{8}.$

Actually, this seems like a pretty fun problem to solve by counting words...

Demosthenes

2015-04-20 01:02 AM

You are correct, again. I'm lost at this point. Don't know what's wrong. Giving up for now.

Thanks.

Chruser

2015-04-20 04:36 AM

I played around a bit with the word-counting approach, which seems to have given me some promising results.

Each walk of length $\reverse M\ge 0$ in $\reverse n$ dimensions that starts at the origin corresponds to a word of length $\reverse M$ from the alphabet $\reverse A_n=\{d_1^+,d_1^-,d_2^+,d_2^-,\ldots,d_n^+,d_n^-\}$ .

For instance, if you're interested in walks from $\reverse (0,\,0,\,0)$ to $\reverse \vec{r} = (7,\,3,\,-4)$ in $\reverse M=20$ steps, consider the word $\reverse \Omega$ , where

$\reverse \Omega = d_1^+d_1^+d_1^+d_1^+d_1^+d_1^+d_1^+d_2^+d_2^+d_2^+ d_3^-d_3^-d_3^-d_3^-XXXXXX$ .

The $\reverse d_i^+$ and $\reverse d_i^-$ characters correspond to steps in the positive and negative directions in dimension $\reverse i$ , respectively. The $\reverse X$ :es are characters (directions) yet to be selected from $\reverse A_3$ . If we walk in the order prescribed from left to right in $\reverse \Omega$ , by the time we reach the $\reverse X$ :es, we will have reached $\reverse \vec{r}$ in our walk.

If we consider the first two $\reverse X$ :es from the left, we can replace them with any pair of $\reverse d_i^+$ and $\reverse d_i^-$ (for fixed $\reverse i$ ) and still be in $\reverse \vec{r}$ after these two additional steps. Repeating this for each consecutive pair of $\reverse X$ :es, assuming that we have an even number of $\reverse X$ :es, the resulting string describes a walk from the origin to $\reverse \vec{r}$ in $\reverse M$ steps.

In this particular example, it is realized that we can represent a selection of three pairs of $\reverse d_1^+$ and $\reverse d_1^-$ as the sum 3+0+0 (three pairs from the first dimension, none from the remaining two). Similarly, 0+2+1 represents a selection of no pairs of $\reverse d_1^+$ and $\reverse d_1^-$ , two pairs of $\reverse d_2^+$ and $\reverse d_2^-$ , and one pair of $\reverse d_3^+$ and $\reverse d_3^-$ (thus 0+2+1 gives rise to the string $\reverse d_1^+d_1^+d_1^+d_1^+d_1^+d_1^+d_1^+d_2^+d_2^+d_2^+ d_3^-d_3^-d_3^-d_3^-d_2^+d_2^-d_2^+d_2^-d_3^+d_3^-).$ Each such sum with three summands (where the summands are nonnegative integers that sum to half the number of $\reverse X$ :es) gives us a walk to $\reverse \vec{r}$ represented by distinct letters.

By counting the number of permutations of all words that arise from all such sums (3+0+0, 0+3+0, 0+0+3, 2+0+1, 2+1+0, 0+2+1, 1+2+0, 0+1+2, 1+0+2, 1+1+1), we get the total number of walks we seek (since no other walks of this type exist).

For this example, we get that the number of walks that we seek, N, is

(Number of walks arising from 3+0+0) + (Number of walks arising from 0+3+0) + ... + (Number of walks arising from 1+1+1) =

$\reverse \frac{20!}{(7+3)!\cdot(0+3)!\cdot3!\cdot0!\cdot0! \cdot 4!} \,+\, \frac{20!}{7!\cdot0!\cdot(3+3)!\cdot(0+3)!\cdot0! \cdot 4!} \,+\, \dots \,+\, \frac{20!}{(7+1)!\cdot(0+1)!\cdot(3+1)!\cdot(0+1)! \cdot(0+1)! \cdot (4+1)!}.$

Dividing N by the total number of walks in 20 steps ( $\reverse 6^{20}$ ) yields the probability that we end up in $\reverse \vec{r}$ after 20 steps.

This example is easily extended to the general case. For instance, using the notation

$\reverse [u]^+ = \max(0,u),\\ [u]^- = -\min(0,u),$

we get that the probability that we end up in $\reverse \vec{r} = (x_1,\,x_2,\,x_3,\ldots,x_n)$ after $\reverse M$ steps is given by

$\reverse \frac{M!}{(2n)^M}\cdot\sum\frac{1}{\prod_{k=1}^{n} ([x_k]^+ + i_k)! ([x_k]^- + i_k)!}$

where the sum is taken over all nonnegative integers $\reverse i_1, i_2, \ldots i_n$ such that $\reverse {i_1+i_2+\dots+i_n = \frac{M-(|x_1|+|x_2|+\dots+|x_n|)}{2}.$

Demosthenes

2015-04-21 11:38 PM

Sorry for being slow. I think I've solved it, and I will try and comment on your solution tomorrow. Exhausted at this point, and have a stack of papers to grade. :(

Chruser

2015-04-23 12:15 AM

That doesn't sound very fun. :(

Remind me to capacitate myself to work on problems like this without any teaching duties.

All times are GMT -6. The time now is 04:59 PM.