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}.$$
5
-
$\begingroup$ Seems to me like a nice question, what is the context? $\endgroup$– Johan WästlundCommented Jul 8, 2015 at 6:34
-
$\begingroup$ Your "perhaps" is a left tail bound, but you ask for a right tail bound? $\endgroup$– Brendan McKayCommented Jul 8, 2015 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 ZareCommented Jul 8, 2015 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$– mathjungeCommented Jul 8, 2015 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$– mathjungeCommented Jul 8, 2015 at 15:34
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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$ Commented Dec 7, 2015 at 21:33