0
$\begingroup$

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
$\endgroup$
2
  • $\begingroup$ Are the $X_i$'s independent? $\endgroup$ Jun 16, 2020 at 21:35
  • $\begingroup$ @Iosif Pinelis, thank you very much! Yes, the $X_i$'s are independent. $\endgroup$ Jun 17, 2020 at 7:54

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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$? $\endgroup$ Jun 17, 2020 at 10:34
  • $\begingroup$ sorry, I mean when $k \ge 1$, $D_k \le 3/4$. $\endgroup$ Jun 17, 2020 at 15:16
  • $\begingroup$ @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$. $\endgroup$ Jun 17, 2020 at 15:58
  • $\begingroup$ thank you very much! $\endgroup$ Jun 17, 2020 at 16:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.