Skip to main content
MathOverflow

Return to Question

added 9 characters in body
Source Link
rusho
rusho
  • 33
  • 4

Suppose I have two random variables $X_1$ and $X_2$. $X_1,X_2$ are both sums of random variables, and I can find Chernoff bounds for both variables independently. That is to say, I have $$Pr[\mid X_i - \mathbb{E}X_i \mid \geq \delta \mathbb{E}X_i] \leq 2\exp(-\frac{\delta^2 \mathbb{E}X_i}{3}) $$ for both $i=1,2$.

Now, I have a new variable $$Y = \frac{X_1 - X_2}{X_1 + X_2}$$ I know how I can get concentration bounds using the union bound for both the numerator and denominator. But is there a way that I can get some kind of bound for the fraction itself? Here is what I attempted.

First, get the bounds for the numerator. Then holding the lower and upper bounds of the numerator constant, try to get concentration bounds for the (lower(or upper) bound/denominator random variable) term, i.e., get lower bounds for $\frac{LB(X_1-X_2)}{X_1+X_2}$, where LB is taking the LBlower bound we get from the numerators concentration bound. Then try to find probability and lower bound for this new $\frac{constant}{X_1+X_2}$ type term. Similarly try to find probability and upper bound using the numerator upper bound term. But the calculation got messy and I couldn't finish it.

Is there a method for solving problems like this?

Suppose I have two random variables $X_1$ and $X_2$. $X_1,X_2$ are both sums of random variables, and I can find Chernoff bounds for both variables independently. That is to say, I have $$Pr[\mid X_i - \mathbb{E}X_i \mid \geq \delta \mathbb{E}X_i] \leq 2\exp(-\frac{\delta^2 \mathbb{E}X_i}{3}) $$ for both $i=1,2$.

Now, I have a new variable $$Y = \frac{X_1 - X_2}{X_1 + X_2}$$ I know how I can get concentration bounds using the union bound for both the numerator and denominator. But is there a way that I can get some kind of bound for the fraction itself? Here is what I attempted.

First, get the bounds for the numerator. Then holding the lower and upper bounds of the numerator constant, try to get concentration bounds for the (lower(or upper) bound/denominator random variable) term, i.e., get lower bounds for $\frac{LB(X_1-X_2)}{X_1+X_2}$, where LB is taking the LB we get from the numerators concentration bound. Then try to find probability and lower bound for this new $\frac{constant}{X_1+X_2}$ type term. Similarly try to find probability and upper bound using the numerator upper bound term. But the calculation got messy and I couldn't finish it.

Is there a method for solving problems like this?

Suppose I have two random variables $X_1$ and $X_2$. $X_1,X_2$ are both sums of random variables, and I can find Chernoff bounds for both variables independently. That is to say, I have $$Pr[\mid X_i - \mathbb{E}X_i \mid \geq \delta \mathbb{E}X_i] \leq 2\exp(-\frac{\delta^2 \mathbb{E}X_i}{3}) $$ for both $i=1,2$.

Now, I have a new variable $$Y = \frac{X_1 - X_2}{X_1 + X_2}$$ I know how I can get concentration bounds using the union bound for both the numerator and denominator. But is there a way that I can get some kind of bound for the fraction itself? Here is what I attempted.

First, get the bounds for the numerator. Then holding the lower and upper bounds of the numerator constant, try to get concentration bounds for the (lower(or upper) bound/denominator random variable) term, i.e., get lower bounds for $\frac{LB(X_1-X_2)}{X_1+X_2}$, where LB is taking the lower bound we get from the numerators concentration bound. Then try to find probability and lower bound for this new $\frac{constant}{X_1+X_2}$ type term. Similarly try to find probability and upper bound using the numerator upper bound term. But the calculation got messy and I couldn't finish it.

Is there a method for solving problems like this?

Source Link
rusho
rusho
  • 33
  • 4

Chernoff style concentration bound for ratio of variables

Suppose I have two random variables $X_1$ and $X_2$. $X_1,X_2$ are both sums of random variables, and I can find Chernoff bounds for both variables independently. That is to say, I have $$Pr[\mid X_i - \mathbb{E}X_i \mid \geq \delta \mathbb{E}X_i] \leq 2\exp(-\frac{\delta^2 \mathbb{E}X_i}{3}) $$ for both $i=1,2$.

Now, I have a new variable $$Y = \frac{X_1 - X_2}{X_1 + X_2}$$ I know how I can get concentration bounds using the union bound for both the numerator and denominator. But is there a way that I can get some kind of bound for the fraction itself? Here is what I attempted.

First, get the bounds for the numerator. Then holding the lower and upper bounds of the numerator constant, try to get concentration bounds for the (lower(or upper) bound/denominator random variable) term, i.e., get lower bounds for $\frac{LB(X_1-X_2)}{X_1+X_2}$, where LB is taking the LB we get from the numerators concentration bound. Then try to find probability and lower bound for this new $\frac{constant}{X_1+X_2}$ type term. Similarly try to find probability and upper bound using the numerator upper bound term. But the calculation got messy and I couldn't finish it.

Is there a method for solving problems like this?