Skip to main content
edited body
Source Link
Farzad
  • 197
  • 7

Hi everyone,

Note: This question is a general case and edited version of my previous question ``How to obtain tail bounds for a sum of dependent and bounded random variables?''.

I am looking for tail bounds (preferably exponential) for a linear combination of dependent and bounded random variables.

consider $$K_{ij}=\sum_{r=1}^N\sum_{c=1}^N W_{ir}C_{ij}W_{jc}$$$$K_{ij}=\sum_{r=1}^N\sum_{c=1}^N W_{ir}C_{rc}W_{jc}$$ where $i \neq j$, $W\in \{+1, -1\}$ and $W$ follows $\operatorname{Bernoulli}(0.5)$, and $C=\operatorname{Toeplitz}(1, \rho, \rho^2, \ldots, \rho^{N-1})$, $0 \leq \rho < 1$.

I will be to happy if you give me any pointer to how I can evaluate the moment generating function of $K_{ij}$ to have bound for $Pr\{K_{ij} \geq \epsilon\}\leq \min_s\exp(-s\epsilon)E[\exp(K_{ij}s)]$ based on chernoff bound.

For a hint I put the following case, that is in fact a special case of the above one. Consider $$K_{ij}=\sum_{r=1}^N\sum_{c=1}^N W_{ir}W_{jc}$$ where $i \neq j$, $W\in \{+1, -1\}$ and $W$ are i.i.d. random variables $\operatorname{Bernoulli}(0.5)$.

