2
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ Are your random variables positive? $\endgroup$
    – fedja
    Apr 22, 2022 at 13:21
  • $\begingroup$ Yes, $X_1,X_2$ are both positive. $\endgroup$
    – rusho
    Apr 22, 2022 at 14:43

1 Answer 1

1
$\begingroup$

$\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.

$\endgroup$
4
  • $\begingroup$ 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)]$ $\endgroup$
    – rusho
    Apr 22, 2022 at 14:45
  • $\begingroup$ @rusho : Putting $\le1-P(A)$ into brackets was intended as a comment. Since that may be confusing, I have now edited the answer accordingly. $\endgroup$ Apr 22, 2022 at 15:59
  • $\begingroup$ Thank you! That definitely clears it up. And I feel like I'll be able to calculate bounds for this type of random variables now. $\endgroup$
    – rusho
    Apr 22, 2022 at 16:20
  • $\begingroup$ @rusho : I am glad this was of help. $\endgroup$ Apr 22, 2022 at 16:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.