Equal-slices.tex

\section{Equal-slice distributions} \label{sec:eqs}

In this section we describe the equal-slices distribution $\eqs{k}^n$ and the equal-nondegenerate-slices distribution $\ens{k}^n$. It will actually be more convenient to begin with the latter. Before proceeding, we briefly introduce some notation.

\begin{definition} Given a distribution $\pi$ on $\Omega$, we write $\min(\pi) = \min_{x \in \Omega} \pi[x]$. \end{definition}

A final important concept is the \emph{distance} between two probability measures: \begin{definition} For $\distra$ and $\distrb$ probability distributions on $\Omega^n$, the \emph{total variation distance} $\dtv{\distra}{\distrb}$ is defined by \[ \dtv{\distra}{\distrb} = \frac12 \sum_{x \in \Omega^n} \abs{\distra[x] - \distrb[x]} = \max_{A \subseteq \Omega^n} \abs{\distra(A) - \distrb(A)}. \] If $\dtv{\distra}{\distrb} \leq \tau$ we say that $\distra$ and $\distrb$ are \emph{$\tau$-close}. \end{definition}

\subsection{Equal-nondegenerate-slices}

\begin{definition} Given a vector $\slice \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 $\slice_1$ many $1$'s, $\slice_2$ many $2$'s, \dots, $\slice_k$ many $k$'s}\}. \] We abuse terminology by also referring to $\slice$ as the slice. A slice is \emph{nondegenerate} when $\slice_a \neq 0$ for all $a \in [k]$. 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_a$ arc consists of those $q_i$'s whose nearest $r$-point counterclockwise is $r_a$. Finally, $x$ is defined by setting $x_i = a$ for all $i$ such that $q_i$ in the $r_a$ arc. See Figure~\ref{fig:ens} for an example. \end{definition}

\begin{figure}[htb] \begin{center} \includegraphics[height=7.5cm]{ens-figure.png} \caption{An example of the two stages in drawing from $\ens{3}^{10}$. The resulting string is $1131232213$.} \label{fig:ens} \end{center} \end{figure}

\begin{remark} The distribution is symmetric with respect to the $k$ symbols in $[k]$, and thus we may naturally extend it to any alphabet $\Omega$ with $\abs{\Omega} = k$. \end{remark}

\ignore{\begin{remark} More generally, when $\abs{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 $\slice$ uniformly from the $\binom{n-1}{k-1}$ possibilities, then choosing $x$ uniformly from this slice. \end{remark}

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

We end our discussion of the equal-nondegenerate-slices distribution with a handy lemma (which is not true of the equal-slices distribution). First, one more piece of notation: \begin{definition} Let $x \in [m]^n$, $y \in [k]^m$. We write $y \circ x$ for the string $\chg{x}{(1, \dotsc, m)}{(y_1, \dotsc, y_m)} \in [k]^n$. For example, if $n = 6$, $m = 4$, $k = 3$, $x = 4124332$, $y = 3132$, then $y \circ x = 2312331$. This operation is indeed function composition if one thinks of a string in $\Omega^n$ as a map $[n] \to \Omega$. \end{definition} \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.

But 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 now define the closely related variant, the equal-slices distribution: \begin{definition} \label{def:eqs} 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_a$ is placed, it is considered to split the gap into two occupiable gaps. Thus when placing $r_a$, there are $n+a-1$ gaps to choose from. As a consequence, some of the resulting $r$-arcs may be empty of $q$-points. \end{definition}

\begin{remark} It is not hard to see\noteryan{honest} that the process in Definition~\ref{def:eqs} yields a uniformly random (circular) ordering of the $n+k$ points. In particular, the definition of $\eqs{k}^n$ is symmetric with respect ot the symbols $[k]$. \end{remark}

Let's first show that 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 $r_a$'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 $r_a$ is placed adjacent to one of $r_1, \dots, r_{a-1}$ is at most $2(a-1)/(n+a-1) \leq 2(a-1)/n$. Hence the probability of having any adjacent $r_a$'s is at most $\sum_{a=1}^k 2(a-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} Given $k$ points $r_1, \dotsc, r_k$ on the the circle of unit circumference, dividing it into arcs, the associated \emph{spacing} is the $k$-dimensional vector $\spac$ defined by setting $\spac[a]$ to be the length of the arc emanating clockwise from $r_a$. We identify a spacing $\spac$ with a probability distribution on $[k]$ in the natural way. We say that $\spac$ is a \emph{(uniformly) random spacing} if it is derived by choosing the points $r_1, \dotsc, r_k$ independently and uniformly at random on the circle. \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 random spacing $\spac$ can equivalently be defined as choosing the vector of probabilities $(\spac[1], \dots, \spac[k])$ uniformly from the simplex $\{(p_1, \dots, p_k) : \sum p_a = 1, p_a \geq 0\ \forall a \in [k]\}$. \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 random spacing $\spac$ on $[k]$; then, draw a string from the product distribution $\spac^{\otimes n}$ on $[k]^{n}$. \end{proposition} \begin{proof} In the original 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_a$ around the circle. As we earlier remarked, 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_a$'s first, and then the $q_i$'s next, one-by-one. The choice of $r_a$'s gives a random spacing $\spac$, and then the formation of $x$ by choice of $q_i$'s is indeed equivalent to drawing $x$ from the product distribution $\spac^{\otimes n}$.\noteryan{Not very eloquently put.} \end{proof}

\begin{remark} \label{rem:eqs-equiv} \noteryan{proofs not necessary?} Drawing $x \sim \eqs{k}^n$ is equivalent to first choosing a slice $\slice$ uniformly from the $\binom{n+k-1}{k-1}$ possibilities (nondegenerate and degenerate), then choosing $x$ uniformly from this slice. Hence $\ens{k}^n$ is precisely $\eqs{k}^n$ conditioned on the string being nondegenerate. Equivalently, for each $x$ in slice $\slice$ we have \begin{equation} \label{eqn:eqs-equiv} \eqs{k}^n[x] = 1 \Bigm/ \binom{n+k-1}{k-1, \slice_1, \dots, \slice_k}. \end{equation} \end{remark}

Finally, we will occasionally need the following technical bounds: \begin{proposition} \label{prop:rand-min} If $\spac$ is a random spacing on $[k]$ as in Definition~\ref{def:spacings}, then \[ \Pr[\min(\spac) \leq \theta] \leq k(k-1) \theta. \] \end{proposition} \begin{proof} By a union bound and symmetry, $\Pr[\min(\spac) \leq \theta] \leq k \Pr[\spac[1] \leq \theta]$. The event $\spac[1] \leq \theta$ occurs only if one of $r_2, \dots, r_k$ falls within the arc of length $\theta$ clockwise of $r_1$. By another union bound, this has probability at most $(k-1)\theta$. \end{proof} \begin{proposition} \label{prop:min-eqs} Assume $2k^2 \leq n$. Then we may crudely bound $\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} Define $\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, \slice_1, \dots, \slice_k} \alpha^{k-1}. \] Hence we can lower-bound the expression~\eqref{eqn:eqs-equiv} appearing in Remark~\ref{rem: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}