Measures.tex - Revision history

Ryanworldwide at 20:25, 8 July 2009

2009-07-08T20:25:55Z

Show changes

Ryanworldwide: Undo revision 1768 by 67.186.58.92 (Talk)

2009-07-08T20:13:29Z

Undo revision 1768 by 67.186.58.92 (Talk)

Show changes

67.186.58.92 at 04:22, 25 June 2009

2009-06-25T04:22:06Z

Show changes

Ryanworldwide at 01:21, 19 May 2009

2009-05-19T01:21:11Z

Show changes

Ryanworldwide at 13:59, 18 May 2009

2009-05-18T13:59:39Z

← Older revision		Revision as of 06:59, 18 May 2009
Line 2:		Line 2:

	\noteryan{As mentioned at the end, I think this section would be better if the master lemma at the end came first}		\noteryan{As mentioned at the end, I think this section would be better if the master lemma at the end came first}


			\noteryan{The following needs to be put into its proper place}
			We will also need the following simple 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 $q_2, \dots, q_k$ falls within the arc of length $\gamma$ clockwise of $q_1$. By another union bound, this has probability at most $(k-1)\gamma$.
			\end{proof}

Ryanworldwide at 13:44, 18 May 2009

2009-05-18T13:44:17Z

@@ Line 1: / Line 1: @@
-\section{Probability measures}
+\section{Passing between probability measures}
@@ Line 58: / Line 8: @@
 We begin by recording some simple facts about distances between probability distributions.  Throughout this subsection we assume $\pi$ and $\nu$ are probability distributions on the same finite set $\Omega$.\noteryan{Perhaps change $\Omega$ to $[k]$ throughout.}
 \begin{fact}  \label{fact:tv-mix} Let $(\nu_\kappa)_{\kappa \in K}$ be a family of distributions on $\Omega$, let $\lambda$ be a distribution on $K$, and let $\mu$ be the associated mixture distribution, given by drawing $\kappa \sim \lambda$ and then drawing from $\nu_\kappa$.  Then\noteryan{need to prove? It's just the triangle inequality}
 \[
@@ Line 183: / Line 125: @@
 \end{lemma}
 \begin{proof}
-We apply Propositions~\ref{prop:prod-eqs}, \ref{prop:eqs-prod}, and \ref{prop:eqs-eqs} with $\eps = 2r/n$, but condition on $r \leq |J| \leq 4r$.  This increases the total variation distance by at most $2\gamma$, where $\gamma$ is the probability that $r \leq |J| \leq 4r$ fails.  By Fact~\ref{fact:dev}, the increase is at most $4\exp(-r/4)$, which is at most $2 r / \sqrt{n}$ using the lower bound $r \geq 2 \ln n$.  The claimed bounds now follow.\noteryan{This is explained messily.}
+We apply Propositions~\ref{prop:prod-eqs}, \ref{prop:eqs-prod}, and \ref{prop:eqs-eqs} with $\eps = 2r/n$, but condition on $r \leq |J| \leq 4r$.  This increases the total variation distance by at most $2\gamma$, where $\gamma$ is the probability that $r \leq |J| \leq 4r$ fails. \textbf{ACTUALLY, JUST BY $\gamma$.} By Fact~\ref{fact:dev}, the increase is at most $4\exp(-r/4)$, which is at most $2 r / \sqrt{n}$ using the lower bound $r \geq 2 \ln n$.  The claimed bounds now follow.\noteryan{This is explained messily.}
 \end{proof}

Ryanworldwide at 18:50, 17 May 2009

2009-05-17T18:50:51Z

← Older revision		Revision as of 11:50, 17 May 2009
Line 27:		Line 27:
	\end{definition}		\end{definition}

	The terminology ``equal-slices'' comes from the following:\noteryan{So far we don't actually need the observations that follow}		The terminology ``equal-slices'' comes from the following:\noteryan{So far we don't actually need the observations that follow --- updated: or do we? See Prop~\ref{prop:degen} below}
	\begin{definition} Given a vector $C \in \N^k$ whose components sum to $n$, the associated \emph{slice} of $[k]^{n}$ is the set		\begin{definition} Given a vector $C \in \N^k$ whose components sum to $n$, the associated \emph{slice} of $[k]^{n}$ is the set
	\[		\[
Line 34:		Line 34:
	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 with bars and dots?}		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 with bars and dots?}
	\end{definition}		\end{definition}
	\begin{proposition} The equal-slices distribution $\eqs{k}^{n}$ is equivalent to first choosing a slice uniformly from the $\binom{n+k-1}{k-1}$ many possibilities, then drawing a string uniformly from that slice. \noteryan{Include proof? If so, it's by throwing $n+k-1$ points into the interval and looking at the result in two ways.}		\begin{proposition} \label{prop:eqs-equiv} The equal-slices distribution $\eqs{k}^{n}$ is equivalent to first choosing a slice uniformly from the $\binom{n+k-1}{k-1}$ many possibilities, then drawing a string uniformly from that slice. \noteryan{Include proof? If so, it's by throwing $n+k-1$ points into the interval and looking at the result in two ways.}
	\end{proposition}		\end{proposition}

	The following observation will be crucial:		The following observation will be crucial:
	\begin{lemma} Let $x \sim \eqs{k}^n$, and let $a \sim [k-1]$ be uniformly random. Then $\chg{x}{k}{a}$ is distributed as~$\eqs{k-1}^n$.		\begin{lemma} Let $x \sim \eqs{k}^n$, and let $i \sim [k-1]$ be uniformly random. Then $\chg{x}{k}{i}$ is distributed as~$\eqs{k-1}^n$.
	\end{lemma}		\end{lemma}
	\begin{proof}		\begin{proof}
	From the definition, the string $\chg{x}{k}{a}$ is distributed as follows: first $\nu$ is taken to be a random distribution on $[k]$; then $\wt{\nu}$ is taken to be the distribution on $[k-1]$ with $\wt{\nu}[b] = \nu[b]$ for $b \neq a$ and $\wt{\nu}[a] = \nu[a] + \nu[k]$; then a string is drawn from the product distribution $\wt{\nu}^{\otimes n}$. Thus it suffices to show that $\wt{\nu}$ is a random distribution on $[k-1]$ in the sense of Definition~\ref{def:spacings}. This is easy to see: having chosen $k$ points on the circle, thus forming $\nu$, we get the correct distribution $\wt{\nu}$ simply by removing the $k$th point. \noteryan{This is not especially well-explained; will try to think how to say it with the maximum combination of concision and correctness.}		From the definition, the string $\chg{x}{k}{a}$ is distributed as follows: first $\nu$ is taken to be a random distribution on $[k]$; then $\wt{\nu}$ is taken to be the distribution on $[k-1]$ with $\wt{\nu}[j] = \nu[j]$ for $j \neq i$ and $\wt{\nu}[i] = \nu[i] + \nu[k]$; then a string is drawn from the product distribution $\wt{\nu}^{\otimes n}$. Thus it suffices to show that $\wt{\nu}$ is a random distribution on $[k-1]$ in the sense of Definition~\ref{def:spacings}. This is easy to see: having chosen $k$ points on the circle, thus forming $\nu$, we get the correct distribution $\wt{\nu}$ simply by removing the $k$th point. \noteryan{This is not especially well-explained; will try to think how to say it with the maximum combination of concision and correctness.}
	\end{proof}		\end{proof}

			We will also need the following simple bound:
			\begin{proposition} \label{prop:degen} Let $x \sim \eqs{k}^n$. The probability $x$ is in a degenerate slice is at most $k(k-1)/n$.
			\end{proposition}
			\begin{proof} We can view a draw $x \sim \eqs{k}^n$ as follows: Pick $q_1, \dots, q_k$ on the unit circle as in Definition~\ref{def:spacings} to define the random distribution $\nu$. Next, pick $n$ more points $r_1, \dots, r_n$ independently and uniformly on the circle, and define $x_j$ to be $i$ iff $r_j$ is in the arc emanating clockwise from $q_i$.\noteryan{Not worth it to point out that there are certain $0$-probability events involved here\dots}. The string $x$ is degenerate iff after the $n+k$ points are drawn there are two $q_i$ points appearing ``consecutively'' on the circle.

			Given the locations but not the labels of the $n+k$ points ultimately drawn, the identity of the $q_i$'s is uniformly random from the $(n+k)(n+k-1) \cdots (n+1)$ possibilities. By symmetry, the probability that two $q_i$'s appear consecutively is, by a union bound, at most $\binom{k}{2}$ times the probability that $q_1$ and $q_2$ appear consecutively. We can imagine that $q_1$ is chosen first and $q_2$ second; then the probability they appear consecutively is precisely $2/(n+k-1)$. Hence the probability that $x$ is degenerate is at most $\binom{k}{2} \cdot 2/(n+k-1) \geq k(k-1)/n$. \noteryan{Again, I'd prefer if this proof was a little more elegantly phrased.}
			\end{proof}


Line 164:		Line 171:
	\end{fact}		\end{fact}

	We can combine this fact with the previous propositions to get a master lemma for passing between distributions:		We can combine this fact with the previous propositions to get a master lemma for passing between distributions:\noteryan{I think it would be better if in this section we: 1. Had the equal-slices subsection. 2. Then had one more subsection which: a) begins with the statement of this lemma; then, b) says, ``Psst, reader, this lemma's proof is very boring. We wouldn't be disappointed if you skipped reading it.''}
	\begin{lemma} \label{lem:distributions} Let $(\pi^m)$ and $(\nu^m)$ be distribution families. Assume $2 \ln n \leq r \leq n/2$. Let $J$ be an $[r,4r]$-random subset of $[n]$, let $x$ be drawn from $[k]^{\barJ}$ according to $\pi^{\|\barJ\|}$, and let $y$ be drawn from $[k]^J$ according to $\nu^{\|J\|}$. The resulting distribution on $(x,y)$ has total variation distance from $\pi^n$ which can be bounded as follows:		\begin{lemma} \label{lem:distributions} Let $(\pi^m)$ and $(\nu^m)$ be distribution families. Assume $2 \ln n \leq r \leq n/2$. Let $J$ be an $[r,4r]$-random subset of $[n]$, let $x$ be drawn from $[k]^{\barJ}$ according to $\pi^{\|\barJ\|}$, and let $y$ be drawn from $[k]^J$ according to $\nu^{\|J\|}$. The resulting distribution on $(x,y)$ has total variation distance from $\pi^n$ which can be bounded as follows:
	\begin{~~itemize~~}		\begin{enumerate}
	\item (Product to equal-slices.) If $\pi^m = \pi^{\otimes m}$ and $\nu^m = \eqs{\ell}^m$ for $\ell \leq k$, the bound is		\item (Product to equal-slices.) If $\pi^m = \pi^{\otimes m}$ and $\nu^m = \eqs{\ell}^m$ for $\ell \leq k$, the bound is
	\[		\[
Line 172:		Line 179:
	\]		\]
	\item (Equal-slices to product.) If $\pi^m = \eqs{k}^m$ and $\nu^m = \nu^{\otimes m}$, the bound is $4k \cdot r/\sqrt{n}$.		\item (Equal-slices to product.) If $\pi^m = \eqs{k}^m$ and $\nu^m = \nu^{\otimes m}$, the bound is $4k \cdot r/\sqrt{n}$.
	\item (Equal-slices to equal-slices.) If $\pi^m = \eqs{k}^m$ and $\nu^m = \eqs{\ell}^m$ for $\ell \leq k$, the bound is $4k \cdot r/\sqrt{n}$.		\item (Equal-slices to equal-slices.) \label{eqn:distrs-eqs-eqs} If $\pi^m = \eqs{k}^m$ and $\nu^m = \eqs{\ell}^m$ for $\ell \leq k$, the bound is $4k \cdot r/\sqrt{n}$.
	\end{~~itemize~~}		\end{enumerate}
	\end{lemma}		\end{lemma}
	\begin{proof}		\begin{proof}
	We apply Propositions~\ref{prop:prod-eqs}, \ref{prop:eqs-prod}, and \ref{prop:eqs-eqs} with $\eps = 2r/n$, but condition on $r \leq \|J\| \leq 4r$. This increases the total variation distance by at most $2\gamma$, where $\gamma$ is the probability that $r \leq \|J\| \leq 4r$ fails. By Fact~\ref{fact:dev}, the increase is at most $4\exp(-r/4)$, which is at most $2 r / \sqrt{n}$ using the lower bound $r \geq 2 \ln n$. The claimed bounds now follow.\noteryan{This is explained messily.}		We apply Propositions~\ref{prop:prod-eqs}, \ref{prop:eqs-prod}, and \ref{prop:eqs-eqs} with $\eps = 2r/n$, but condition on $r \leq \|J\| \leq 4r$. This increases the total variation distance by at most $2\gamma$, where $\gamma$ is the probability that $r \leq \|J\| \leq 4r$ fails. By Fact~\ref{fact:dev}, the increase is at most $4\exp(-r/4)$, which is at most $2 r / \sqrt{n}$ using the lower bound $r \geq 2 \ln n$. The claimed bounds now follow.\noteryan{This is explained messily.}
	\end{proof}		\end{proof}

128.237.250.15 at 21:49, 15 May 2009

2009-05-15T21:49:18Z

Show changes

Ryanworldwide at 21:14, 14 May 2009

2009-05-14T21:14:21Z

← Older revision		Revision as of 14:14, 14 May 2009
Line 52:		Line 52:
	\subsection{Equal-slices}		\subsection{Equal-slices}

	\begin{definition} We say that $\nu$ is a \emph{random distribution} on $[k]$ if the vector $(\nu[1], \dots, \nu[k])$ is chosen uniformly from the ~~simplex~~ $~~\{(p_1, \dots, p_k) : \sum p_i = 1, p_i \geq 0\ \forall i\}~~$.		\begin{definition} \label{def:spacings} We say that $\nu$ is a \emph{random distribution} on $[k]$ if the vector of probabilities $(\nu[1], \dots, \nu[k])$ is formed as follows: $k$ points are chosen on the circle of unit circumference, uniformly and independently, and $\nu[a]$ is set to the length of the arc emanating clockwise from the $a$th point.
	\end{definition}		\end{definition}

	\begin{remark} It is well known (see, e.g.~\cite[Ch.\ 1]{Rei89}) that a random distribution $\nu$ can equivalently be defined by choosing $~~k-1$ points in $~~[0,1]~~$ uniformly and independently and letting $~~\nu[i]$ ~~be the length of~~ the $~~i$th spacing thus formed~~, $i = 1 \~~dots k~~$.\noteryan{~~The reader may take~~ this to ~~be the definition, if they desire~~.}		\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 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}		\end{remark}

