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.

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?

share|improve this question
    
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

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
    
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

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.