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?
Best Answer
$\newcommand{\de}{\delta}$You have the bounds \begin{equation} P(|X_i-m_i|\ge \de_i m_i]\le2e^{-\de_i^2 m_i/3} \end{equation} for $i=1,2$ and $\de_i>0$, where \begin{equation} m_i:=EX_i. \end{equation} 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{equation} \begin{aligned} A&:=\{|X_1-m_1|<\de_1 m_1,|X_1-m_1|<\de_2 m_2\} \\ &=\{m_1(1-\de_1)<X_1<m_1(1+\de_1),m_2(1-\de_2)<X_2<m_2(1+\de_2)\} \end{aligned} \end{equation} we have $X_1>0$ and $X_2>0$, which implies that \begin{equation} Y = \frac{X_1-X_2}{X_1+X_2} \end{equation} is increasing in $X_1$ and decreasing in $X_2$, so that the event
\begin{equation} B:=\Big\{\frac{m_1(1-\de_1)-m_2(1+\de_2)}{m_1(1+\de_1)+m_2(1-\de_2)} <Y<\frac{m_1(1+\de_1)-m_2(1-\de_2)}{m_1(1-\de_1)+m_2(1+\de_2)}\Big\} \end{equation} occurs. That is, $A\subseteq B$ and hence $1-P(B)\le1-P(A)$.
So, by the union bound, we get the concentration result: \begin{equation} 1-P(B)\le 2e^{-\de_1^2 m_1/3}+2e^{-\de_2^2 m_2/3}. \end{equation} One can now (quasi-)optimize the choices of $\de_1$ and $\de_2$, depending on one's objectives.