How to estimate a total variation distance?

Question

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.

Answer 1

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}