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.



How to estimate a total variation distance?
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}


