I recently read a small ACS education paper on random walks, where the authors essentially describe various physical phenomena such as poylmer folding from the vantage point of random walks. One aspect that was touched upon was the multinomial distribution to find the end to end distance of a polymer given a 3D random walk. Now, I have encountered the 1D random walk for polymers, and it was fairly straightforward to compute the end-to-end distance of an ideal polymer chain. However, I am struggling to understand the higher dimensional aspects.
For simplicity consider a random walk in 2D, that is only allowed movement in the poisitive or negative x-direction and similarly only positive or negative y-direction, all with equal probability. The walk is allowed to cross itself. Furthermore, the end to end distance vector, $\vec{r}$, with $N$ links is given by:
$$\vec{r} = \sum_{i=0}^{N} \vec{a_i}$$
Whereby $\vec{a_i}$ is a vector whose orientation can only be in the x or y direction (postive or negative). My issue is with setting up the multinomial expression to find the probability of obtaining a specific end-to-end distance, $\left|\vec{r}\right|$.
My approach would have been analogous to the 1D approach by first:
$$ \left|\vec{r}\right| = (x_+ – x_- + y_+ -y_-)a$$
$$N = (x_+ + x_- + y_+ +y_-)$$
Where $a = \left| \vec{a_i}\right|$ is the length of one link, $x_+$ denotes the amount of steps in the positive x-direction and $x_-$ the amount of steps in the negative x-direction (and same for $y$). In the 1D case it would now be possible to eliminate a variable, and write down the distribution for obtaining an end-to-end distance of $\left|\vec{r}\right|$ :
$$P(\left|\vec{r}\right|, N) = \frac{N!}{(\frac{\left|\vec{r}\right|}{2a} + \frac{N}{2})!( \frac{N}{2} – \frac{\left|\vec{r}\right|}{2a})!} \cdot (\frac{1}{2})^N$$
However, I can't seem to piece together such a distribution for higher dimensions.
Any hints would be appreciated!
Best Answer
I think you need one more slight edit to your post: in the body of the post, you have $$|\vec r| = (x_+ - x_- + y_+ - y_-) a$$ which you seem to have noted implicitly is problematic, because it could be negative. In the comments, you solved this with another minor correction: $$| \vec r| = |x_+ - x_- + y_+ - y_-| a$$ but this too doesn't work, because (for instance) if the walk has taken 3 steps north and 3 steps south, then we have $x_+ = y_- = 3$ and $x_- = y_+ = 0$, whence $|\vec r|$ is apparently 0, which is bad. You really need $$|\vec r| = (|x_+ - x_-| + |y_+ - y_-|)a$$ which gives a preview of why this will be so combinatorially obnoxious.
The fun thing about this 2D example that isn't present in the 1D example is that the collection of states with $|\vec r| = k$ is no longer convenient. In the 1D case, the states with $|\vec r| = 4$ are straightforward; they're $\pm 4$. But in the 2D case, the states with $|\vec r| = 4$ are rather complicated, consisting of $(\pm 4, 0), (\pm 3, \pm 1), (\pm 2, \pm 2), (\pm 1, \pm 3), (0, \pm 4)$ (16 states in total). Worse yet, the probabilities of arriving at those states are different; there is just one 4-step path from $(0, 0)$ to $(0, 4)$, for instance, but there are $\binom 4 2 = 6$ ways from $(0, 0)$ to $(2, 2)$.
What this suggests is that finding a probability function for $|\vec r|$ directly is going to be very complicated, and it won't be possible to do in a way that is at all conveniently parametrized in $N$ like the 1D case. (It will be possible, though laborious, to handle this for small fixed $N$, of course.)
The real problem here for what you're trying to do is that we do have a convenient expression for the probability function of the radius $R$ -- as in, the genuine Euclidean distance radius, not the graph distance metric you're interested in; Rayleigh showed that $P_N(R)$ is approximately $\frac{2R}{N} e^{-R^2 / N}$. This convenient expression suggests why one may be more challenging for you to obtain; level sets of the form $|\vec r| = k$ are squares (rotated $45^{\circ}$), whereas level sets of the form $R = k$ are circles. Radial "sameness" is conveyed in a circular fashion, not through the squares.
ADDENDUM to address your comment (since my response would not also fit inside a comment):
Well -- yes and no. If what you want is an asymptotic expression that holds for large $N$, then Euclidean distance is the way to go, and Rayleigh already did the heavy lifting for you. If what you want is an exact expression for the Euclidean radius, then unfortunately that will also be difficult because of the obnoxious translation between the continuous nature of the Euclidean radius and the discrete nature of the grid $\mathbb Z^2$. This is one of the places where it bites you a bit that you're working with a discrete random walk instead of, say, a Brownian motion, which would admit cleaner statements of this sort.
This statement isn't quite right either, unfortunately. In the 2D case, Rayleigh's findings show that $R$ (the Euclidean radius, again) has the distribution of $\sqrt{X^2 + Y^2}$, where $X, Y$ are independent normal variables. You can call this distribution either a Rayleigh distribution or a Chi distribution (since it is the square root of a Chi-square distribution), but it's not simply absolute value of a normal distribution. (Connection to the 1D case: in that case, the distribution of the $R$, which is the same as $\vec r$, is $\sqrt{X^2} = |X|$ for a single normal variable; this is the so-called half-normal distribution, or the aforementioned Chi distribution with 1 df.)
Back to the 2D case, the moral lesson here is that the Rayleigh distribution is perfect for $R$ but not $|\vec r|$; and yet, it's also not terrible for $|\vec r|$, because a square with side length $s$ can be placed inside and outside of circles with radii $a, b$ for some $a, b$ that are not too far apart and related nicely to $s$ (but that I'm too lazy to compute at the moment). This means that although the Rayleigh distribution doesn't describe the probability distribution of $|\vec r|$ perfectly, you could use it to get decent upper and lower bounds on it.
But of course, you're right -- most of the statements I'm making are of an asymptotic nature and don't help that much for determining things for small $N$. To find the probability that $|\vec r| = k$, we have a few jobs:
Step 2 might get us to what you've been secretly itching for the whole time -- something akin to a multinomial distribution. It's worth stopping to do very small examples of this by hand, because you'll get a sense of the complexity of the problem. If $W_6$ is the position of the walk after 6 steps:
\begin{align*} \mathbb P(W_6 = (6, 0)) &= \left( \frac 1 4 \right)^6 \\ \mathbb P(W_6 = (3, 3)) &= \binom 6 3 \left( \frac 1 4 \right)^6 \\ \mathbb P(W_6 = (1, 1)) &= \sum_{k = 1, 3, 5} \binom 6 k \cdot \binom k {(k-1)/2} \cdot \binom {6-k}{(6-k-1)/2} \left( \frac 1 4 \right)^4 \end{align*}
The logic for the last line is: choose which $k$ of the 6 moves will be up/down (instead of left/right). This breaks the 6 moves into two groups (i.e. the up/down group and the left/right group). Then, within each group, what moves we need are already predetermined; the up/down group must have 1 more up than down, and the left/right group must have 1 more right than left. All we need is to account for how many ways there are to reorder the proper number of sequences.
The expression I wrote can be cleaned up considerably but I tried to leave it in a format that would motivate why it is valid. And of course, even after cleaning it up, there's still a $\sum$ in front of it. It's pretty gross. You can use this kind of approach to brute-force some analysis for $|\vec r|$, but depending on your application for this work, a simulation-based approach may well be a much better route to go.