# Random permutations from Brownian motion

Let $B(t)$ be a Brownian motion. The ordering of $(0, B(1), ..., B(n-1))$ is a random permutation in $S_n$. This is not uniform for $n>2$ since the probabilities of the identity permutation $[123...n]$ and of $[n(n-1)...1]$ are $1/2^{n-1}$, not $1/n!$. (For $n=3$, the other $4$ permutations all have probability $1/8$.)

If $B(t)$ is conditioned to return to the origin at time $n$, this gives a different distribution on $S_n$. For $n=3$ it is uniform, and I had hoped it would be uniform for all $n$, but this is not the case. For $n=4$, permutations appear to fall into $4$ classes of size $4$ or $8$, with constant probabilities on these classes.

## What are these distributions on $S_n$? In particular, which permutations are the least/most likely and what are their probabilities?

One approach for the unpinned Brownian motion is to consider $(B(1)-B(0),...,B(n)-B(n-1))$, a spherically symmetric Gaussian. The permutation is a function of the direction from the origin, and this direction is uniformly distributed on the sphere. The probability of a permutation corresponds to the ratio between the volume of a spherical simplex and the volume of the whole sphere. An analogous method works for pinned Brownian motion. However, I don't see a good way to compute those volumes.

-
For the unpinned Brownian motion, it seems to me that any permutation has probability at most $1/2^{n-1}$. To achieve any fixed permutation, for each $k$, condionnally on $(B(0), \dots, B(k)$, the difference $B(k+1)-B(k)$ must belong to some interval which is either contained in $[0,+\infty)$ or $(-\infty,0]$. This happens with probability less than $1/2$. – Guillaume Aubrun May 25 '12 at 16:32
Yes, that's correct. Given a permutation $\pi$ in $S_n$ ending in $n$, construct a permutation $\pi'$ in $S_{n+1}$ by appending $n+1$. $Prob(\pi') = 1/2 Prob(\pi)$. Also, construct $\pi''$ in $S_{n+2}$ by appending $n+2,n+1$. $Prob(\pi'') = 1/8 Prob(\pi)$. This can be generalized further to "decomposable" permutations so that for some $i$, $\pi(i) = i$ and for all $j\lt i$, $\pi(j)\lt i$. A decomposable permutation can be viewed as a permutation $\sigma^-$ in $S_i$ glued to a permutation $\sigma^+$ in $S_{n-i+1}$, and the probability is $Prob(\sigma^-)Prob(\sigma^+)$. – Douglas Zare May 25 '12 at 23:02

Here is some progress I've made in answering my own question, the distribution on $S_4$. For any symmetric continuous distribution for $B(i+1)-B(i)$,

$$Prob(1234) = Prob(4321) = 1/8 \\\\ Prob(1243) = Prob(4312) = Prob(3421) = Prob(2134) = 1/16 \\\\ Prob(1324) = Prob(4231) = 1/24 \\\\ Prob(1342) = Prob(4213) = Prob(2431) = Prob(3124) = \alpha \\\\ Prob(1432) = Prob(4123) = Prob(2341) = Prob(3214) = 1/16 - \alpha \\\\ Prob(1423) = Prob(4132) = Prob(3241) = Prob(2314) = 1/48 \\\\ Prob(2143) = Prob(3412) = 1/16 - \alpha \\\\ Prob(2413) = Prob(3142) = \alpha - 1/48$$

For example, we can compute $Prob(1423)=1/48$: Let $b(i) = B(i)-B(i-1)$. The condition is that $|b(1)|\gt|b(2)|\gt|b(3)|$, which happens with probability $1/6$, and $b(1)>0, b(2)<0, b(3)>0$, which is independent and happens with probability $1/8$.

$Prob(2143) = Prob(1432)$ by reordering the steps, switching the step $b(1)$ with $b(2)$.

$Prob(2431) + Prob(1432) = Prob(132)/2$ since either $2431$ or $1432$ occurs after $B(0)\lt B(2)\lt B(1)$ when $b(3)\lt 0$.

The value of $\alpha$ depends on the Gaussian assumption. If the random permutation were generated by ordering a random walk whose steps are uniform on $[-1,1]$, the value of $\alpha$ would be $1/24= 0.041667...$. For Brownian motion, $1/16 - \alpha$ is the fraction of the unit sphere satisfying $x \gt y+z, y \gt 0, z \gt 0$, a spherical triangle with angles $\pi/2, \arccos(1/\sqrt3), \arccos(1/\sqrt3)$. The area is $2 \arccos(1/\sqrt3) - \pi/2$, so $1/16 - \alpha = \arccos(1/\sqrt3)/(2\pi)-1/8$ and $\alpha = 3/16 - \arccos(1/\sqrt3)/(2\pi) = 0.035457...$.

Perhaps more symmetries between the cases would exist for a random walk with steps uniform on $[-1,1]$.

-
If they were uniform on $[-1,1]$, instead of a unit sphere you would have a unit cube. – Will Sawin May 27 '12 at 22:15

Brownian motion has what's called "independent" increments, right? So B(1)-B(0) is independent from B(2)-B(1),B(3)-B(2), etc. These increments will be Gaussian with mean 0 and variance 1.

Instead of computing the order distribution directly, we could look for general properties. If you ignore the first coordinate or ignore the last coordinate, you should induce the distribution for $S_{n-1}$.

I wonder if it's easier to take a random walk with unit steps and sample at N random times and consider the relative order of those positions.

-
Yes, the increments are independent for an unpinned Brownian motion. You can also get the distribution on $S_{n/2}$ by looking at $B(0), B(2),$ etc. I hadn't considered sampling at random times, but perhaps that would give another interesting distribution. – Douglas Zare Jun 11 '12 at 9:58