(Answer: As it is noted in Ori's comment, it can be considered as the multiplication of two independent Binomial random variables, i.e., $$K_{ij}=\left(\sum_{r=1}^N W_{ir}\right)\left(\sum_{c=1}^N W_{jc}\right)$$, then the moment generating function can be evaluated and then by using the Chernoff we can have a tail bound for $K_{ij}$.)

Thanks a lot in advance.

Hi everyone,

Note: This question is a general case and edited version of my previous question ``How to obtain tail bounds for a sum of dependent and bounded random variables?''.

I am looking for tail bounds (preferably exponential) for a linear combination of dependent and bounded random variables.

consider $$K_{ij}=\sum_{r=1}^N\sum_{c=1}^N W_{ir}C_{ij}W_{jc}$$ where $i \neq j$, $W\in \{+1, -1\}$ and $W$ follows $\operatorname{Bernoulli}(0.5)$, and $C=\operatorname{Toeplitz}(1, \rho, \rho^2, \ldots, \rho^{N-1})$, $0 \leq \rho < 1$.

I will be to happy if you give me any pointer to how I can evaluate the moment generating function of $K_{ij}$ to have bound for $Pr\{K_{ij} \geq \epsilon\}\leq \min_s\exp(-s\epsilon)E[\exp(K_{ij}s)]$ based on chernoff bound.

For a hint I put the following case, that is in fact a special case of the above one. Consider $$K_{ij}=\sum_{r=1}^N\sum_{c=1}^N W_{ir}W_{jc}$$ where $i \neq j$, $W\in \{+1, -1\}$ and $W$ are i.i.d. random variables $\operatorname{Bernoulli}(0.5)$.

(Answer: As it is noted in Ori's comment, it can be considered as the multiplication of two independent Binomial random variables, i.e., $$K_{ij}=\left(\sum_{r=1}^N W_{ir}\right)\left(\sum_{c=1}^N W_{jc}\right)$$, then the moment generating function can be evaluated and then by using the Chernoff we can have a tail bound for $K_{ij}$.)

Thanks a lot in advance.

Hi everyone,

Note: This question is a general case and edited version of my previous question ``How to obtain tail bounds for a sum of dependent and bounded random variables?''.

I am looking for tail bounds (preferably exponential) for a linear combination of dependent and bounded random variables.

consider $$K_{ij}=\sum_{r=1}^N\sum_{c=1}^N W_{ir}C_{rc}W_{jc}$$ where $i \neq j$, $W\in \{+1, -1\}$ and $W$ follows $\operatorname{Bernoulli}(0.5)$, and $C=\operatorname{Toeplitz}(1, \rho, \rho^2, \ldots, \rho^{N-1})$, $0 \leq \rho < 1$.

I will be to happy if you give me any pointer to how I can evaluate the moment generating function of $K_{ij}$ to have bound for $Pr\{K_{ij} \geq \epsilon\}\leq \min_s\exp(-s\epsilon)E[\exp(K_{ij}s)]$ based on chernoff bound.

For a hint I put the following case, that is in fact a special case of the above one. Consider $$K_{ij}=\sum_{r=1}^N\sum_{c=1}^N W_{ir}W_{jc}$$ where $i \neq j$, $W\in \{+1, -1\}$ and $W$ are i.i.d. random variables $\operatorname{Bernoulli}(0.5)$.

(Answer: As it is noted in Ori's comment, it can be considered as the multiplication of two independent Binomial random variables, i.e., $$K_{ij}=\left(\sum_{r=1}^N W_{ir}\right)\left(\sum_{c=1}^N W_{jc}\right)$$, then the moment generating function can be evaluated and then by using the Chernoff we can have a tail bound for $K_{ij}$.)

Thanks a lot in advance.

added 289 characters in body
Source Link
Farzad
  • 197
  • 7

Hi everyone,

Note: This question is a general case and edited version of my previous question ``How to obtain tail bounds for a sum of dependent and bounded random variables?''.

I am looking for tail bounds (preferably exponential) for a linear combination of dependent and bounded random variables.

consider $$K_{ij}=\sum_{r=1}^N\sum_{c=1}^N W_{ir}C_{ij}W_{jc}$$ where $i \neq j$, $W\in \{+1, -1\}$ and $W$ follows $\operatorname{Bernoulli}(0.5)$, and $C=\operatorname{Toeplitz}(1, \rho, \rho^2, \ldots, \rho^{N-1})$, $0 \leq \rho < 1$.

I will be to happy if you give me any pointer to how I can evaluate the moment generating function of $K_{ij}$ to have bound for $Pr\{K_{ij} \geq \epsilon\}\leq \min_s\exp(-s\epsilon)E[\exp(K_{ij}s)]$ based on chernoff bound.

For a hint I put the following case, that is in fact a special case of the above one. Consider $$K_{ij}=\sum_{r=1}^N\sum_{c=1}^N W_{ir}W_{jc}$$ where $i \neq j$, $W\in \{+1, -1\}$ and $W$ are i.i.d. random variables $\operatorname{Bernoulli}(0.5)$.

(Answer: As it is noted in Ori's comment, it can be considered as the multiplication of two independent Binomial random variables, i.e., $$\left(K_{ij}=\sum_{r=1}^N W_{ir}\right)\left(\sum_{c=1}^N W_{jc}\right)$$$$K_{ij}=\left(\sum_{r=1}^N W_{ir}\right)\left(\sum_{c=1}^N W_{jc}\right)$$, then the moment generating function can be evaluated and then by using the Chernoff we can have a a tail bound for $K_{ij}$.)

Thanks a lot in advance.

Hi everyone,

I am looking for tail bounds (preferably exponential) for a linear combination of dependent and bounded random variables.

consider $$K_{ij}=\sum_{r=1}^N\sum_{c=1}^N W_{ir}C_{ij}W_{jc}$$ where $i \neq j$, $W\in \{+1, -1\}$ and $W$ follows $\operatorname{Bernoulli}(0.5)$, and $C=\operatorname{Toeplitz}(1, \rho, \rho^2, \ldots, \rho^{N-1})$, $0 \leq \rho < 1$.

I will be to happy if you give me any pointer to how I can evaluate the moment generating function of $K_{ij}$.

For a hint I put the following case, that is in fact a special case the above one. Consider $$K_{ij}=\sum_{r=1}^N\sum_{c=1}^N W_{ir}W_{jc}$$ where $i \neq j$, $W\in \{+1, -1\}$ and $W$ are i.i.d. random variables $\operatorname{Bernoulli}(0.5)$.

(Answer: As it is noted in Ori's comment, it can be considered as the multiplication of two independent Binomial random variables, i.e., $$\left(K_{ij}=\sum_{r=1}^N W_{ir}\right)\left(\sum_{c=1}^N W_{jc}\right)$$, then the moment generating function can be evaluated and then by using the Chernoff we can have a a tail bound for $K_{ij}$.)

Thanks a lot in advance.

Hi everyone,

Note: This question is a general case and edited version of my previous question ``How to obtain tail bounds for a sum of dependent and bounded random variables?''.

I am looking for tail bounds (preferably exponential) for a linear combination of dependent and bounded random variables.

consider $$K_{ij}=\sum_{r=1}^N\sum_{c=1}^N W_{ir}C_{ij}W_{jc}$$ where $i \neq j$, $W\in \{+1, -1\}$ and $W$ follows $\operatorname{Bernoulli}(0.5)$, and $C=\operatorname{Toeplitz}(1, \rho, \rho^2, \ldots, \rho^{N-1})$, $0 \leq \rho < 1$.

I will be to happy if you give me any pointer to how I can evaluate the moment generating function of $K_{ij}$ to have bound for $Pr\{K_{ij} \geq \epsilon\}\leq \min_s\exp(-s\epsilon)E[\exp(K_{ij}s)]$ based on chernoff bound.

For a hint I put the following case, that is in fact a special case of the above one. Consider $$K_{ij}=\sum_{r=1}^N\sum_{c=1}^N W_{ir}W_{jc}$$ where $i \neq j$, $W\in \{+1, -1\}$ and $W$ are i.i.d. random variables $\operatorname{Bernoulli}(0.5)$.

(Answer: As it is noted in Ori's comment, it can be considered as the multiplication of two independent Binomial random variables, i.e., $$K_{ij}=\left(\sum_{r=1}^N W_{ir}\right)\left(\sum_{c=1}^N W_{jc}\right)$$, then the moment generating function can be evaluated and then by using the Chernoff we can have a tail bound for $K_{ij}$.)

Thanks a lot in advance.

added 3 characters in body
Source Link
Farzad
  • 197
  • 7

Hi everyone,

I am looking for tail bounds (preferably exponential) for the suma linear combination of dependent and bounded random variables.

First case, consider $$K_{ij}=\sum_{r=1}^N\sum_{c=1}^N W_{ir}C_{ij}W_{jc}$$ where $i \neq j$, $W\in \{+1, -1\}$ and $W$ follows $\operatorname{Bernoulli}(0.5)$, and $C=\operatorname{Toeplitz}(1, \rho, \rho^2, \ldots, \rho^{N-1})$, $0 \leq \rho < 1$.

I will be to happy if you give me any pointer to how I can evaluate the moment generating function of $K_{ij}$.

For a hint I put the following case, that is in fact a special case the above one. Consider $$K_{ij}=\sum_{r=1}^N\sum_{c=1}^N W_{ir}W_{jc}$$ where $i \neq j$, $W\in \{+1, -1\}$ and $W$ are i.i.d. random variables $\operatorname{Bernoulli}(0.5)$. How can I obtain an exponential bound over $Pr[K_{ij} \geq \epsilon] \leq \exp(?)$ where $\epsilon$ is a positive value.

(Added in the edited version: Answer: As it is noted in Ori's comment, it can be considered as the multiplication of two independent Binomial random variables, i.e., $$\left(K_{ij}=\sum_{r=1}^N W_{ir}\right)\left(\sum_{c=1}^N W_{jc}\right)$$, then Ithe moment generating function can usebe evaluated and then by using the Chernoff bound towe can have a a tail bound for $K_{ij}$.)

(Added in the edited version:) Second case, consider $$K_{ij}=\sum_{r=1}^N\sum_{c=1}^N W_{ir}C_{ij}W_{jc}$$ where $i \neq j$, $W\in \{+1, -1\}$ and $W$ follows $\operatorname{Bernoulli}(0.5)$, and $C=\operatorname{Toeplitz}(1, \rho, \rho^2, \ldots, \rho^{N-1})$, $0 \leq \rho < 1$.

I will be to happy if you give me any pointer to how I can evaluate the moment generating function of $K_{ij}$ in the second case.

Thanks a lot in advance.

Hi everyone,

I am looking for tail bounds (preferably exponential) for the sum of dependent and bounded random variables.

First case, consider $$K_{ij}=\sum_{r=1}^N\sum_{c=1}^N W_{ir}W_{jc}$$ where $i \neq j$, $W\in \{+1, -1\}$ and $W$ are i.i.d. random variables $\operatorname{Bernoulli}(0.5)$. How can I obtain an exponential bound over $Pr[K_{ij} \geq \epsilon] \leq \exp(?)$ where $\epsilon$ is a positive value.

(Added in the edited version: Answer: As it is noted in Ori's comment, it can be considered as the multiplication of two independent Binomial random variables, then I can use the Chernoff bound to have a tail bound for $K_{ij}$.)

(Added in the edited version:) Second case, consider $$K_{ij}=\sum_{r=1}^N\sum_{c=1}^N W_{ir}C_{ij}W_{jc}$$ where $i \neq j$, $W\in \{+1, -1\}$ and $W$ follows $\operatorname{Bernoulli}(0.5)$, and $C=\operatorname{Toeplitz}(1, \rho, \rho^2, \ldots, \rho^{N-1})$, $0 \leq \rho < 1$.

I will be to happy if you give me any pointer to how I can evaluate the moment generating function of $K_{ij}$ in the second case.

Thanks a lot in advance.

Hi everyone,

I am looking for tail bounds (preferably exponential) for a linear combination of dependent and bounded random variables.

consider $$K_{ij}=\sum_{r=1}^N\sum_{c=1}^N W_{ir}C_{ij}W_{jc}$$ where $i \neq j$, $W\in \{+1, -1\}$ and $W$ follows $\operatorname{Bernoulli}(0.5)$, and $C=\operatorname{Toeplitz}(1, \rho, \rho^2, \ldots, \rho^{N-1})$, $0 \leq \rho < 1$.

I will be to happy if you give me any pointer to how I can evaluate the moment generating function of $K_{ij}$.

For a hint I put the following case, that is in fact a special case the above one. Consider $$K_{ij}=\sum_{r=1}^N\sum_{c=1}^N W_{ir}W_{jc}$$ where $i \neq j$, $W\in \{+1, -1\}$ and $W$ are i.i.d. random variables $\operatorname{Bernoulli}(0.5)$.

(Answer: As it is noted in Ori's comment, it can be considered as the multiplication of two independent Binomial random variables, i.e., $$\left(K_{ij}=\sum_{r=1}^N W_{ir}\right)\left(\sum_{c=1}^N W_{jc}\right)$$, then the moment generating function can be evaluated and then by using the Chernoff we can have a a tail bound for $K_{ij}$.)

Thanks a lot in advance.

edited title
Link
Farzad
  • 197
  • 7
Loading
added 691 characters in body
Source Link
Farzad
  • 197
  • 7
Loading
added 5 characters in body
Source Link
Farzad
  • 197
  • 7
Loading
added 4 characters in body
Source Link
Farzad
  • 197
  • 7
Loading
added 29 characters in body
Source Link
Farzad
  • 197
  • 7
Loading
Source Link
Farzad
  • 197
  • 7
Loading