# Total Variation distance of polynomials of Bernoulli R.V.s

Let $X_i, Y_i$ be i.i.d Bernoulli $0/1$ random variables with $\mathbb{E}[X_i] = p$ and $\mathbb{E}[Y_i] = q$.

Let

\begin{align*} X &= X_1 X_2 + Χ_2 Χ_3 + \ldots +X_{n-2} X_{n-1}+ X_{n-1} X_n\\ Y &= Y_1 Y_2 + Y_2 Y_3 + \ldots +Y_{n-2} Y_{n-1}+ Y_{n-1} Y_n \end{align*}

I would like to get an upper bound on the total variation distance of $X$ and $Y$.

Right now I have the following bound using data processing, and Pinsker's inequalities.

\begin{align*} d_{tv}(X,Y) &\leq d_{tv}((X_1,\ldots,X_n),(Y_1, \ldots, Y_n)) \\ &\leq \sqrt{\frac12 D((X_1,\ldots,X_n)\|(Y_1, \ldots, Y_n))} \\ &= \sqrt{\frac{n}{2} D(X_1\|Y_1)} \\ &= \sqrt{\frac{n}{2} \left(p \log \frac{p}{q} + (1-p) \log \frac{1-p}{1-q} \right)}\\ &\leq 4 \sqrt{\frac{n}{(1-p)p}} | p-q| \end{align*}

I would like to get a better upper bound, since I suspect that the correct bound should be $4 \sqrt{\frac{n}{(1-p)}} | p-q|$.

The following plot shows the exact total variation distance (blue line) for $p \in (0,1)$, $q = p+0.01$,$n=100$ and the upper bound $4 \sqrt{\frac{n}{(1-p)}} | p-q|$ (green line).