# Estimate an expression about probability about Bernoulli random variables

Given $$v_{ij} \in \{0,1\}$$, $$i \in \{1,2\}$$, $$j \in \{1,2,\ldots,n\}$$. Let $$X_1, X_2, \ldots, X_n$$ be random variables, $$P[X_i=1]=P[X_i=0]=1/2$$, $$i \in \{1,\ldots, n\}$$. By checking many examples, I think that the following is true: when $$|v_1|, |v_2|$$ are large enough, \begin{align} \frac{1}{2} \sum_{x_1=0}^n \sum_{x_2=0}^n | P[ \sum_{r=1}^n v_{1r}X_r = x_1, \sum_{r=1}^n v_{2r}X_r = x_2 ] - P[ \sum_{r=1}^n v_{1r}X_r = x_1+1, \sum_{r=1}^n v_{2r}X_r = x_2+1 ] | < 1-\epsilon. \end{align} Is there some method to prove this? Thank you very much.

For example, let $$n=4$$, and $$v_{1}=(v_{11},\ldots,v_{14})=(1,1,1,0), v_2=(v_{21},\ldots,v_{24})=(0,0,1,1)$$, then the following Python codes gives the result $$0.3446349999999999$$.

import numpy as np

N = 10**5

XX = [np.random.randint(2, size=4) for n in np.arange(N)]

r=0
for x1 in range(0,5):
for x2 in range(0,5):
P1 = list(map(lambda X: (X[0]+X[1]+X[2]==x1)&(X[2]+X[3]==x2), XX))
P2 = list(map(lambda X: (X[0]+X[1]+X[2]==x1+1)&(X[2]+X[3]==x2+1), XX))
r=r+abs(np.mean(P1)-np.mean(P2))
r/2


Let $$n=4$$, and $$v_{1}=(v_{11},\ldots,v_{14})=(0,1,1,1), v_2=(v_{21},\ldots,v_{24})=(1,1,1,1)$$, then the following Python codes gives the result $$0.31340999999999997$$.

import numpy as np

N = 10**5

XX = [np.random.randint(2, size=4) for n in np.arange(N)]

r=0
for x1 in range(0,5):
for x2 in range(0,5):
P1 = list(map(lambda X: (X[1]+X[2]+X[3]==x1)&(X[0]+X[1]+X[2]+X[3]==x2), XX))
P2 = list(map(lambda X: (X[1]+X[2]+X[3]==x1+1)&(X[0]+X[1]+X[2]+X[3]==x2+1), XX))
r=r+abs(np.mean(P1)-np.mean(P2))
r/2

• Are the $X_i$'s independent? – Iosif Pinelis Jun 16 '20 at 21:35
• @Iosif Pinelis, thank you very much! Yes, the $X_i$'s are independent. – Jianrong Li Jun 17 '20 at 7:54

We shall assume that the $$X_i$$'s are independent. The problem can be restated as follows: show that for some $$h\in(0,1)$$, all natural $$n$$, and all subsets $$J$$ and $$K$$ of the set $$[n]:=\{1,\dots,n\}$$ we have $$\begin{equation*} S:=\sum_{x,y}|P(X_J=x,X_K=y)-P(X_J=x+1,X_K=y+1)|\le2-h, \tag{1} \end{equation*}$$ where $$X_J:=\sum_{i\in J}X_i$$ and the sum in (1) is over all all integers $$x,y$$. Write $$\begin{equation*} S\le T+U, \tag{2} \end{equation*}$$ where $$\begin{equation*} T:=\sum_{x,y}|P(X_J=x,X_K=y)-P(X_J=x+1,X_K=y)|, \end{equation*}$$ \begin{align*} U&:=\sum_{x,y}|P(X_J=x+1,X_K=y)-P(X_J=x+1,X_K=y+1)| \\ &=\sum_{x,y}|P(X_J=x,X_K=y)-P(X_J=x,X_K=y+1)|. \end{align*}
By the independence of the $$X_i$$'s, $$\begin{equation*} P(X_J=x,X_K=y)=\sum_z P(X_{J\cap K}=z)P(X_{J\setminus K}=x-z)P(X_{K\setminus J}=y-z). \end{equation*}$$ Hence, \begin{align*} T&\le\sum_zP(X_{J\cap K}=z)\,\sum_y P(X_{K\setminus J}=y-z) \\ &\times\sum_x|P(X_{J\setminus K}=x-z)-P(X_{J\setminus K}=x+1-z)| \\ &=\sum_x|P(X_{J\setminus K}=x)-P(X_{J\setminus K}=x+1)|=:D_{|J\setminus K|}, \end{align*} where $$|\cdot|$$ denotes the cardinality. Similarly, $$U\le D_{|K\setminus J|}$$, so that, by (2) $$\begin{equation*} S\le D_{|J\setminus K|}+D_{|K\setminus J|}. \tag{3} \end{equation*}$$ Note that $$D_0=1$$ and, by this answer, for $$k\ge1$$ we have \begin{align*} D_k=\frac1{2^k}\,\Big(2\binom k{m+1}-1\Big)\le\frac34, \end{align*} where $$m:=\lfloor (k-1)/2\rfloor$$. So, by (3), $$\begin{equation*} S\le 1+3/4=7/4 \end{equation*}$$ if $$J\ne K$$.
In the remaining case when $$J=K$$, $$\begin{equation*} S=\sum_x|P(X_J=x)-P(X_J=x+1)|=D_{|J|}\le1. \end{equation*}$$
Thus, in all cases (1) holds with $$h=2-\max(7/4,1)=1/4>0$$, as desired.
• thank you very much for your great answer! I am trying to understand every step of your proof. In the formula before (3), it is said that $\sum_z P(X_{J \cap K}=z) \sum_y P(X_{K\backslash J}=y-z)=1$. I am trying to understand this step. I think that $$\sum_z P(X_{J \cap K}=z) \sum_y P(X_{K\backslash J}=y-z) \\=\sum_z P(X_{J \cap K}=z) \sum_y P(X_{K\backslash J}=y) = \sum_{y,z} P(X_{J \cap K}=z) P(X_{K\backslash J}=y) \\=\sum_{y,z}P(X_{K}=y+z)=\sum_y P(X_{K}=y)=1$$. Is my understanding correct? I checked that when $k=2$, $D_k=3/4$. So maybe for $k \ge 1$, $D_k \ge 3/4$? – Jianrong Li Jun 17 '20 at 10:34
• sorry, I mean when $k \ge 1$, $D_k \le 3/4$. – Jianrong Li Jun 17 '20 at 15:16
• @JianrongLi : Oops! I did indeed miss $3/4$; this is now corrected -- thank you for pointing this out. As for your detalization of the multi-line display before (3), what I had in mind was something like this, but a bit simpler: just using the fact that $\sum\limits_t P(X_M=t)=1$. – Iosif Pinelis Jun 17 '20 at 15:58