# Equal-slices distribution for DHJ(k)

For $k \in {\mathbb N}$, define $\nu_k$ to be the uniform distribution on the $k$-simplex $\{(p_1, \dots, p_k) : p_i \geq 0\ \forall i, \sum \pi_i = 1\}$. It will be useful to think of $\nu_k$ as first drawing $k$ i.i.d. $\mathrm{Exponential}(1)$ rv's $Y_1, \dots, Y_k$, and then setting $p_j = Y_j/(\sum Y_i)$.

1. The fact that $\nu_k$ can be thought of this way is because the density function of $(Y_1, \dots, Y_k)$ is $\exp(-y_1)\cdots\exp(-y_k) = \exp(-(y_1 + \cdots + y_k))$, which only depends on $s = y_1 + \cdots + y_k$; i.e., it's constant on each simplex $Y_1 + \cdots + Y_k = s$.

2. One can also think of the $Y_j$'s as interarrival times in a Poisson Process. By a well-known fact about the location of events in a Poisson Process, it follows that $\nu_k$ is also equivalent to picking $k-1$ independent uniformly random points in $[0,1]$ and then letting $p_j$ be the length of the $j$th segment formed.

3. If we draw $(p_1, \dots, p_k)$ from $\nu_k$, and then draw a string in $[k]^n$ according to the product distribution defined by $(p_1, \dots, p_k)$, then we get an "equal-slices" draw from $[k]^n$. (You can take this as the definition of "equal-slices" if you like.)

4. Given that we're going to be doing this, it's not really essential to divide all of the $Y_i$'s by their sum. We can be more relaxed and just say that $\nu_k$ determines $(Y_1, \dots, Y_k)$, and then we make a draw from $[k]^n$ according to the product distribution in which $j \in [k]$ is chosen with probability proportional to $Y_j$.

5. Summarizing, we can draw from equal-slices on $[k]^n$ as follows: pick $(Y_1, \dots, Y_k)$ as i.i.d. $\mathrm{Exponential}(1)$'s; then draw from the product distribution "proportional to $(Y_1, \dots, Y_k)$".

Goal: To define a distribution on combinatorial lines $(x^1, \dots, x^k, z) \in [k+1]^n$ in such a way that: (i) $z$ is distributed according to equal-slices on $[k+1]^n$; (ii) each $x^j$ is distributed according to equal-slices on $[k]^n$. Please note that $x^j$ will not necessarily be the point in the line where the wildcards are $j$'s.

Let us record an easy-to-see fact:

Proposition 1 Suppose we first draw a string in $[k+1]^n$ from the product distribution $\mu$ proportional to $(y_1, \dots, y_{k+1})$, and then we change all the $(k+1)$'s in the string to $j$'s, where $j \in [k]$. Then the resulting string is distributed according to the product distribution $\mu_j$ on $[k]^n$ proportional to $(y_1, \dots, y_{j-1}, y_j + y_{k+1}, y_{j+1}, \dots, y_k)$.

The following proposition achieves the essence of the goal:

Proposition 2 Suppose $\lambda$ is a distribution on the $k$-simplex defined as follows. First we draw i.i.d. Exponentials $(Y_1, \dots, Y_{k+1})$ as in $\nu_{k+1}$. Then we set $W^{(j)} = (Y_1, \dots, Y_{j-1}, Y_j + Y_{k+1}, Y_{j+1}, \dots, Y_k)$ (as in Proposition 1). Next, we choose $J \in [k]$ uniformly at random. Following this, we define $\vec{W} = W^{(J)}$. Finally, we scale $\vec{W}$ so as to get a point $(p_1, \dots, p_k)$ on the $k$-simplex.
Then $\lambda$ is identical to $\nu_k$ (even though the components of $\vec{W}$ are not i.i.d. Exponentials).
Proof: It suffices to check that density function $f(w_1, \dots, w_k)$ of the vector $\vec{W}$ depends only on $w_1 + \cdots + w_k$. Now $\vec{W}$ has a mixture distribution, a uniform mixture of the $W^{(j)}$ distributions. The density of $W^{(j)}$ at $(w_1, \dots, w_k)$ is

$\displaystyle \exp(-w_1)\cdots\exp(-w_{j-1}) \cdot \left(w_j \exp(-w_j)\right) \cdot \exp(-w_{j+1}) \cdots \exp(-w_k) \qquad$

$\displaystyle \qquad = w_j \exp(-(w_1 + \cdots + w_k)).$

This is because the density of a sum of two independent $\mathrm{Exponential}(1)$'s is $t\exp(-t)$. Hence the density of $\vec{W}$ at $(w_1, \dots, w_k)$ is

$\displaystyle \frac{w_1 + \cdots + w_k}{k} \exp(-(w_1 + \cdots + w_k)),$

which indeed depends only on $w_1 + \cdots + w_k$. $\Box$

We can now achieve the goal by combining the previous two propositions:

Achieving the Goal: Draw $z \in [k+1]^n$ according to equal-slices on $[k+1]^n$. Next, let $v^j \in [k]^n$ be the string formed by changing all the $(k+1)$'s in $z$ to $j$'s. Finally, pick a random permutation $\pi$ on $[k]$ and define $x^{i} = v^{\pi(i)}$.

Proof: We can think of $z$ as being drawn from the product distribution proportional to $(Y_1, \dots, Y_{k+1})$, where $(Y_1, \dots, Y_{k+1})$ is drawn as in $\nu_k$. The strings $(v^1, \dots, v^k, z)$ form a combinatorial line ("in order"), so clearly $(x^1, \dots, x^k, z)$ form a combinatorial line (possibly "out of order"). We have that $v^j$ is distributed according to the product distribution proportional to $W^{(j)}$. Thus $x^i$ is distributed according to a product distribution which itself is distributed as $\lambda = \nu_k$. Hence $x^i$ is equal-slices-distributed on $[k]^n$. $\Box$