Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

My problem is as follows:

I have two biased coins with probabilities $p_1$ and $p_2$ of landing heads. I start with coin 1 and toss it until it lands heads. Then I swap to coin 2 and toss until it lands heads. I then repeat the procedure until I have tossed $n$ times.

$X_n$ is the random variable which counts the number of heads in the process. My objective is to show that with probability $1-e^{-\Omega(n)}$ $X_n$ will be in the interval $[(1-\varepsilon)\mathbb{E}[X_n], (1+\varepsilon)\mathbb{E}[X_n]]$ for a fixed $\varepsilon>0$.

I have observed that if $p_1<p_2$ I know that $np_1\leq\mathbb{E}[X_n]\leq np_2$ so if I can somehow use Chernoff's or Azuma's inequality I don't need to calculate the expectation of $\mathbb{E}[X_n]$. I have tried looking at this problem with Markov chains but I haven't been successful there. I have also observed that for each $n$ I can define new random variables $Y_{k,n}$ where I throw coin 1 $k$ times and coin 2 $n-k$ times and let $Y_{k,n}$ denote the number of heads I got. I then know that for each $n$ there exists a unique $k$ such that $\mathbb{E}[Y_{k,n}]\leq \mathbb{E}[X_n] < \mathbb{E}[Y_{k+1,n}]$. I can't take that approach further though because I can't find suitable bounds for the variance of $X_n$

I'm not asking you to spoil the problem for me. I'm merely asking if someone could push me in the right direction.

share|improve this question

1 Answer 1

up vote 3 down vote accepted

Let us go for hints then. A crucial tool is $Y_n$ the number of tosses between the $(n-1)$th head and the $n$th head of coin $2$. Then $(Y_n)_{n\geqslant1}$ is an i.i.d. sequence and one can easily determine its distribution. For every positive $n$, let $S_n=\sum\limits_{k=1}^nY_k$.

Now, $[X_n\geqslant2k]=[S_k\leqslant n]$ hence, to evaluate $\mathrm P(X_n\geqslant(1+\varepsilon)\mathrm E(X_n))$, one can choose some $k$ depending on $n$ such that $2k\leqslant (1+\varepsilon)\mathrm E(X_n)$ and use the upper bound $$ \mathrm P(X_n\geqslant(1+\varepsilon)\mathrm E(X_n))\leqslant\mathrm P(S_k\leqslant n). $$ Likewise, to evaluate $\mathrm P(X_n\leqslant(1-\varepsilon)\mathrm E(X_n))$, one can choose some $\ell$ depending on $n$ such that $2\ell\geqslant (1-\varepsilon)\mathrm E(X_n)$ and use the upper bound $$ \mathrm P(X_n\leqslant(1-\varepsilon)\mathrm E(X_n))\leqslant\mathrm P(S_\ell\geqslant n). $$ So one must estimate the probability of these $S_k$ and $S_\ell$ events. This is the realm of large deviations theory but a simple version will be enough for us. Assume for example one wants to bound $$ A=\mathrm P(S_k\leqslant n). $$ Note that for every nonnegative $t$, $[S_k\leqslant n]=[\mathrm e^{-tS_k}\geqslant\mathrm e^{-tn}]$. This remark is at the basis of the so called Chernoff's bounds, in our case, $$ A=\mathrm P(\mathrm e^{-tS_k}\geqslant\mathrm e^{-tn})\leqslant\mathrm e^{tn}\mathrm E(\mathrm e^{-tS_k})=\mathrm e^{tn}\mathrm E(\mathrm e^{-tY_1})^k. $$ Assume for a moment that $k=\alpha n+o(n)$ when $n\to\infty$, then $A\leqslant\mathrm e^{-\Omega(n)}$ as soon as there exists a nonnegative $t$ such that $$ \mathrm e^{t}\,\mathrm E(\mathrm e^{-tY_1})^\alpha \lt1. $$ When $t\to0$, the LHS of this inequality is $1+t-\alpha t\mathrm E(Y_1)+o(t)$ hence such a parameter $t$ exists as soon as $1-\alpha \mathrm E(Y_1)\lt0$. You know the value of $\mathrm E(Y_1)$ and the only condition on $\alpha $ is $$ 2\alpha n+o(n)\leqslant (1+\varepsilon)\mathrm E(X_n), $$ hence the proof that $A\leqslant\mathrm e^{-\Omega(n)}$ is complete if $$ (1+\varepsilon)\cdot\mathrm E(Y_1)\cdot\xi\gt2\quad \mbox{with}\quad \xi=\lim\limits_{n\to\infty}\frac{\mathrm E(X_n)}{n}. $$ As you probably already guessed, it happens that $$ \mathrm E(Y_1)\cdot\xi=2, $$ hence this strategy succeeds for every positive $\varepsilon$. Likewise for $B=\mathrm P(S_\ell\geqslant n)$.

The relation $\mathrm E(Y_1)\cdot\xi=2$ is standard renewal theory, but let me finish by explaining the reason why it holds. In the long run, by the most classical version of the law of large numbers, it takes about $n=\mathrm E(Y_1)\cdot N$ tosses for $X$ to increase of $2N$ units, that is, $X_n\approx 2N\approx 2n/\mathrm E(Y_1)$. Since $X_n\approx\mathrm E(X_n)$, this yields $\xi=2/\mathrm E(Y_1)$.

share|improve this answer
    
Tell me if some steps are not detailed enough. –  Did Nov 17 '11 at 1:57
    
Hello I have similar homework. I dont understand the step when t->0 why the LHS that was previously exponential became of linear form. –  irrehaare Nov 4 '12 at 12:58
    
@irrehaare Because $e^t=1+t+o(t)$ when $t\to0$. –  Did Nov 4 '12 at 13:10

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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