2
$\begingroup$

Let $X_1, \ldots, X_n$ be independent Bernoulli random variables. Then $Pr[X_i=1]=Pr[X_i=0]=1/2$. Let $X = (X_1, \ldots, X_n)$ and $v \in \{0,1\}^n$, $Y=v \cdot X$, $Z=Y-1$. Let \begin{align} \mu_1(x) = Pr[Y=x], \ \mu_2(x)=Pr[Z=x], \ x \in [n]=\{1, \ldots, n\}. \end{align} Are there some method to estimate the total variation distance? \begin{align} d_{TV}(\mu_1, \mu_2) & = \frac{1}{2} \sum_{x \in [n]} | \mu_1(x) - \mu_2(x) | \\ & = \frac{1}{2} \sum_{x \in [n]} | Pr[Y=x] - Pr[Z=x] |. \end{align} Without loss of generality, we many assume that $v=(1,\ldots, 1,0,\ldots,0)$, where the number of $1$'s is $k$ ($0 < k \leq n$). Then \begin{align} d_{TV}(\mu_1, \mu_2) & = \frac{1}{2} \sum_{x \in [n]} | Pr[Y=x] - Pr[Z=x] | \\ & = \frac{1}{2} \sum_{x \in [n]} | Pr[X_1+\cdots+X_k=x] - Pr[X_1+\cdots + X_k=x+1] |. \end{align}

Assume that $n$ is sufficient large. Do we have $d_{TV}(\mu_1, \mu_2)< 1-\epsilon$ for some $0 \leq \epsilon \leq 1$? Thank you very much.

$\endgroup$
  • $\begingroup$ Looks like the distributions of $Y$ and $Z$ only depend on $k$ ($=$ the number of 1-components of $v$). Do you also assume that $k$ is large? And why do you even need $n$? $\endgroup$ – Serguei Popov Aug 3 '18 at 19:05
  • $\begingroup$ @Serguei, thank you very much for your comments. Yes, I also assume that $k$ is large. $\endgroup$ – Jianrong Li Aug 3 '18 at 19:10
3
$\begingroup$

For the TV-distance, we have \begin{align} d_{TV}= \frac{1}{2} \sum_{x=0}^k |d_x| \end{align} (with the summation actually beginning at $x=0$), where \begin{multline*} d_x:=P(S_k=x) - P(S_k=x+1)=\frac1{2^k}\,\Big(\binom kx-\binom k{x+1}\Big) \\ =\frac1{2^k}\,\frac{k!}{(x+1)!(k-x)!}\,(2x-(k-1)) \end{multline*} and $S_k:=X_1+\cdots+X_k$, so that $d_x\le0$ for $x=0,\dots,m:=\lfloor (k-1)/2\rfloor$ and $d_x>0$ for $x=m+1,\dots,k$. Note also that $d_x=c_x-c_{x+1}$, where $c_x:=\frac1{2^k}\,\binom kx$. So, \begin{align*} 2d_{TV}&=-\sum_{x=0}^m d_x+\sum_{x=m+1}^k d_x \\ &=-\sum_{x=0}^m c_x+\sum_{x=0}^m c_{x+1}+\sum_{x=m+1}^k c_x-\sum_{x=m+1}^k c_{x+1} \\ &=-\sum_{x=0}^m c_x+\sum_{x=1}^{m+1} c_x+\sum_{x=m+1}^k c_x-\sum_{x=m+2}^{k+1} c_x \\ &=c_{m+1}-c_0+c_{m+1}-c_{k+1} \\ &=c_{m+1}-1+c_{m+1}-0 \\ &=\frac1{2^k}\,\Big(2\binom k{m+1}-1\Big) \sim\sqrt{\frac 8{\pi k}} \end{align*} as $k\to\infty$, by Stirling's formula, so that \begin{equation} d_{TV} \sim\sqrt{\frac 2{\pi k}}. \end{equation}

$\endgroup$
  • $\begingroup$ @losif Pinelis, thank you very much for your answer. I am trying to understand your answer. How to show that $-\sum_{x=0}^m d_x+\sum_{x=m+1}^k d_x=\frac1{2^k}\,\Big(2\binom k{m+1}-1\Big)$? $\endgroup$ – Jianrong Li Aug 4 '18 at 13:57
  • $\begingroup$ @losif Pinelis, I have another question, should we have $m = \lfloor (k-1)/2 \rfloor$? Thank you very much. $\endgroup$ – Jianrong Li Aug 4 '18 at 14:36
  • $\begingroup$ I have added details concerning your first question, and also fixed the typo concerning the definition of $m$. $\endgroup$ – Iosif Pinelis Aug 5 '18 at 2:35
  • $\begingroup$ @losif Pinelis, thank you very much for your kind help. $\endgroup$ – Jianrong Li Aug 5 '18 at 3:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.