<s>[INST] How to estimate a total variation distance? 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.
 [/INST] 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}
</s>