# 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 left tail bound. Perhaps, for some $a>0$ and $0 < \epsilon < p$, $$\mathbf P[X_k < (1+ p - \epsilon)^k ] \leq e^{-a k}.$$

• Seems to me like a nice question, what is the context? – Johan Wästlund Jul 8 '15 at 6:34
• Your "perhaps" is a left tail bound, but you ask for a right tail bound? – Brendan McKay Jul 8 '15 at 12:14
• 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$. – Douglas Zare Jul 8 '15 at 12:41
• 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. – mathjunge Jul 8 '15 at 15:31
• 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. – 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}.$$
• 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)}.$ – Matthew Junge Dec 7 '15 at 21:33