Return to Question

Fix $m$ arbitrary values $x_1, x_2, ..., x_m$ in $[0,1]$, and an integer $n$. Obtain $n$-set $S$ by drawing $n \le m$ times randomly without replacement from $\{1,2,..,m\}$. Define r.v. $X = \sum_{i \in S} x_i$ and $\mu=E[X]$.

Is it the case that

 

$$\Pr[X \ge \mu + \epsilon\mu] ~=~ \exp(- \Omega(\epsilon^2 \mu))~?~~~~~(1)$$

Following the hint here, we can use McDiarmid's inequality to prove the weaker bound

$$\Pr[X \ge \mu + \epsilon n] ~=~ \exp(-\Omega(\epsilon^2 n)),~~~~~(2)$$

but this bound depends on $n$ and is weaker when $\mu \ll n$.

A related but different question was asked here.

[EDIT: My original question asked first if bound (1) holds in all applications of of McDiarmid's inequality where $X=f(y_1,..,y_n)$ is a function of $n$ independent random variables, and $f$ changes by at most 1 when any $x_i$ is changed. For the record, the answer to that seems to be NO. For a counter-example, take $$\textstyle X = f(x_1, x_2, \ldots, x_n) = \big|k \,-\, \big((\sum_{i=1}^n x_i) \bmod 2k\big)\big| $$ where each $x_i$ is i.i.d. uniformly over $[0,1]$ and, say, $k=\lceil \sqrt n\rceil$. Then $X$ is roughly uniformly distributed over $[0,k]$, so $\mu \approx k/2$, and $\Pr[X \ge \mu + \mu/2] = \Omega(1) \ne \exp(-\Omega(\mu))$.]

Fix $m$ arbitrary values $x_1, x_2, ..., x_m$ in $[0,1]$, and an integer $n$. Obtain $n$-set $S$ by drawing $n \le m$ times randomly without replacement from $\{1,2,..,m\}$. Define r.v. $X = \sum_{i \in S} x_i$ and $\mu=E[X]$.

Is it the case that

$$\Pr[X \ge \mu + \epsilon\mu] ~=~ \exp(- \Omega(\epsilon^2 \mu))~?~~~~~(1)$$

Following the hint here, we can use McDiarmid's inequality to prove the weaker bound

$$\Pr[X \ge \mu + \epsilon n] ~=~ \exp(-\Omega(\epsilon^2 n)),~~~~~(2)$$

but this bound depends on $n$ and is weaker when $\mu \ll n$.

A related but different question was asked here.

[EDIT: My original question asked first if bound (1) holds in all applications of of McDiarmid's inequality where $X=f(y_1,..,y_n)$ is a function of $n$ independent random variables, and $f$ changes by at most 1 when any $x_i$ is changed. For the record, the answer to that seems to be NO. For a counter-example, take $$\textstyle X = f(x_1, x_2, \ldots, x_n) = \big|k \,-\, \big((\sum_{i=1}^n x_i) \bmod 2k\big)\big| $$ where each $x_i$ is i.i.d. uniformly over $[0,1]$ and, say, $k=\lceil \sqrt n\rceil$. Then $X$ is roughly uniformly distributed over $[0,k]$, so $\mu \approx k/2$, and $\Pr[X \ge \mu + \mu/2] = \Omega(1) \ne \exp(-\Omega(\mu))$.]

Fix $m$ arbitrary values $x_1, x_2, ..., x_m$ in $[0,1]$, and an integer $n$. Obtain $n$-set $S$ by drawing $n$ times randomly without replacement from $\{1,2,..,m\}$. Define r.v. $X = \sum_{i \in S} x_i$ and $\mu=E[X]$.

Is it the case that

$$\Pr[X \ge \mu + \epsilon\mu] ~=~ \exp(- \Omega(\epsilon^2 \mu))~?~~~~~(1)$$

Following the hint here, we can use McDiarmid's inequality to prove the weaker bound

$$\Pr[X \ge \mu + \epsilon n] ~=~ \exp(-\Omega(\epsilon^2 n)).~~~~~(2)$$

But this bound depends on $n$ and is weaker when $\mu \ll n$.

A related but different question was asked here.

[EDIT: My original question asked first if bound (1) holds in all applications of of McDiarmid's inequality where $X=f(y_1,..,y_n)$ is a function of $n$ independent random variables, and $f$ changes by at most 1 when any $x_i$ is changed. For the record, the answer to that seems to be NO. For a counter-example, take $$\textstyle X = f(x_1, x_2, \ldots, x_n) = \big|k \,-\, (\sum_{i=1}^n x_i) \bmod 2k\big| $$ where each $x_i$ is i.i.d. uniformly over $[0,1]$ and, say, $k=\lceil \sqrt n\rceil$. Then $X$ is roughly uniformly distributed over $[0,k]$, so $\mu \approx k/2$, and $\Pr[X \ge \mu + \mu/2] = \Omega(1) \ne \exp(\Omega(\mu))$.]

Fix $m$ arbitrary values $x_1, x_2, ..., x_m$ in $[0,1]$, and an integer $n$. Obtain $n$-set $S$ by drawing $n \le m$ times randomly without replacement from $\{1,2,..,m\}$. Define r.v. $X = \sum_{i \in S} x_i$ and $\mu=E[X]$.

Is it the case that

$$\Pr[X \ge \mu + \epsilon\mu] ~=~ \exp(- \Omega(\epsilon^2 \mu))~?~~~~~(1)$$

Following the hint here, we can use McDiarmid's inequality to prove the weaker bound

$$\Pr[X \ge \mu + \epsilon n] ~=~ \exp(-\Omega(\epsilon^2 n)),~~~~~(2)$$

but this bound depends on $n$ and is weaker when $\mu \ll n$.

A related but different question was asked here.

[EDIT: My original question asked first if bound (1) holds in all applications of of McDiarmid's inequality where $X=f(y_1,..,y_n)$ is a function of $n$ independent random variables, and $f$ changes by at most 1 when any $x_i$ is changed. For the record, the answer to that seems to be NO. For a counter-example, take $$\textstyle X = f(x_1, x_2, \ldots, x_n) = \big|k \,-\, \big((\sum_{i=1}^n x_i) \bmod 2k\big)\big| $$ where each $x_i$ is i.i.d. uniformly over $[0,1]$ and, say, $k=\lceil \sqrt n\rceil$. Then $X$ is roughly uniformly distributed over $[0,k]$, so $\mu \approx k/2$, and $\Pr[X \ge \mu + \mu/2] = \Omega(1) \ne \exp(-\Omega(\mu))$.]

Fix $m$ arbitrary values $x_1, x_2, ..., x_m$ in $[0,1]$, and an integer $n$. Obtain $n$-set $S$ by drawing $n$ times randomly without replacement from $\{1,2,..,m\}$. Define r.v. $X = \sum_{i \in S} x_i$ and $\mu=E[X]$.

Is it the case that

$$\Pr[X \ge \mu + \epsilon\mu] ~=~ \exp(- \Omega(\epsilon^2 \mu))~?~~~~~(1)$$

Following the hint here, we can use McDiarmid's inequality to prove the weaker bound

$$\Pr[X \ge \mu + \epsilon n] ~=~ \exp(-\Omega(\epsilon^2 n)).~~~~~(2)$$

But this bound depends on $n$ and is weaker when $\mu \ll n$.

A related but different question was asked here.

[EDIT: My original question asked if bound (1) holds in all applications of of McDiarmid's inequality where $X=f(y_1,..,y_n)$ is a function of $n$ independent random variables, and $f$ changes by at most 1 when any $x_i$ is changed. For the record, the answer to that seems to be NO. For a counter-example, take $$\textstyle X = f(x_1, x_2, \ldots, x_n) = \big|k \,-\, (\sum_{i=1}^n x_i) \bmod 2k\big| $$ where each $x_i$ is i.i.d. uniformly over $[0,1]$ and, say, $k=\lceil \sqrt n\rceil$. Then $X$ is roughly uniformly distributed over $[0,k]$, so $\mu \approx k/2$, and $\Pr[X \ge \mu + \mu/2] = \Omega(1) \ne \exp(\Omega(\mu))$.]

Fix $m$ arbitrary values $x_1, x_2, ..., x_m$ in $[0,1]$, and an integer $n$. Obtain $n$-set $S$ by drawing $n$ times randomly without replacement from $\{1,2,..,m\}$. Define r.v. $X = \sum_{i \in S} x_i$ and $\mu=E[X]$.

Is it the case that

$$\Pr[X \ge \mu + \epsilon\mu] ~=~ \exp(- \Omega(\epsilon^2 \mu))~?~~~~~(1)$$

Following the hint here, we can use McDiarmid's inequality to prove the weaker bound

$$\Pr[X \ge \mu + \epsilon n] ~=~ \exp(-\Omega(\epsilon^2 n)).~~~~~(2)$$

But this bound depends on $n$ and is weaker when $\mu \ll n$.

A related but different question was asked here.

[EDIT: My original question asked first if bound (1) holds in all applications of of McDiarmid's inequality where $X=f(y_1,..,y_n)$ is a function of $n$ independent random variables, and $f$ changes by at most 1 when any $x_i$ is changed. For the record, the answer to that seems to be NO. For a counter-example, take $$\textstyle X = f(x_1, x_2, \ldots, x_n) = \big|k \,-\, (\sum_{i=1}^n x_i) \bmod 2k\big| $$ where each $x_i$ is i.i.d. uniformly over $[0,1]$ and, say, $k=\lceil \sqrt n\rceil$. Then $X$ is roughly uniformly distributed over $[0,k]$, so $\mu \approx k/2$, and $\Pr[X \ge \mu + \mu/2] = \Omega(1) \ne \exp(\Omega(\mu))$.]