View source for Equal-slices distribution for DHJ(k)

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

Some comments:

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

2. One can also think of the <math>Y_j</math>'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 <math>\nu_k</math> is also equivalent to picking <math>k-1</math> independent uniformly random points in <math>[0,1]</math> and then letting <math>p_j</math> be the length of the <math>j</math>th segment formed. 

3. If we draw <math>(p_1, \dots, p_k)</math> from <math>\nu_k</math>, and then draw a string in <math>[k]^n</math> according to the product distribution defined by <math>(p_1, \dots, p_k)</math>, then we get an "equal-slices" draw from <math>[k]^n</math>. (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 <math>Y_i</math>'s by their sum. We can be more relaxed and just say that <math>\nu_k</math> determines <math>(Y_1, \dots, Y_k)</math>, and then we make a draw from <math>[k]^n</math> according to the product distribution in which <math>j \in [k]</math> is chosen with probability <em>proportional to</em> <math>Y_j</math>.

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


The point of this article is the following:


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


Let us record an easy-to-see fact: 
<blockquote><b>Proposition 1</b> <em> Suppose we first draw a string in <math>[k+1]^n</math> from the product distribution <math>\mu</math> proportional to <math>(y_1, \dots, y_{k+1})</math>, and then we change all the <math>(k+1)</math>'s in the string to <math>j</math>'s, where <math>j \in [k]</math>. Then the resulting string is distributed according to the product distribution <math>\mu_j</math> on <math>[k]^n</math> proportional to <math>(y_1, \dots, y_{j-1}, y_j + y_{k+1}, y_{j+1}, \dots, y_k)</math>. </em></blockquote>


The following proposition achieves the essence of the goal: 
<blockquote><b>Proposition 2</b> <em> Suppose <math>\lambda</math> is a distribution on the <math>k</math>-simplex defined as follows. First we draw i.i.d. Exponentials <math>(Y_1, \dots, Y_{k+1})</math> as in <math>\nu_{k+1}</math>. Then we set <math>W^{(j)} = (Y_1, \dots, Y_{j-1}, Y_j + Y_{k+1}, Y_{j+1}, \dots, Y_k)</math> (as in Proposition 1). Next, we choose <math>J \in [k]</math> uniformly at random. Following this, we define <math>\vec{W} = W^{(J)}</math>. Finally, we scale <math>\vec{W}</math> so as to get a point <math>(p_1, \dots, p_k)</math> on the <math>k</math>-simplex. <br>

Then <math>\lambda</math> is identical to <math>\nu_k</math> (even though the components of <math>\vec{W}</math> are <b>not</b> i.i.d. Exponentials). </em></blockquote>

<em>Proof:</em>  It suffices to check that density function <math>f(w_1, \dots, w_k)</math> of the vector <math>\vec{W}</math> depends only on <math>w_1 + \cdots + w_k</math>. Now <math>\vec{W}</math> has a mixture distribution, a uniform mixture of the <math>W^{(j)}</math> distributions. The density of <math>W^{(j)}</math> at <math>(w_1, \dots, w_k)</math> is <p align=center><math>\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 </math></p>
 <p align=center><math>\displaystyle  \qquad = w_j \exp(-(w_1 + \cdots + w_k)). </math></p>
 This is because the density of a sum of two independent <math>\mathrm{Exponential}(1)</math>'s is <math>t\exp(-t)</math>. Hence the density of <math>\vec{W}</math> at <math>(w_1, \dots, w_k)</math> is <p align=center><math>\displaystyle  \frac{w_1 + \cdots + w_k}{k} \exp(-(w_1 + \cdots + w_k)), </math></p>
which indeed depends only on <math>w_1 + \cdots + w_k</math>. <math>\Box</math>


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

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

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