On the variational distance of independently repeated experiments
Let P and Q be two probability distributions which differ only for values with non-zero probability. We show that the variational distance between the n-fold product distributions P^n and Q^n cannot grow faster than the square root of n.
\section{Preliminaries}

Let $P$ be a probability distribution with range ${\mathcal{Z}}$ and let $n \in
{\mathbb{N}}$. We denote by $P^n$ the $n$-fold \emph{product
  distribution}, that is,
\[
  P^n(z_1, \ldots, z_n) = \prod_{i=1}^n P(z_i) 
\]
for any $z_1, \ldots, z_n \in {\mathcal{Z}}$. Note that $P^n$ describes $n$
independently repeated random experiments with distribution $P$.


The \emph{variational distance} between two probability distributions
$P$ and $Q$ with range ${\mathcal{Z}}$ is defined as\footnote{See, e.g.,
  \cite{CovTho91}. $\delta(\cdot, \cdot)$ is also called
  \emph{statistical difference}~\cite{Reyzin04}, \emph{Kolmogorov
    distance}, or \emph{trace distance}~\cite{NieChu00}.}
\[
\delta(P,Q) := \frac{1}{2} \sum_{z \in {\mathcal{Z}}} |P(z) - Q(z)| \ .
\]
Note that $\delta$ is a distance measure on the set of probability
distributions with range ${\mathcal{Z}}$. In particular, $\delta$ is symmetric,
$\delta(P,Q) = 0$ if and only if $P=Q$, and the triangle inequality
\begin{equation} \label{eq:tri}
  \delta(P, Q) \leq \delta(P, P') + \delta(P', Q)
\end{equation}
holds.

\section{Main Result and Proof}

\subsection{Upper Bounds for the Variational Distance}

Let $P$ and $Q$ be two probability distributions with range ${\mathcal{Z}}$.  It
is a direct consequence of the triangle inequality~\eqref{eq:tri} that
the variational distance $\delta(P^n, Q^n)$ between the $n$-fold
product distributions $P^n$ and $Q^n$ cannot grow faster than linearly
in $n$, i.e.,
\begin{equation} \label{eq:linear}
  \delta(P^n, Q^n) \leq n \delta(P, Q) \ .
\end{equation}
Moreover, it is easy to find examples where this inequality is almost
tight. Let, e.g., $P$ and $Q$ be two binary distributions with range
${\mathcal{Z}} = \{0,1\}$ such that $P(1)=0$ and $Q(1) = \varepsilon$ for some
$\varepsilon>0$. If $n \varepsilon \ll 1$ then the variational
distance $\delta(P^n, Q^n)$ is roughly equal to $n \delta(P, Q) = n
\varepsilon$.

However, the upper bound~\eqref{eq:linear} can only be close to
optimal if, for some element $z \in {\mathcal{Z}}$, the relative difference
$|P(z)-Q(z)|/(P(z) + Q(z))$ between the probabilities is large. (Note
that, in the above example, this relative difference for $z=1$ equals
one.)  Indeed, the following result states that, in all other cases,
$\delta(P^n, Q^n)$ cannot grow more than the square root of~$n$.

\begin{lemma} \label{lem:int}
  Let $P$ and $Q$ be two probability distributions with range ${\mathcal{Z}}$,
  let ${\mathcal{D}} := \{z \in {\mathcal{Z}} : P(z) \neq Q(z)\}$ be the subset of ${\mathcal{Z}}$
  where $P$ and $Q$ differ, and let ${\bar{p}}:=\inf_{z \in {\mathcal{D}}}(\min(P(z),
  Q(z)))$. If ${\bar{p}}>0$ then, for any $n \in {\mathbb{N}}$,
  \[
    \delta(P^n, Q^n) 
  \leq 
      \sqrt{\frac{1}{\pi {\bar{p}}}}  \sqrt{n+\frac{1}{{\bar{p}}}} 
    \, \delta(P, Q)
  \]
  and
   \[
    \delta(P^n, Q^n) 
  \leq 
      \sqrt{\frac{n}{2 {\bar{p}}}} \, \delta(P, Q) \ .
  \] 
\end{lemma}

