Estimate an expression about probability about Bernoulli random variables

Question

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

Answer 1

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.