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$ – Iosif Pinelis Jun 16 '20 at 21:35
  • $\begingroup$ @Iosif Pinelis, thank you very much! Yes, the $X_i$'s are independent. $\endgroup$ – Jianrong Li Jun 17 '20 at 7:54
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$ – Jianrong Li Jun 17 '20 at 10:34
  • $\begingroup$ sorry, I mean when $k \ge 1$, $D_k \le 3/4$. $\endgroup$ – Jianrong Li Jun 17 '20 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$ – Iosif Pinelis Jun 17 '20 at 15:58
  • $\begingroup$ thank you very much! $\endgroup$ – Jianrong Li Jun 17 '20 at 16:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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