The first bound of Lemma~\ref{lem:int} is optimal in the sense that,
for any ${\bar{p}}>0$, there are probability distributions $P$ and $Q$ with
minimum probability ${\bar{p}}$ such that the quotient between the left and
the right hand side of the inequality approaches one for increasing
$n$ (as long as $\delta(P^n,Q^n) \ll 1$). On the other hand, the
constant $\frac{1}{2}$ in the second bound is the smallest value of
$c$ such that $\delta(P^n, Q^n) \leq \sqrt{c n/{{\bar{p}}}} \, \delta(P, Q)$
always holds.

The result of Lemma~\ref{lem:int} is also complementary to a lower
bound derived in~\cite{Reyzin04}, which states that, if the maximum
probabilities of $P$ and $Q$ are small enough and if $n$ is not too
large, then $\delta(P^n, Q^n) \geq \Omega(\sqrt{n}) \delta(P,Q)$.

\subsection{Proof of Lemma~\ref{lem:int}}

To prove Lemma~\ref{lem:int}, we consider a probability distribution
$P_t$ parameterized by some real value $t$ and compute a bound on the
derivative, with respect to $t$, of the variational distance
$\delta(P_t^n, P_{t_o}^n)$.


\begin{lemma} \label{lem:der}
  Let $\{P_{t}\}_{t \in {\mathbb{R}}}$ be a family of probability distributions
  with range ${\mathcal{Z}}$ parameterized by $t \in {\mathbb{R}}$, let $t_0 \in {\mathbb{R}}$,
  and let $z_1, z_2 \in {\mathcal{Z}}$ such that\footnote{$\der{
      f(t)}{t}{t_0}$ denotes the right derivative $\lim_{t \to
      t_0^{+}} \frac{f(t) - f(t_0)}{t-t_0}$ of the function $f$ at
    $t=t_0$.}
  \[
    \der{P_t(z)}{t}{t_0}
  = 
    \begin{cases}
      1 & \text{if $z = z_1$} \\
      -1 & \text{if $z = z_2$}
    \end{cases} 
  \]
  and $P_t(z) = P_{t_0}(z)$ for any $z \in {\mathcal{Z}} \backslash
  \{z_1, z_2\}$.  If $p:=P_{t_0}(z_1)$ and $p':=P_{t_0}(z_2)$
  are nonzero then
  \[
     \der{\delta(P_{t}^n, P_{t_0}^n)}{t}{t_0} 
  \leq
      \frac{1}{\sqrt{2 \pi}} 
    \sqrt{\frac{1}{p} + \frac{1}{p'}} 
    \, \sqrt{n+\frac{1}{\min(p,p')}}
  \]
  and
  \[
     \der{\delta(P_{t}^n, P_{t_0}^n)}{t}{t_0} 
  \leq
      \frac{1}{2} 
    \sqrt{\frac{1}{p} + \frac{1}{p'}} 
    \, \sqrt{n} \ .
  \]
\end{lemma}

\begin{proof}
  Assume without loss of generality that $t_0 = 0$. Since $P_t(z)$
  does not depend on $t$ for $z \in {\mathcal{Z}} \backslash \{z_1,
  z_2\}$, we have $P_t(z_1) + P_t(z_2) = p + p'$, and thus, by
  the definition of the variational distance,
  \[
    \delta(P_{t}^n, P_{0}^n)
  =
    \frac{1}{2} \sum_{k=0}^{n} 
      q(k) \sum_{r=0}^{k} \binom{k}{r} | a_{k,r}(t) |
  \]
  where
   \[
    q(k) := \binom{n}{k} (p+p')^k (1-p-p')^{n-k}
  \]
  and
  \[
    a_{k,r}(t)
  :=
      \left(\frac{p}{p+p'}\right)^r
        \left(\frac{p'}{p+p'}\right)^{k-r}
    - \left(\frac{P_{t}(z_1)}{p+p'}\right)^r
        \left(\frac{P_{t}(z_2)}{p + p'}\right)^{k-r} 
     \ .
  \]
  Let $a'_{k,r}(0):=\der{a_{k,r}(t)}{t}{0}$.  Because $a_{k,r}(0)=0$,
  we have
  \[
  \der{|a_{k,r}(t)|}{t}{0} = |a'_{k,r}(0)| \ .
  \]  
  Moreover, it follows from~\eqref{eq:derpot} that $a'_{k,r}(0) \geq
  0$ if and only if $r \leq {\bar{r}} := \lfloor k \frac{p}{p+p'} \rfloor$.
  We thus conclude
  \begin{equation} \label{eq:completesum}
    \der{\delta(P_{t}^n, P_{0}^n)}{t}{0} 
  = 
    \sum_{k=0}^{n} q(k)
      \sum_{r=0}^{{\bar{r}}} \binom{k}{r}
        a'_{k,r}(0) \ .
  \end{equation}
  Let $\alpha:=\frac{p}{p+p'}$ and $\beta:=\frac{p'}{p+p'}$. The last
  sum in the above expression can then be rewritten as
  \begin{align}
    \sum_{r=0}^{{\bar{r}}} \binom{k}{r}
      a'_{k,r}(0)
  & = 
    \frac{1}{p+p'} \sum_{r=0}^{{\bar{r}}} 
    \left[
      \binom{k}{r} (k-r) \alpha^r \beta^{k-r-1}
      - \binom{k}{r} r \alpha^{r-1} \beta^{k-r}
    \right] \nonumber \\
  & = 
    \frac{k}{p+p'} 
      \left[
        \sum_{r=0}^{{\bar{r}}} 
          \binom{k-1}{r} \alpha^r \beta^{k-r-1}
        - \sum_{r=0}^{{\bar{r}}-1} 
          \binom{k-1}{r} \alpha^r \beta^{k-r-1} 
      \right] \nonumber \\
  & =
    \frac{k}{p+p'} 
    \binom{k-1}{{\bar{r}}} \alpha^{\bar{r}}  \beta^{k-{\bar{r}}-1} \ .  \label{eq:intsum}
  \end{align}
  With the definition ${\tilde{\alpha}}:=\frac{{\bar{r}}+1}{k+1}$,
  ${\tilde{\beta}}:=\frac{(k+1)-({\bar{r}}+1)}{k+1}$, we have
  \begin{align}
    \binom{k-1}{{\bar{r}}} \alpha^{\bar{r}} \beta^{k-{\bar{r}}-1}
  & =  
    \binom{k+1}{{\bar{r}}+1} \frac{({\bar{r}}+1) ((k+1)-({\bar{r}}+1))}{k (k+1)}
      \frac{\alpha^{{\bar{r}}+1} \beta^{(k+1)-({\bar{r}}+1)}}{\alpha \beta} \nonumber \\
  & \leq
    \binom{k+1}{{\bar{r}}+1} \frac{({\bar{r}}+1) ((k+1)-({\bar{r}}+1))}{k (k+1)} 
      \frac{{\tilde{\alpha}}^{{\bar{r}}+1} {\tilde{\beta}}^{(k+1)-({\bar{r}}+1)}}{\alpha \beta} \nonumber\\
  & \leq
    \sqrt{\frac{1}{2 \pi (k+1) {\tilde{\alpha}} {\tilde{\beta}}}}
    \cdot \frac{({\bar{r}}+1) ((k+1)-({\bar{r}}+1))}{k (k+1)\alpha \beta} \nonumber\\
  & = 
    \frac{1}{k} \sqrt{\frac{k+1}{2 \pi \alpha \beta}} \,
      \sqrt{\frac{{\tilde{\alpha}} {\tilde{\beta}}}{\alpha \beta}} \ , \label{eq:intbinombound} 
  \end{align}
  where the first inequality follows from~\eqref{eq:maxpot} and the
  second from Lemma~\ref{lem:stirbin}.  Using the definition of ${\bar{r}}$
  and letting $\gamma:=k \alpha - \lfloor k \alpha \rfloor$, the
  expression in the second square root of the last term can be bounded
  by
  \begin{multline}
    \frac{{\tilde{\alpha}} {\tilde{\beta}}}{\alpha \beta}
  =    
    \frac{\lfloor k \alpha \rfloor+1}{\alpha (k+1)} 
      \cdot \frac{(k+1) - (\lfloor k \alpha \rfloor +1)}{ \beta (k+1)}
  =
    \frac{k \alpha+(1-\gamma)}{\alpha (k+1)} 
      \cdot \frac{k \beta + \gamma}{\beta (k+1)} \\
  =
    \frac{k + \frac{1-\gamma}{\alpha}}{k+1} 
    \cdot \frac{k + \frac{\gamma}{\beta}}{k+1} 
  \leq
    \frac{k+\frac{1}{\min(\alpha, \beta)}}{k+1} \ ,
  \end{multline}
  where the last inequality follows from the fact that
  $\frac{1-\gamma}{\alpha} = \frac{1-\gamma}{1-\beta}$ and
  $\frac{\gamma}{\beta}$ cannot both be larger than one, since $\beta,
  \gamma \in [0,1]$.  Combining this with~\eqref{eq:intbinombound}
  and~\eqref{eq:intsum}, we find
  \begin{equation} \label{eq:partsumone}
    \sum_{r=0}^{{\bar{r}}} \binom{k}{r}
      a'_{k,r}(0)  
  =
    \frac{k}{p+p'} \binom{k-1}{{\bar{r}}} \alpha^{\bar{r}} \beta^{k-{\bar{r}}-1}
  \leq 
    s(k)
    \ ,
  \end{equation}
  where
  \[
    s(k)
  :=   
      \frac{1}{p+p'} 
    \sqrt{\frac{k+\frac{1}{\min(\alpha, \beta)}}{2 \pi\alpha \beta}} \ .
  \]
  Alternatively, the left hand side of~\eqref{eq:partsumone} can be
  upper bounded by
  \begin{equation} \label{eq:salt}
    {\tilde{s}}(k)
  :=   
    \frac{1}{p+p'} \, \sqrt{\frac{k}{4 \alpha \beta}} \ .
  \end{equation} 
  To see this, assume first that $\alpha k \geq 2$ and $\beta k \geq
  2$. Then $\frac{1}{\min(\alpha, \beta)} \leq \frac{k}{2}$ which
  implies
  \[
    s(k) 
  \leq 
    \frac{1}{p+p'} \sqrt{\frac{\frac{3}{2} k}{2 \pi \alpha \beta}} 
  <
    {\tilde{s}}(k) \ .
  \]
  On the other hand, if $\alpha k < 2$ or $\beta k < 2$, the bound
  follows from a straightforward calculation using~\eqref{eq:maxpot}.
  (In this case, ${\bar{r}}$ or $(k-1)-{\bar{r}}$ is either $0$ or $1$, i.e., the
  binomial $\binom{k-1}{{\bar{r}}}$ in~\eqref{eq:partsumone} equals $1$ or
  $k-1$.)
  
  When~\eqref{eq:completesum} is combined with~\eqref{eq:partsumone},
  we obtain
  \begin{equation} \label{eq:sumcompletebound}
    \der{\delta(P_t^n, P_{0}^n)}{t}{0} 
  \leq
    \sum_{k=0}^{n} q(k) s(k) \ .
  \end{equation}
  Note that $s(k)$ is a concave function in $k$ and that $q(k)$ are
  the probabilities of a binomial distribution with mean $n (p+p')$,
  that is, $\sum_{k=0}^n q(k) = 1$ and $\sum_{k=0}^n q(k) k = n
  (p+p')$.  We can thus apply Jensen's inequality to find an upper
  bound for the sum on the right hand side
  of~\eqref{eq:sumcompletebound}, i.e.,
  \[
    \der{\delta(P_t^n, P_0^n)}{t}{0} 
  \leq
    \sum_{k=0}^{n} q(k)  s(k)
  \leq
    s\bigl(\sum_{k=0}^{n} q(k) k\bigr) 
  = 
    s(n (p+p')) \ ,
  \]
  from which the first inequality of the lemma follows.
  
  Similarly, because ${\tilde{s}}(k)$ is concave in $k$ as well, we have
  \[
    \der{\delta(P_t^n, P_0^n)}{t}{0} 
  \leq
    {\tilde{s}}(n  (p+p')) \ ,
  \]
  which implies the second inequality of the lemma.
\end{proof}

We now use the bounds provided by Lemma~\ref{lem:der} to prove our
main result.

\begin{proof}[Proof of Lemma~\ref{lem:int}]
  
  We first prove the first inequality of the lemma for the special
  case where the probabilities $P$ and $Q$ only differ for two values
  $z_1$ and $z_2$. Assume (without loss of generality) that
  $P(z_1) \leq Q(z_1)$ and let $p:=P(z_1)$, $p':= P(z_2)$,
  $q:=Q(z_1)$.  For $t \in [p,q]$, let $P_t$ be the distribution
  with range ${\mathcal{Z}}$ given by
\[
  P_t := \frac{q-t}{q-p} P + \frac{t-p}{q-p} Q \ .
\]
i.e., $P_t(z_1) = t$, $P_t(z_2) = p+p'-t$, and $P_t(z) = P(z)
= Q(z)$ for any $z \in {\mathcal{Z}} \backslash \{z_1, z_2\}$. We can
thus apply the first inequality of Lemma~\ref{lem:der} which gives
\[
\begin{split}
  \der{\delta(P_s^n, P_{t}^n)}{s}{t} 
& \leq       
       \frac{1}{\sqrt{2 \pi}} 
    \sqrt{\frac{1}{t} + \frac{1}{p+p'-t}} 
    \, \sqrt{n+\frac{1}{\min(t,p+p'-t)}} \\
& \leq
      \frac{1}{\sqrt{2 \pi}} 
    \sqrt{\frac{2}{{\bar{p}}}} 
    \, \sqrt{n+\frac{1}{{\bar{p}}}}   \ .
\end{split}
\]
Using Lemma~\ref{lem:pathint}, we obtain
\[
  \delta(P^n, Q^n) = \delta(P_p^n, P_q^n) 
\leq
  \int_{p}^{q}  \der{\delta(P_s^n, P_{t}^n)}{s}{t} {\mathrm{d}} t
\leq
  (q-p) \frac{1}{\sqrt{2 \pi}} 
    \sqrt{\frac{2}{{\bar{p}}}} 
    \, \sqrt{n+\frac{1}{{\bar{p}}}} \ .
\]
Since $q-p = \delta(P,Q)$, this concludes the proof of the first
inequality of the lemma for the special case where the probabilities
$P$ and $Q$ differ for at most two values in ${\mathcal{Z}}$.

To prove the general case, we first observe that if the set ${\mathcal{D}}$ is
infinite, then ${\bar{p}}$ equals zero and nothing has to be proven. On the
other hand, if ${\mathcal{D}}$ is finite, it is easy to see that there exists a
sequence $(P_i)_{i=1, \ldots, m}$ (for some $m \in {\mathbb{N}}$) of
distributions with range ${\mathcal{Z}}$ such that
\begin{itemize}
\item $P_1 = P$ and $P_m = Q$,
\item for any $i \in \{1, \ldots, m\}$, the distributions $P_i$ and
  $P_{i+1}$ differ only for two elements in ${\mathcal{D}}$,
\item $\min_{z \in {\mathcal{D}}} P_i(z) \geq {\bar{p}}$, for all $i \in \{1, \ldots,
  m\}$, and
\item $\sum_{i=1}^{m-1} \delta(P_i, P_{i+1}) = \delta(P_1, P_m)$.
\end{itemize}
The general assertion then follows directly from the special case
proven above and the triangle inequality~\eqref{eq:tri}, i.e.,
\[
\begin{split}
  \delta(P^n, Q^n)
\leq 
  \sum_{i=1}^{m-1} \delta(P_i^n P_{i+1}^n)
& \leq
  \sum_{i=1}^{m-1} \sqrt{\frac{1}{\pi {\bar{p}}}} \, \sqrt{n+\frac{1}{{\bar{p}}}} 
    \, \delta(P_i, P_{i+1}) \\
& =
  \sqrt{\frac{1}{\pi {\bar{p}}}} \, \sqrt{n+\frac{1}{{\bar{p}}}} 
    \, \delta(P, Q) \ .
\end{split}
\]

The second inequality follows by exactly the same reasoning based on
the second inequality of Lemma~\ref{lem:der}.
\end{proof}


2005-09-05T13:38:42.000
0509
cs/0509013
en
https://arxiv.org/abs/cs/0509013
Let P and Q be two probability distributions which differ only for values with non-zero probability. We show that the variational distance between the n-fold product distributions P^n and Q^n cannot grow faster than the square root of n.
Information Theory (cs.IT)
On the variational distance of independently repeated experiments
Qwen/Qwen-72B
1. YES
2. YES