Zelaron Gaming Forum  
Register Stats Arcade Portal Forum FAQ Members List Social Groups Calendar Search Today's Posts Mark Forums Read
Go Back   Zelaron Gaming Forum > The Zelaron Nexus > Science and Art

 
 
Thread Tools Display Modes

 
Random walk in arbitrary dimension
Reply
Posted 2015-04-18, 06:31 PM
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?

Last edited by Demosthenes; 2015-04-18 at 06:36 PM.
Old
Profile PM WWW Search
Demosthenes seldom sees opportunities until they cease to beDemosthenes seldom sees opportunities until they cease to beDemosthenes seldom sees opportunities until they cease to beDemosthenes seldom sees opportunities until they cease to be
 
Demosthenes
 



 
Reply
Posted 2015-04-18, 07:52 PM in reply to Demosthenes's post "Random walk in arbitrary dimension"
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.
Old
Profile PM WWW Search
Demosthenes seldom sees opportunities until they cease to beDemosthenes seldom sees opportunities until they cease to beDemosthenes seldom sees opportunities until they cease to beDemosthenes seldom sees opportunities until they cease to be
 
Demosthenes
 



 
Reply
Posted 2015-04-18, 09:36 PM in reply to Demosthenes's post "Random walk in arbitrary dimension"
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.

Last edited by WetWired; 2015-04-18 at 09:38 PM.
Old
Profile PM WWW Search
WetWired read his obituary with confusionWetWired read his obituary with confusionWetWired read his obituary with confusionWetWired read his obituary with confusion
 
WetWired
 



 
Reply
Posted 2015-04-19, 03:30 AM in reply to Demosthenes's post "Random walk in arbitrary dimension"
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.
"Stephen Wolfram is the creator of Mathematica and is widely regarded as the most important innovator in scientific and technical computing today." - Stephen Wolfram

Last edited by Chruser; 2015-04-19 at 04:58 AM.
Old
Profile PM WWW Search
Chruser shouldn't have fed itChruser shouldn't have fed itChruser shouldn't have fed itChruser shouldn't have fed itChruser shouldn't have fed it
 
 
Chruser
 



 
Reply
Posted 2015-04-19, 02:35 PM in reply to Chruser's post starting "\int_{-\pi}^{\pi} e^{x(\cos..."
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.
Old
Profile PM WWW Search
Demosthenes seldom sees opportunities until they cease to beDemosthenes seldom sees opportunities until they cease to beDemosthenes seldom sees opportunities until they cease to beDemosthenes seldom sees opportunities until they cease to be
 
Demosthenes
 



 
Reply
Posted 2015-04-19, 10:11 PM in reply to Demosthenes's post starting "Thanks for the comments! And sorry,..."
Demosthenes said: [Goto]
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.
"Stephen Wolfram is the creator of Mathematica and is widely regarded as the most important innovator in scientific and technical computing today." - Stephen Wolfram

Last edited by Chruser; 2015-04-19 at 10:41 PM.
Old
Profile PM WWW Search
Chruser shouldn't have fed itChruser shouldn't have fed itChruser shouldn't have fed itChruser shouldn't have fed itChruser shouldn't have fed it
 
 
Chruser
 



 
Reply
Posted 2015-04-19, 10:54 PM in reply to Chruser's post starting "It wasn't really ambiguous, I just..."
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.

Last edited by Demosthenes; 2015-04-19 at 11:00 PM.
Old
Profile PM WWW Search
Demosthenes seldom sees opportunities until they cease to beDemosthenes seldom sees opportunities until they cease to beDemosthenes seldom sees opportunities until they cease to beDemosthenes seldom sees opportunities until they cease to be
 
Demosthenes
 



 
Reply
Posted 2015-04-20, 01:06 AM in reply to Demosthenes's post starting "I tried using my new expansion for R...."
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...
"Stephen Wolfram is the creator of Mathematica and is widely regarded as the most important innovator in scientific and technical computing today." - Stephen Wolfram

Last edited by Chruser; 2015-04-20 at 01:20 AM.
Old
Profile PM WWW Search
Chruser shouldn't have fed itChruser shouldn't have fed itChruser shouldn't have fed itChruser shouldn't have fed itChruser shouldn't have fed it
 
 
Chruser
 



 
Reply
Posted 2015-04-20, 02:02 AM in reply to Chruser's post starting "The integral seems fine for d=1 (both..."
You are correct, again. I'm lost at this point. Don't know what's wrong. Giving up for now.

Thanks.
Old
Profile PM WWW Search
Demosthenes seldom sees opportunities until they cease to beDemosthenes seldom sees opportunities until they cease to beDemosthenes seldom sees opportunities until they cease to beDemosthenes seldom sees opportunities until they cease to be
 
Demosthenes
 



 
Reply
Posted 2015-04-20, 05:36 AM in reply to Demosthenes's post starting "You are correct, again. I'm lost at..."
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 summation is taken over all nonnegative integers such that
"Stephen Wolfram is the creator of Mathematica and is widely regarded as the most important innovator in scientific and technical computing today." - Stephen Wolfram
Old
Profile PM WWW Search
Chruser shouldn't have fed itChruser shouldn't have fed itChruser shouldn't have fed itChruser shouldn't have fed itChruser shouldn't have fed it
 
 
Chruser
 



 
Reply
Posted 2015-04-22, 12:38 AM in reply to Chruser's post starting "I played around a bit with the..."
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.
Old
Profile PM WWW Search
Demosthenes seldom sees opportunities until they cease to beDemosthenes seldom sees opportunities until they cease to beDemosthenes seldom sees opportunities until they cease to beDemosthenes seldom sees opportunities until they cease to be
 
Demosthenes
 



 
Reply
Posted 2015-04-23, 01:15 AM in reply to Demosthenes's post starting "Sorry for being slow. I think I've..."
That doesn't sound very fun.

Remind me to capacitate myself to work on problems like this without any teaching duties.
"Stephen Wolfram is the creator of Mathematica and is widely regarded as the most important innovator in scientific and technical computing today." - Stephen Wolfram
Old
Profile PM WWW Search
Chruser shouldn't have fed itChruser shouldn't have fed itChruser shouldn't have fed itChruser shouldn't have fed itChruser shouldn't have fed it
 
 
Chruser
 
 

Bookmarks

« Previous Thread | Next Thread »

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
Thread Tools
Display Modes

Posting Rules [Forum Rules]
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts
BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Forum Jump

Similar Threads
Thread Thread Starter Forum Replies Last Post
Random 35 Tracks Tape. Mdselctr Science and Art 1 2009-09-24 05:59 PM
Random Title Chruser Forum News, Suggestions and Discussion 29 2002-05-14 09:16 PM


All times are GMT -6. The time now is 03:18 PM.
'Synthesis 2' vBulletin 3.x styles and 'x79' derivative
by WetWired the Unbound and Chruser
Copyright ©2002-2008 zelaron.com
Powered by vBulletin® Version 3.8.2
Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.
This site is best seen with your eyes open.