# Coin tossing and counting heads

Toss coins with probability $p_i$ of getting a head. Call the number of coin tosses you need on average until you get the first head $A$. The number of tosses you need to get an average of at least one head is the smallest integer $y$ so that $\sum_{i=1}^{y} p_i \geq 1$.

When is it true that $y \geq A$? Is it true if the $p_i$ are non-decreasing?

-
I think you need to work on these definitions some more. "Probability of getting a head until you get a head"... what does that mean? –  1015 Apr 1 '13 at 12:24
@julien Corrected. Thank you. –  artmax Apr 1 '13 at 12:27
See the geometric distribution. –  1015 Apr 1 '13 at 12:30
Not sure if I get this still. Let $p_i = \frac{2}{3}, \forall i > 0$. What is $y$? –  Macavity Apr 1 '13 at 12:33
@Macavity Solve $2y/3 =1$ so $y=3/2$. Round up to $2$. –  artmax Apr 1 '13 at 12:36

Let $T$ denote the number of the coin toss when the first head appears. For every nonnegative integer $n$, let $Q(n)=\sum\limits_{i=1}^{+\infty}p_i\mathbf 1_{i\leqslant n}$. Thus, $A$ and $y$ are uniquely defined by the identity $A=E[T]$ and by the fact that $Q(y)\geqslant1\gt Q(y-1)$.

Extend $Q$ to the nonnegative real line by linear interpolation and assume that the extended function $Q$ is convex. This is equivalent to the fact that $(p_i)_{i\geqslant1}$ is nondecreasing.

Then, Jensen inequality yields $Q(A)\leqslant E[Q(T)]$. For every $i\geqslant1$, $P[T\geqslant i]=\prod\limits_{n=1}^{i-1}(1-p_n)$. Hence, $E[Q(T)]=\sum\limits_{i=1}^{+\infty}p_iP[T\geqslant i]=\sum\limits_{i=1}^{+\infty}p_i\prod\limits_{n=1}^{i-1}(1-p_n)=1-\prod\limits_{n=1}^{+\infty}(1-p_n)\leqslant1.$ In particular $Q(A)\leqslant1$, which implies that $A\leqslant y$.

If the sequence $(p_i)_{i\geqslant1}$ is nondecreasing, then $y\geqslant A$.

As an example in the other direction, assume that $p_i\lt1$ for every $i\geqslant1$ and that $\sum\limits_ip_i$ converges. Then the event "no head ever" has positive probability hence $A$ is infinite and the inequality $y\geqslant A$ cannot hold in full generality.

-
Why is $E[Q(T)]=\sum\limits_{i=1}^{+\infty}p_iP[T\geqslant i]$ true? –  artmax Apr 1 '13 at 15:31
Because $Q(T)=\sum\limits_{i=1}^{+\infty}p_i\mathbf 1_{T\geqslant i}$, by definition of $Q$. –  Did Apr 1 '13 at 15:33
Thank you. Do you know if there is a reference for this problem? –  artmax Apr 1 '13 at 15:37
None that I would be aware of. –  Did Apr 1 '13 at 15:44
Dunno. What did you try? –  Did Apr 1 '13 at 19:24