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

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