Skip to main content
MathOverflow

Return to Question

I want a "left" tail bound
Source Link
mathjunge
mathjunge
  • 191
  • 8

Fix $p>0$ and define a recursive sequence of random variables with $X_1 =1$ and $$X_{k+1} = X_k + \text{Bin}(X_k,p).$$ Thus, $\mathbf E [ X_k ] = (1+p)^k$. I would like a rightleft tail bound. Perhaps, for some $a>0$ and $0 < \epsilon < p$, $$\mathbf P[X_k < (1+ p - \epsilon)^k ] \leq e^{-a k}.$$

Fix $p>0$ and define a recursive sequence of random variables with $X_1 =1$ and $$X_{k+1} = X_k + \text{Bin}(X_k,p).$$ Thus, $\mathbf E [ X_k ] = (1+p)^k$. I would like a right tail bound. Perhaps, for some $a>0$ and $0 < \epsilon < p$, $$\mathbf P[X_k < (1+ p - \epsilon)^k ] \leq e^{-a k}.$$

Fix $p>0$ and define a recursive sequence of random variables with $X_1 =1$ and $$X_{k+1} = X_k + \text{Bin}(X_k,p).$$ Thus, $\mathbf E [ X_k ] = (1+p)^k$. I would like a left tail bound. Perhaps, for some $a>0$ and $0 < \epsilon < p$, $$\mathbf P[X_k < (1+ p - \epsilon)^k ] \leq e^{-a k}.$$

Source Link
mathjunge
mathjunge
  • 191
  • 8

Recursive sequence of binomial random variables

Fix $p>0$ and define a recursive sequence of random variables with $X_1 =1$ and $$X_{k+1} = X_k + \text{Bin}(X_k,p).$$ Thus, $\mathbf E [ X_k ] = (1+p)^k$. I would like a right tail bound. Perhaps, for some $a>0$ and $0 < \epsilon < p$, $$\mathbf P[X_k < (1+ p - \epsilon)^k ] \leq e^{-a k}.$$