Random permutations from Brownian motion

Question

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.

Answer 1

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]$.

Answer 2

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.

Answer 3

Since my answer is long, here is a loose heuristic summary answer: A permutation $\pi$ such that $|\pi(i+1) - \pi(i)|$ is large for many values of $i$ occurs less frequently than permutations where such values are small.

The first results on this might be from Bandt and Shiha's 2005 paper Order patterns in time series, which gives the probability that $\pi \in S_n$ occurs as an ordinal pattern for AR(1) processes and fractional Brownian motion for $n = 3,4$. It includes Douglas Zare's answer for the case of ordinary Brownian motion. Another $n = 3,4$ answer is given in DeFord and Moore's Random walk null models for time series, which gives the probability that $\pi \in S_n$ occurs in a walk with uniform steps on $[b-1,b] \; \; \left(\frac{1}{2} \leq b \leq 1\right)$ as a piecewise-defined polynomial in $b$.

In John Mangual's 2012 answer, there is a suggestion to "look for general properties" instead of directly computing the distribution on $S_n$. This happens in The frequency of pattern occurrence in random walks, where Elizalde and Martinez showed that certain pairs of permutations occur with the same probability regardless of choice of density function for the steps. A matrix $L_\pi$ is introduced that maps the positive orthant to the region of steps that generate $\pi$. They show that if $L_\pi$ can be obtained from $L_\tau$ by permuting its rows and columns, then $\pi$ and $\tau$ occur with the same probability regardless of choice of step density function. The converse is conjectured to hold. A characterization for the pairs of permutations with equal frequencies independent of density choice is given in Martinez's thesis Equivalences on patterns in random walks via the all-subset (resonance) hyperplane arrangement.

A generic integral that calculates the probability that $\pi \in S_{n+1}$ occurs is $\int_{\mathbb{R}_{>0}^n} g(L_\pi(\mathbf{x})) \mathrm{d} \mathbf{x}$, where $g$ is the joint density function for the steps. The preprint Ordinal pattern probabilities for symmetric random walks uses this to compute or compare probabilities for various density functions. In particular, an answer is given to the question about steps drawn from the uniform distribution on $[-1,1]$. For that choice of density, the probability that $\pi \in S_{n+1}$ occurs is $\frac{K_\pi}{2^n n!}$, where $K_\pi$ is the size of a weak order interval in the affine Weyl group. A complicated elementary description of $K_\pi$ is that it counts the number of strictly upper triangular matrices $M$ such that $M_{i,j} = 0$ whenever there exists $k$ such that $\pi(k) \leq i < j \leq \pi(k+1)$ or $\pi(k+1) \leq i < j \leq \pi(k)$ subject to the constraint, due to Shi, that $M_{it} + M_{tj} \leq M_{ij} \leq M_{it} + M_{tj} + 1$ whenever $i < t < j$. Code that calculates this distribution is given here.

This provides a description of the extremes: The identity and its reverse occur with probability $\frac{1}{2^n}$, while any permutation where $1$ and $n+1$ are consecutive occurs with probability $\frac{1}{2^n n!}$. A permutation where $|\pi(i) - \pi(i+1)| = m$ for some $i$ is guaranteed to have probability less than or equal to $\frac{1}{2^n m!}$.

For the mean zero Gaussian, we can compare permutations by looking at the matrix $\mathrm{lev}(\pi)$ whose $ij$-th entry counts the number of positions $k$ such that $\pi(k) \leq i,j < \pi(k+1)$ or $\pi(k+1) \leq i,j < \pi(k)$. If $\mathrm{lev}(\pi)_{ij} \leq \mathrm{lev}(\tau)_{ij}$ for all $i,j$, then $\pi$ occurs more frequently than $\tau$. (This is a somewhat precise version of the heuristic this answer opened with.) For exact probabilities, there is a decent answer when $\pi$ is a permutation such that $|\pi^{-1}(i+1) - \pi^{-1}(i)| \leq 2$, which applies to any symmetric density function. For such permutations, the probability is given by $$\frac{1}{2^n \prod_{j=1}^n \mathrm{lev}(\pi)_j},$$ where $\mathrm{lev}(\pi)_j$ is the number of positions $k$ such that $\pi(k) \leq j < \pi(k+1)$ or $\pi(k+1) \leq j < \pi(k)$. This expression applies to every $\pi \in S_{n+1}$ when the steps are drawn from a mean zero double-exponential distribution.