Line 71:		Line 71:
	\end{proposition}		\end{proposition}

	The following observation ~~is also~~ crucial:		The following observation will be crucial:
	\begin{lemma} Let $x \sim \eqs{k}^n$, and let $a \sim [k-1]$ be uniformly random. Then $\chg{x}{k}{a}$ is distributed as $\eqs{k-1}^n$.		\begin{lemma} Let $x \sim \eqs{k}^n$, and let $a \sim [k-1]$ be uniformly random. Then $\chg{x}{k}{a}$ is distributed as~$\eqs{k-1}^n$.
	\end{lemma}		\end{lemma}
	\begin{proof}		\begin{proof}
	\~~noteryan~~{~~needs~~ to be ~~filled~~ in}		From the definition, the string $\chg{x}{k}{a}$ is distributed as follows: first $\nu$ is taken to be a random distribution on $[k]$; then $\wt{\nu}$ is taken to be the distribution on $[k-1]$ with $\wt{\nu}[b] = \nu[b]$ for $b \neq a$ and $\wt{\nu}[a] = \nu[a] + \nu[k]$; then a string is drawn from the product distribution $\wt{\nu}^{\otimes n}$. Thus it suffices to show that $\wt{\nu}$ is a random distribution on $[k-1]$ in the sense of Definition~\ref{def:spacings}. This is easy to see: having chosen $k$ points on the circle, thus forming $\nu$, we get the correct distribution $\wt{\nu}$ simply by removing the $k$th point. \noteryan{This is not especially well-explained; will try to think how to say it with the maximum combination of concision and correctness.}
	\end{proof}		\end{proof}

	\subsection{~~Random restrictions~~}		\subsection{Composite distributions}
	\begin{definition} A \emph{restriction} on $[k]^n$ is a pair $(J, x_\barJ)$, where $J \subseteq [n]$ and $x_\barJ \in [k]^{\barJ}$, where $\barJ = [n] \setminus J$. It is thought of as a ``partial string'', where the $\barJ$-coordinates are ``fixed'' according to $x_\barJ$ and the $J$-coordinates are still ``free''. Given a fixing $y_J \in [k]^J$, we write $(x_\barJ, y_J)$ for the complete composite string in $[k]^n$.\noteryan{~~Some may say~~ this ~~is bad~~ notation, ~~but~~ I believe it ~~is very~~ useful ~~notation. We can address this point.~~}		\begin{definition} A \emph{restriction} on $[k]^n$ is a pair $(J, x_\barJ)$, where $J \subseteq [n]$ and $x_\barJ \in [k]^{\barJ}$, where $\barJ = [n] \setminus J$. It is thought of as a ``partial string'', where the $\barJ$-coordinates are ``fixed'' according to $x_\barJ$ and the $J$-coordinates are still ``free''. Given a fixing $y_J \in [k]^J$, we write $(x_\barJ, y_J)$ for the complete composite string in $[k]^n$.\noteryan{Although this notation looks awkward, I believe it's useful\dots}
	\end{definition}		\end{definition}

	\begin{definition} \label{def:restriction} Let $0 \leq \eps \leq 1$ and let $(\pi^m)$ be a family of probability distributions, where $\pi^m$ is a distribution on $[k]^m$. We say that $(J, x_\barJ)$ is an \emph{$(\epsilon,\pi)$-random restriction} if $J$ is chosen by including each coordinate of $[n]$ independently with probability $\eps$, and then $x_\barJ$ is drawn from $[k]^{\barJ}$ according to $\pi^{\|\barJ\|}$.		\begin{definition} \label{def:restriction} Let $0 \leq \eps \leq 1$ and let $(\pi^m)$ be a family of probability distributions, where $\pi^m$ is a distribution on $[k]^m$. We say that $(J, x_\barJ)$ is an \emph{$(\epsilon,\pi)$-random restriction} if $J$ is chosen by including each coordinate of $[n]$ independently with probability $\eps$, and then $x_\barJ$ is drawn from $[k]^{\barJ}$ according to $\pi^{\|\barJ\|}$.
	\end{definition}		\end{definition}
	In the above definition, $\pi^m$ is typically either equal-slices $\eqs{k}^m$ or a product distribution $\nu^{\otimes m}$ based on some distribution $\nu$ on $[k]$. \\		In the above definition, $\pi^m$ is typically either equal-slices $\eqs{k}^m$ or a product distribution $\nu^{\otimes m}$ based on some distribution $\nu$ on $[k]$. We briefly record here a useful, standard large-deviation bound:

	~~The following~~ standard large-deviation bound ~~will prove useful~~:
	\begin{fact} \label{fact:large-dev} If $(J,x_\barJ)$ is an $(\epsilon,\pi)$-random restriction, then $(\eps/2)n \leq \|J\| \leq 2\eps n$ except with probability at most $2\exp(-\eps n/8)$.		\begin{fact} \label{fact:large-dev} If $(J,x_\barJ)$ is an $(\epsilon,\pi)$-random restriction, then $(\eps/2)n \leq \|J\| \leq 2\eps n$ except with probability at most $2\exp(-\eps n/8)$.
	\end{fact}		\end{fact}
Line 96:		Line 94:
	\end{fact}		\end{fact}

	Because of this, we can use Corollary~\ref{cor:mix-distance} to bound the total variation distance between $\pi^{\otimes n}$ and a composite distribution. For example, we conclude:~~\noteryan{this proposition lets us pass from uniform to eq-slices at the very beginning}~~		Because of this, we can use Corollary~\ref{cor:mix-distance} to bound the total variation distance between $\pi^{\otimes n}$ and a composite distribution. For example, we conclude:
	\begin{proposition} \label{prop:unif-composite} Let $\mu_k$ denote the uniform distribution $[k]$, and let $\nu$ be any distribution on $[k]$. Writing $\mu_k^{(\nu)}$ for the $(\eps,\mu_k,\nu)$-composite distribution on strings in $[k]^n$, we have		\begin{proposition} \label{prop:unif-composite} Let $\mu_k$ denote the uniform distribution $[k]$, and let $\nu$ be any distribution on $[k]$. Writing $\mu_k^{(\nu)}$ for the $(\eps,\mu_k,\nu)$-composite distribution on strings in $[k]^n$, we have
	\[		\[
Line 102:		Line 100:
	\]		\]
	\end{proposition}		\end{proposition}
	~~Since~~ the equal-slices distribution $\eqs{k}^{m}$ on $m$ coordinates is a mixture of product distributions $\nu^{\otimes m}$, we conclude from Proposition~\ref{prop:unif-composite} and Fact~\ref{fact:tv-mix}:		For any $\ell \leq k$, the equal-slices distribution $\eqs{\ell}^{m}$ on $m$ coordinates is a mixture of product distributions $\nu^{\otimes m}$ on $[k]^m$. Hence we conclude from Proposition~\ref{prop:unif-composite} and Fact~\ref{fact:tv-mix}:\noteryan{this proposition lets us pass from uniform to eq-slices at the very beginning}
	\begin{proposition} Let $\mu_k$ denote the uniform distribution $[k]$. Writing $\~~mu_k~~'$ for the $(\eps,\mu_k,\eqs{k})$-composite distribution on strings in $[k]^n$, we have		\begin{proposition} Let $\mu_k$ denote the uniform distribution $[k]$, and let $\ell \leq k$. Writing $\mu'$ for the $(\eps,\mu_k,\eqs{\ell})$-composite distribution on strings in $[k]^n$, we have
	\[		\[
	\dtv{\mu_k^{\otimes n}}{\~~mu_k~~'} \leq \sqrt{k-1} \cdot \eps \sqrt{n}.		\dtv{\mu_k^{\otimes n}}{\mu'} \leq \sqrt{k-1} \cdot \eps \sqrt{n}.
	\]		\]
	\end{proposition}		\end{proposition}

	Using Corollary~\ref{cor:mix-distance} more generally, we obtain:\noteryan{this lets us pass from an arbitrary product distribution to equal-slices}		Using Corollary~\ref{cor:mix-distance} more generally, we obtain:\noteryan{this lets us pass from an arbitrary product distribution to equal-slices}
	\begin{proposition} \label{prop:prod-composite} Let $\nu$ be any distribution on $[k]$. Writing $\nu'$ for the $(\eps,\nu,\eqs{k})$-composite distribution on strings in $[k]^n$, we have		\begin{proposition} \label{prop:prod-composite} Let $\nu$ be any distribution on $[k]$, and $\ell \leq k$. Writing $\nu'$ for the $(\eps,\nu,\eqs{\ell})$-composite distribution on strings in $[k]^n$, we have
	\[		\[
	\dtv{\mu_k^{\otimes n}}{\nu'} \leq {\textstyle \sqrt{\frac{1}{\min(\nu)}-1}} \cdot \eps \sqrt{n}.		\dtv{\mu_k^{\otimes n}}{\nu'} \leq {\textstyle \sqrt{\frac{1}{\min(\nu)}-1}} \cdot \eps \sqrt{n}.
	\]		\]
	\end{proposition}		\end{proposition}
	Hence:\noteryan{this proposition lets us do restrictions under equal slices}		Hence:\noteryan{this proposition lets us do restrictions under equal slices; even to equal-slices on fewer symbols}
	\begin{proposition} \label{prop:eqs-compos} Let $\~~eqsc{~~k}^{(\~~eps)~~}$ denote the $(\eps, \eqs{k}, \eqs{k})$-composite distribution on strings in $[k]^n$. Then		\begin{proposition} \label{prop:eqs-compos} Let $2 \leq \ell \leq k$ and let $\wt{\mu}$ denote the $(\eps, \eqs{k}, \eqs{\ell})$-composite distribution on strings in $[k]^n$. Then
	\[		\[
	\dtv{\eqs{~~\mu~~}^n}{\~~eqsc{k}^~~{(\~~eps)~~}} \leq 2k \eps \sqrt{n}.		\dtv{\eqs{k}^n}{\wt{\mu}} \leq 2k \eps \sqrt{n}.
	\]		\]
	\end{proposition}		\end{proposition}
	\begin{proof}		\begin{proof}
	Recalling again that $\eqs{~~\mu~~}^m$ is the mixture of product distributions $\nu^{\otimes m}$, where $\nu$ is a random distribution on $[k]$, we apply Fact~\ref{fact:tv-mix} and Proposition~\ref{prop:prod-composite} to conclude		Recalling again that $\eqs{k}^m$ is the mixture of product distributions $\nu^{\otimes m}$, where $\nu$ is a random distribution on $[k]$, we apply Fact~\ref{fact:tv-mix} and Proposition~\ref{prop:prod-composite} to conclude
	\[		\[
	\dtv{\eqs{~~\mu~~}^n}{\~~eqsc{k}^~~{(\~~eps)~~}} \leq \Ex_{\nu}\left[{\textstyle \sqrt{\frac{1}{\min(\nu)}-1}}\right] \cdot \eps \sqrt{n}.		\dtv{\eqs{k}^n}{\wt{\mu}} \leq \Ex_{\nu}\left[{\textstyle \sqrt{\frac{1}{\min(\nu)}-1}}\right] \cdot \eps \sqrt{n}.
	\]		\]
	We can upper-bound the expectation by		We can upper-bound the expectation\noteryan{Undoubtedly someone has worked hard on this $-1/2$th moment of the least spacing before (Devroye '81 or '86 perhaps), but I think it's probably okay to do the following simple thing here} by
	\[		\[
	\Ex_{\nu}\left[{\textstyle \sqrt{\frac{1}{\min(\nu)}}}\right] = \int_{0}^\infty \Pr_{\nu}\left[{\textstyle \sqrt{\frac{1}{\min(\nu)}}} \geq t\right]\,dt = \int_{0}^\infty \Pr_{\nu}\left[\min(\nu) \leq \frac{1}{t^2}\right]\,dt \leq k + \int_{k}^\infty \Pr_{\nu}\left[\min(\nu) \leq \frac{1}{t^2}\right]\,dt. \label{eqn:eq-dist-integral}		\Ex_{\nu}\left[{\textstyle \sqrt{\frac{1}{\min(\nu)}}}\right] = \int_{0}^\infty \Pr_{\nu}\left[{\textstyle \sqrt{\frac{1}{\min(\nu)}}} \geq t\right]\,dt = \int_{0}^\infty \Pr_{\nu}\left[\min(\nu) \leq \frac{1}{t^2}\right]\,dt \leq k + \int_{k}^\infty \Pr_{\nu}\left[\min(\nu) \leq \frac{1}{t^2}\right]\,dt. \label{eqn:eq-dist-integral}
Line 137:		Line 135:
	\end{eqnarray}		\end{eqnarray}
	}		}
	~~Think of~~ $\nu$ ~~as being given by the spacings between~~ $k$ ~~random~~ points chosen from $~~[0,~~1]$. By a union bound, ~~$\Pr_{\nu}[\min(\nu) \leq 1/t^2]$~~ is at most $\binom{k}{2}$ times the probability that two random points ~~in $[0,1]$~~ are within distance $1/t^2$~~. This~~ is ~~clearly at most~~ $2/t^2$. Hence the integral above is bounded by		From Definition~\ref{def:spacings}, the event $\min(\nu) \leq 1/t^2$ occurs only if some two out of $k$ points chosen uniformly from the unit circle are within distance $1/t^2$. By a union bound, this is at most $\binom{k}{2}$ times the probability that two random points on the unit circle are within distance $1/t^2$, which is precisely $2/t^2$. Hence the integral above is bounded by
	\[		\[
	\int_{k}^\infty \binom{k}{2} \cdot \frac{2}{t^2}\,dt \leq \int_{k}^\infty \frac{k^2}{t^2}\,dt = k,		\int_{k}^\infty \binom{k}{2} \cdot \frac{2}{t^2}\,dt \leq \int_{k}^\infty \frac{k^2}{t^2}\,dt = k,

Ryanworldwide at 04:09, 14 May 2009

2009-05-14T04:09:11Z

← Older revision		Revision as of 21:09, 13 May 2009
Line 70:		Line 70:
	\begin{proposition} The equal-slices distribution $\eqs{k}^{n}$ is equivalent to first choosing a slice uniformly from the $\binom{n+k-1}{k-1}$ many possibilities, then drawing a string uniformly from that slice. \noteryan{Include proof? If so, it's by throwing $n+k-1$ points into the interval and looking at the result in two ways.}		\begin{proposition} The equal-slices distribution $\eqs{k}^{n}$ is equivalent to first choosing a slice uniformly from the $\binom{n+k-1}{k-1}$ many possibilities, then drawing a string uniformly from that slice. \noteryan{Include proof? If so, it's by throwing $n+k-1$ points into the interval and looking at the result in two ways.}
	\end{proposition}		\end{proposition}

			The following observation is also crucial:
			\begin{lemma} Let $x \sim \eqs{k}^n$, and let $a \sim [k-1]$ be uniformly random. Then $\chg{x}{k}{a}$ is distributed as $\eqs{k-1}^n$.
			\end{lemma}
			\begin{proof}
			\noteryan{needs to be filled in}
			\end{proof}

	\subsection{Random restrictions}		\subsection{Random restrictions}