Zelaron Gaming Forum - View Single Post

Demosthenes · 06:37 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}.$