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

  • $\begingroup$ Seems to me like a nice question, what is the context? $\endgroup$ – Johan Wästlund Jul 8 '15 at 6:34
  • $\begingroup$ Your "perhaps" is a left tail bound, but you ask for a right tail bound? $\endgroup$ – Brendan McKay Jul 8 '15 at 12:14
  • $\begingroup$ The right tail bounds seem much easier than the left tail bounds. For example, Markov's inequality says $P[X_k > (1+p+\epsilon)^k] \le (\frac{1+p}{1+p+\epsilon})^k$. $\endgroup$ – Douglas Zare Jul 8 '15 at 12:41
  • $\begingroup$ My mistake. I'm interested in a left tail bound. Azuma's or Chernoff's inequalities seem like natural tools, but I'm, so far, unsuccessful appyling them. $\endgroup$ – mathjunge Jul 8 '15 at 15:31
  • 1
    $\begingroup$ This is a toy version of a more difficult problem. It's coming up in the context of the Frog Model. Fix an increasing sequence $a_k$. Add $k$ balls uniformly randomly to $a_k$ bins. Letting $e_k$ be the number of non-empty bins, we then add $k+e_k$ balls to $a_{k+1}$ (new/fresh) bins and continue the algorithm. $\endgroup$ – mathjunge Jul 8 '15 at 15:34

I claim is that $X_k$ stochastically dominates the following process, $W_k$. To make things a bit simpler, assume $X_1 = 2 = W_1$. (This is harmless, since we can just wait some geometric time until $X_{k}=2$ then start the process.) Let $$q = \inf_{k \geq 2} \{\mathbf{P}[\text{Bin}(k,p) > pk]\}.$$ Since this converges as $k \to \infty$ (by normal approximation) we know that $q>0$. Now, define $W_1 = 2$ and

$$W_{k+1} = W_k + (1/2)W_k \text{Ber(q)}.$$

Essentially the $W_k$ increase whenever $X_k$ increases by at least $X_k/2$ and otherwise does not change. One could then write a formal coupling, so that $W_k \preceq X_k$. The $W_k$ are much simpler to analyze. Each successful Ber($q$) trial results in an increase by a factor of $(1+p)$. So we can write

$$W_k = 2*(1+p)^{ \text{Bin}{(k,q)}}.$$

Let $q_k = \mathbf P[ \text{Bin}(k,q) \leq kq/2]$. By Chernoff, $q_k \leq e^{-a k}$ for some $a>0$. It follows that $$\mathbf P [ W_k \leq ( (1+p)^{q/2})^k]\leq q_k \leq e^{-a k}. $$ As $W_k \preceq X_k$ we take $\epsilon = (1+p)^{q/2} -1$ and have $$\mathbf P[X_k \leq (1 + \epsilon)^k ] \leq e^{-ak}.$$

| cite | improve this answer | |
  • $\begingroup$ Good point. Lets take $q = \inf_{k \geq 2} \{ \mathbf P [ \text{Bin}(k,p) > pk] \}$ and then obtain growth on the order of $(1+p)^\text{Bin(k,q)}.$ $\endgroup$ – Matthew Junge Dec 7 '15 at 21:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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