0

I tried to look for a similar question but didn't find the exact thing (the closest I found was this but AFAIK it is not the same)

I have $r$ coins that land heads w.p. $p$. I want at least $m$ heads. On the first step I toss all of $r$ coins and from the second step and on I toss only the coins that didn't land heads already.

What is the expected number of steps until I have at least $m$ heads?

Thank you in advance!

Community
  • 1
hashark
  • 103

2 Answers2

1

Denote this expectation by $\mu_{r,m}$. If $X$ denotes the number of coins that get $1$ then:

$$\mu_{r,m}=1+P\left(X=0\right)\mu_{r,m}+\cdots+P\left(X=m-1\right)\mu_{r-m+1,1}$$

Here $X\sim\text{Bin}(r,p)$.

This allows you to express $\mu_{r,m}$ in $\mu_{r-i,m-i}$ for $i=1,\dots,m-1$ so a recurrence relation is found.

Success!

drhab
  • 151,093
0

Assume the number of steps is $n$.

By that time the (expected) fraction of coins that still is a $0$ is $(1-p)^n$.

So you are looking for $n$ where $r \times (1-p)^n \leq (r - m)$. (The number of $0$ is less than or equal to the allowed number of $0$'s)

(Take a logarithm, after some rearranging of terms to have the exact answer)

Pieter21
  • 3,475
  • thanks! but that's just a lower bound. I am looking for the exact phrase. – hashark Feb 10 '15 at 13:30
  • I think that these functions are nice enough that it will also be the exact number. E.g. if you take the example where you want 7 out of 8 fair coins to be 1, the answer is 3, as I'd expect. – Pieter21 Feb 10 '15 at 15:44