# 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 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?

• Are your random variables positive? Commented Apr 22, 2022 at 13:21
• Yes, $X_1,X_2$ are both positive. Commented Apr 22, 2022 at 14:43

$$\newcommand{\de}{\delta}$$You have the bounds $$$$P(|X_i-m_i|\ge \de_i m_i]\le2e^{-\de_i^2 m_i/3}$$$$ for $$i=1,2$$ and $$\de_i>0$$, where $$$$m_i:=EX_i.$$$$ Clearly, these bounds are useful only if $$m_i>0$$ for $$i=1,2$$, which will be henceforth assumed. Assume also that $$0<\de_i<1$$ for $$i=1,2$$.
Then on the event \begin{aligned} A&:=\{|X_1-m_1|<\de_1 m_1,|X_1-m_1|<\de_2 m_2\} \\ &=\{m_1(1-\de_1) we have $$X_1>0$$ and $$X_2>0$$, which implies that $$$$Y = \frac{X_1-X_2}{X_1+X_2}$$$$ is increasing in $$X_1$$ and decreasing in $$X_2$$, so that the event
$$$$B:=\Big\{\frac{m_1(1-\de_1)-m_2(1+\de_2)}{m_1(1+\de_1)+m_2(1-\de_2)} occurs. That is, $$A\subseteq B$$ and hence $$1-P(B)\le1-P(A)$$.
So, by the union bound, we get the concentration result: $$$$1-P(B)\le 2e^{-\de_1^2 m_1/3}+2e^{-\de_2^2 m_2/3}.$$$$ One can now (quasi-)optimize the choices of $$\de_1$$ and $$\de_2$$, depending on one's objectives.
• Thanks for your answer! I can follow the line of thought, but I got confused at the final concentration result. Is there maybe a typo where you wrote $[\leq 1 - P(A)]$ Commented Apr 22, 2022 at 14:45
• @rusho : Putting $\le1-P(A)$ into brackets was intended as a comment. Since that may be confusing, I have now edited the answer accordingly. Commented Apr 22, 2022 at 15:59