Skip to main content
deleted 2 characters in body
Source Link
Iosif Pinelis
  • 127.8k
  • 8
  • 107
  • 229

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\frac58, \end{align*}\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+5/8=13/8 \end{equation*}\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(13/8,1)=3/8>0$$h=2-\max(7/4,1)=1/4>0$, as desired.

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\frac58, \end{align*} where $m:=\lfloor (k-1)/2\rfloor$. So, by (3), \begin{equation*} S\le 1+5/8=13/8 \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(13/8,1)=3/8>0$, as desired.

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.

deleted 42 characters in body
Source Link
Iosif Pinelis
  • 127.8k
  • 8
  • 107
  • 229

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,K$$J$ and $K$ of the set $[n]:=\{1,\dots,n\}$ such that $$J\cup K\ne\emptyset$$ 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\frac58, \end{align*} where $m:=\lfloor (k-1)/2\rfloor$. So, by (3), \begin{equation*} S\le 1+5/8=13/8 \end{equation*} if $J\ne K$.

In the remaining case when $J=K\ne\emptyset$$J=K$, \begin{equation*} S=\sum_x|P(X_J=x)-P(X_J=x+1)|=D_{|J|}\le5/8. \end{equation*}\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[13/8,5/8]=3/8>0$$h=2-\max(13/8,1)=3/8>0$, as desired.

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,K$ of $[n]:=\{1,\dots,n\}$ such that $$J\cup K\ne\emptyset$$ 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\frac58, \end{align*} where $m:=\lfloor (k-1)/2\rfloor$. So, by (3), \begin{equation*} S\le 1+5/8=13/8 \end{equation*} if $J\ne K$.

In the remaining case when $J=K\ne\emptyset$, \begin{equation*} S=\sum_x|P(X_J=x)-P(X_J=x+1)|=D_{|J|}\le5/8. \end{equation*}

Thus, in all cases (1) holds with $h=2-\max[13/8,5/8]=3/8>0$, as desired.

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\frac58, \end{align*} where $m:=\lfloor (k-1)/2\rfloor$. So, by (3), \begin{equation*} S\le 1+5/8=13/8 \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(13/8,1)=3/8>0$, as desired.

Source Link
Iosif Pinelis
  • 127.8k
  • 8
  • 107
  • 229

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,K$ of $[n]:=\{1,\dots,n\}$ such that $$J\cup K\ne\emptyset$$ 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\frac58, \end{align*} where $m:=\lfloor (k-1)/2\rfloor$. So, by (3), \begin{equation*} S\le 1+5/8=13/8 \end{equation*} if $J\ne K$.

In the remaining case when $J=K\ne\emptyset$, \begin{equation*} S=\sum_x|P(X_J=x)-P(X_J=x+1)|=D_{|J|}\le5/8. \end{equation*}

Thus, in all cases (1) holds with $h=2-\max[13/8,5/8]=3/8>0$, as desired.