Register Stats Arcade Portal Forum FAQ Members List Social Groups Calendar Search Today's Posts Mark Forums Read
 Zelaron Gaming Forum Random walk in arbitrary dimension

 Random walk in arbitrary dimension
 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 $\reverse \rho^L_{\vec{r}/a, t/\tau} = \langle \delta_{\vec{R}(t), \vec{r}} \rangle.$ Here, $\vec{r}$ 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. $\vec{R}(t)$ is a random variable consistent with the final position of the walk. $L$ 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.$ $R_i$ and $r_i$ 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 $R_i$ as follows: $\reverse R_i = \sum_j^{t/\tau} \xi_{j,i}.$ Here, my $\xi_{j,i}$ represent the change in $R_i$ 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.$ $\xi_{j,i}/a$ 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? Last edited by Demosthenes; 2015-04-18 at 06:36 PM.
 Profile PM WWW Search
Demosthenes

 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.
 Profile PM WWW Search
Demosthenes

 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.
 Profile PM WWW Search
 WetWired

 Posted 2015-04-19, 03:30 AM in reply to Demosthenes's post "Random walk in arbitrary dimension" $\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. "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.
 Profile PM WWW Search
Chruser

 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 $\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.
 Profile PM WWW Search
Demosthenes

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 $\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.
"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.
 Profile PM WWW Search
Chruser

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 $\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 #include #include 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
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.

Last edited by Demosthenes; 2015-04-19 at 11:00 PM.
 Profile PM WWW Search
Demosthenes

 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 $\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... "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.
 Profile PM WWW Search
Chruser

 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.
 Profile PM WWW Search
Demosthenes

 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 $\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}.$ "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; 2017-11-22 at 07:37 AM.
 Profile PM WWW Search
Chruser

 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.
 Profile PM WWW Search
Demosthenes

 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
 Profile PM WWW Search
Chruser

 Bookmarks

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

 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 User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home The Zelaron Nexus     Forum News, Suggestions and Discussion         Test Forum             RSS News     Member Introductions     The Lounge         World Record Thread     General Discussion         News and Events         Life Discussion         Opinion and Debate     Science and Art         Tech Help         Science and Technology News         Principia Mathematica     The Anime Corner Zelaron Gaming     General Gaming         Deus Ex: Human Revolution     DayZ     Diablo III         Diablo I & II             Diablo Cube             D2 PvP             D2 Marketplace     RPGMaker

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

All times are GMT -6. The time now is 05:52 PM.
 -- Synthesis 2 (Original Blue) -- Synthesis 2 (Lava Ashes) -- Synthesis 2 (Liquid Violet) -- Ocean -- Zephios -- HUD Revision 'Synthesis 2' vBulletin 3.x styles and 'x79' derivative by WetWired the Unbound and Chruser Copyright ©2002-2008 zelaron.com