Zelaron Gaming Forum

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



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



[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:



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



[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





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

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

Anyway, I like your approach. Have you checked your your first integral numerically (for reasonable values of and 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

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



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 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 variables. Perhaps I could compute the average of R by assuming it to be a sum of the and using the central limit theorem, but then I need both the average and standard deviation of my . 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 with . I figured that the process is okay, though, since by definition



and therefore



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 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



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 per step ranging from 1 to 2d. I can then write

.

This means that would increment by +1 if and -1 if , would increment by +1 if and -1 if 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 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



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)



where



Pushing the 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...)



where



If the 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 , where 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:



All you have to do is supply the , where 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 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

for so the product is

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 in dimensions that starts at the origin corresponds to a word of length from the alphabet .

For instance, if you're interested in walks from to in steps, consider the word , where

.

The and characters correspond to steps in the positive and negative directions in dimension , respectively. The :es are characters (directions) yet to be selected from . If we walk in the order prescribed from left to right in , by the time we reach the :es, we will have reached in our walk.

If we consider the first two :es from the left, we can replace them with any pair of and (for fixed ) and still be in after these two additional steps. Repeating this for each consecutive pair of :es, assuming that we have an even number of :es, the resulting string describes a walk from the origin to in steps.

In this particular example, it is realized that we can represent a selection of three pairs of and 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 and , two pairs of and , and one pair of and (thus 0+2+1 gives rise to the string Each such sum with three summands (where the summands are nonnegative integers that sum to half the number of :es) gives us a walk to 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) =



Dividing N by the total number of walks in 20 steps () yields the probability that we end up in after 20 steps.

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



we get that the probability that we end up in after steps is given by



where the sum is taken over all nonnegative integers such that

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:56 AM.

Powered by vBulletin® Version 3.8.2
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
This site is best seen with your eyes open.