Equal-slices.tex

\section{Equal-slice distributions}

\subsection{Equal-nondegenerate-slices}

\begin{definition} Given a vector $C \in \N^k$ whose components sum to $n$, the associated \emph{slice} of $[k]^{n}$ is the set \[ \{x \in [k]^{n} : x \text{ has $C_1$ many $1$'s, $C_2$ many $2$'s, \dots, $C_k$ many $k$'s}\}. \] We abuse terminology by also referring to $C$ as the slice. A slice is \emph{nondegenerate} when $C_i \neq 0$ for all $i$. There are $\binom{n+k-1}{k-1}$ different slices, of which $\binom{n-1}{k-1}$ are nondegenerate.\noteryan{Justify? Justify later?} \end{definition}

\begin{definition} Let $2 \leq k \leq n$. The \emph{equal-nondegenerate-slices} distribution on $[k]^n$, denoted $\ens{k}^n$, generates a string $x$ as follows: First, points $q_1, \dots, q_n$ are arranged on a circle according to a uniformly random permutation. This also forms $n$ ``gaps between the $q_i$'s. Second, $k$ gaps are chosen, uniformly from the $\binom{n}{k}$ possibilities; points $r_1, \dots, r_k$ are put into the chosen gaps, in random order. \ignore{Second, $k$ points $r_1, \dots, r_k$ are placed one by one into the gaps, each going into a random unoccupied gap.} This divides the $q_i$'s into ``arcs, with the ``$r_j$ arc consists of those $q_i$'s whose nearest $r$-point counterclockwise is $r_j$. Finally, $x$ is defined by setting $x_i = j$ for all $i$ such that $q_i$ in the $r_j$ arc.\noteryan{Diagram would help.} \end{definition} \begin{remark} More generally, when $|J| \geq k$ we write $\ens{k}^J$ for the analogous distribution on $[k]^{J}$, and we write simply $\ens{k}$ when $n$ or $J$ is clear from context. \end{remark} \begin{remark} If $x \sim \ens{k}^n$ then $x$ always belongs to a nondegenerate slice. \end{remark} \begin{remark} It is not hard to see\noteryan{Honest, although we can clarify} that drawing $x \sim \ens{k}^n$ is equivalent to first choosing a nondegenerate slice $C$ uniformly from the $\binom{n-1}{k-1}$ possibilities, then choosing $x$ uniformly from this slice. \end{remark}

\begin{definition} Let $x \in [m]^n$, $y \in [k]^m$. We write $y \circ x$ for the string in $[k]^n$ given by replacing in $x$ the symbol $j$ by the symbol $y_j$, for all $j \in [m]$.\noteryan{This really is function composition, if one thinks of a string in $\Omega^J$ as a map $J \to \Omega$.} \end{definition}

The following lemma will be important: \begin{lemma} \label{lem:last-pt} Let $x \sim \ens{k+1}^n$, and let $j \sim [k]$ be uniformly random. Then $\chg{x}{(k+1)}{j}$ is distributed as~$\ens{k}^n$. \end{lemma} \begin{proof} Suppose we are drawing $x \sim \ens{k+1}^n$ and have chosen the arrangement of $q_1, \dots, q_n$ and also the $k+1$ gaps to be filled with $r$-points. To fill these gaps, we may do the following. First, choose one of the $k+1$ gaps at random to contain $r_{k+1}$. Next, take the first gap counterclockwise from $r_{k+1}$ and let it contain $r_j$, where $j \sim [k]$ is uniformly chosen. Finally, fill the remaining $k-1$ gaps according to a uniform ordering of $[k] \setminus \{j\}$. But having chosen $x$ in this way, $\chg{x}{(k+1)}{j}$ is obtained simply by ``deleting $r_{k+1}$ and interpreting the result as a (correctly distributed) draw from $\ens{k}^n$.\noteryan{not put very eloquently} \end{proof}

The next lemma is also handy: \noteryan{And is \emph{not} true of equal-slices.} \begin{lemma} \label{lem:ens-compose} Let $x \sim \ens{m}^n$ and let $y \sim \ens{k}^m$. Then $y \circ x \in [k]^n$ is distributed as $\ens{k}^n$. \end{lemma} \begin{proof} The effect of forming $y \circ x$ can be thought of as follows: First the points $q_1, \dots, q_n$ and $r_1, \dots, r_m$ are randomly arranged as usual to form $x$. Next, we think of the \emph{arcs} of $q_i$'s as being the $m$ objects circularly permuted in the initial stage of drawing $y$; we then choose $k$ out of the $m$ gaps between the arcs at random and place points $s_1, \dots, s_k$ into them in a random order. Then $z = y \circ x$ is given by setting $z_i = j$ for all $i$ such that $q_i$ is in the $s_j$ ``super-arc.

On the other hand, since $\ens{m}^n$ is symmetric under permutations of $[m]$, the middle stage in this composite process, permuting the $r_j$ arcs, is superfluous. Eliminating it, we see that the $s_j$'s are ultimately placed by first choosing $m$ out of $n$ gaps at random, and then further choosing $k$ out of these $m$ choices at random. This is equivalent to simply choosing $k$ out of the $n$ gaps at random; hence $z$ is indeed distributed as $\ens{k}^n$.\noteryan{Again, not put very eloquently} \end{proof}

\subsection{Equal-slices} We will also use the following slight variant on the equal-nondegenerate-slices distribution: \begin{definition} Let $k \geq 2$ and let $n$ be a positive integer. The \emph{equal-slices} distribution on $[k]^n$, denoted $\eqs{k}^n$, generates a string $x$ in a manner similar to that of equal-nondegenerate-slices. The only distinction is that the points $r_1, \dots, r_k$ are placed into random gaps one-by-one, and once a point $r_j$ is placed, it is considered to split the gap into two occupiable gaps. Thus when placing $r_j$, there are $n+j-1$ gaps to choose from. As a consequence, some of the resulting $r_j$ arcs may be empty of $q$-points. \end{definition} \begin{remark} \label{rem:eqs-equiv} It is again not hard to see\noteryan{Really, it isn't.} that drawing $x \sim \eqs{k}^n$ is equivalent to first choosing a slice $C$ uniformly from the $\binom{n+k-1}{k-1}$ possibilities (nondegenerate and degenerate), then choosing $x$ uniformly from this slice. Alternately, if $x$ is in slice $C$, the probability of drawing $x$ is precisely \begin{equation} \label{eqn:eqs-equiv} 1 \Bigm/ \binom{n+k-1}{k-1, C_1, \dots, C_k}. \end{equation} \end{remark}

The two distributions $\ens{k}^n$ and $\eqs{k}^n$ are very close: \begin{proposition} \label{prop:degen} For $2 \leq k \leq n$ we have $\dtv{\ens{k}^n}{\eqs{k}^n} \leq k(k-1)/n$. \end{proposition} \begin{proof} The distribution $\ens{k}^n$ is precisely $\eqs{k}^n$ conditioned on no $q_j$'s ending up adjacent; hence it suffices to show this event occurs with probability at most $k(k-1)/n$. In a draw from $\eqs{k}^n$, the probability that $q_j$ is placed adjacent to one of $q_1, \dots, q_{j-1}$ is exactly $2(j-1)/(n+j-1) \leq 2(j-1)/n$. Hence the probability of having any adjacent $q_j$'s is at most $\sum_{j=1}^k 2(j-1)/n = k(k-1)/n$, as desired. \end{proof}

It will also be quite useful to observe that equal-slices is a \emph{mixture of product distributions}. \begin{definition} \label{def:spacings} We say that $\nu$ is a (randomly chosen) \emph{uniform spacing distribution} on $[k]$ if the vector of probabilities $(\nu[1], \dots, \nu[k])$ is formed as follows: $k$ points $r_1, \dots, r_k$ are chosen independently from the (continuous) uniform distribution on the circle of unit circumference, dividing the circle into $k$ arcs; then $\nu[i]$ is set to the length of the arc emanating clockwise from $r_i$. \end{definition} \begin{remark} It is well known (see, e.g.~\cite[Ch.\ 1]{Rei89})\noteryan{I think the traditional citation here is Pyke '65, but we can save a spot in the biblio by citing Reiss again (which is also a text, whereas Pyke is a bit painful to read)} that a uniform spacing distribution $\nu$ can equivalently be defined as choosing the vector of probabilities $(\nu[1], \dots, \nu[k])$ uniformly from the simplex $\{(p_1, \dots, p_k) : \sum p_i = 1, p_i \geq 0\ \forall i\}$. \noteryan{Or, by taking the spacings of $k-1$ random points in a unit segment. Since we don't use this fact, I think it's fair to not prove it.} \end{remark} \begin{proposition} \label{prop:eqs-mix} The equal-slices distribution $\eqs{k}^n$ can equivalently be defined as follows: First, draw a uniform spacing distribution $\nu$ on $[k]$; then, draw a string from the product distribution $\nu^{\otimes n}$ on $[k]^{n}$. \end{proposition} \begin{proof} In the usual definition of a draw $x \sim \eqs{k}^n$, the string $x$ only depends on the joint ordering of the $n+k$ points $q_i$ and $r_j$ around the circle. Further, it's easy to see that this ordering is just a uniform (circular) permutation of $n+k$ objects. Hence we can also obtain it by choosing all $n+k$ points independently from the continuous uniform distribution on the circle of unit circumference.\noteryan{Not worth pointing out that we're disregarding some probability-$0$ events here.} Further, in this continuous distribution, we may choose the $r_j$'s first, and then the $q_i$'s next, one-by-one. The choice of $r_j$'s gives a uniform spacing distribution $\nu$, and then the formation of $x$ by choice of $q_i$'s is indeed equivalent to drawing $x$ from the product distribution $\nu^{\otimes n}$.\noteryan{Not very eloquently put.} \end{proof}

We will occasionally need the following bounds: \begin{proposition} \label{prop:rand-min} If $\nu$ is a uniform spacing distribution on $[k]$ as in Definition~\ref{def:spacings}, then \[ \Pr[\min(\nu) \leq \gamma] \leq k(k-1) \gamma. \] \end{proposition} \begin{proof} By a union bound and symmetry, $\Pr[\min(\nu) \leq \gamma] \leq k \Pr[\nu[1] \leq \gamma]$. The event $\nu[1] \leq \gamma$ occurs only if one of $r_2, \dots, r_k$ falls within the arc of length $\gamma$ clockwise of $r_1$. By another union bound, this has probability at most $(k-1)\gamma$. \end{proof} \begin{proposition} \label{prop:min-eqs} Assume $2k^2 \leq n$. Then $\min(\eqs{k}^n) \geq k^{-2n}$. \noteryan{Can actually get something like $k^kn^{-k/2}k^{-n}$ here, but probably best just to get the typographically shortest thing here.} \end{proposition} \begin{proof} We need to lower-bound the expression~\eqref{eqn:eqs-equiv} appearing in Remark~\ref{rem:eqs-equiv}. We can get a simple lower bound as follows: set $\alpha = k(k-1)/n$ and apply the multinomial theorem --- \[ (\alpha + 1 + \cdots + 1)^{n+k-1} = \sum_{t_0 + t_1 + \cdots t_k = n+k-1} \binom{n+k-1}{t_0, t_1, \dots, t_k} \alpha^{t_0} \geq \binom{n+k-1}{k-1, C_1, \dots, C_k} \alpha^{k-1}. \] Hence we can lower-bound the expression~\eqref{eqn:eqs-equiv} by \[ \frac{\alpha^{k-1}}{(\alpha + k)^{n+k-1}} = \frac{(k-1)^{k-1}}{(1 + \frac{k-1}{n})^{n+k-1} n^{k-1} k^n} \geq \frac{(k-1)^{k-1}}{\exp(k-1 + \frac{(k-1)^2}{n}) n^{k-1} k^n} \geq \frac{(k-1)^{k-1}}{\exp(k) n^{k-1} k^{n}}, \] where the first step used the definition of $\alpha$, the second used $1+x \leq \exp(x)$, and the last used $(k-1)^2/n \leq 1/2 \leq 1$, by assumption. \noteryan{Here's where we waste a lot of factors.} Now it's not hard to check\noteryan{Honest.} that when $k \geq 2$ and $n \geq 2k^2$, the above quantity is at least $k^{-2n}$. \end{proof}