R help - Oct 2008 - runs of heads when flipping a coin

Can someone recommend a method to answer the following type of question:

Suppose I have a coin with a probability hhh of coming up heads (and 1-hhh
of coming up tails)
I plan on flipping the coin nnn times (for example, nnn = 500)
What is the expected probability or frequency of a run of rrr heads* during
the nnn=500 coin flips?
Moreover, I would probably (excuse the pun) want the answer for a range of
rrr values, for example rrr = 0:50

Of course I am more interested in an analytical solution than a monte carlo
simulation solution.

Thanks in advance,

Harvey

* OR "a run of rrr heads or more ..."

	[[alternative HTML version deleted]]

You can use 'sample' and 'rle':
> x <- sample(c("H","T"), 500, replace=TRUE,
prob=c(.95, .05))
> as.data.frame(unclass(rle(x)))
   lengths values
1       12      H
2        1      T
3       10      H
4        1      T
5        5      H
6        2      T
7       26      H
8        1      T
9       17      H
10       1      T
11      54      H
12       1      T
13      23      H
14       1      T
15       7      H
16       1      T
17       2      H


On Thu, Oct 9, 2008 at 1:16 PM, Harvey <modelers at gmail.com>
wrote:
> Can someone recommend a method to answer the following type of question:
>
> Suppose I have a coin with a probability hhh of coming up heads (and 1-hhh
> of coming up tails)
> I plan on flipping the coin nnn times (for example, nnn = 500)
> What is the expected probability or frequency of a run of rrr heads* during
> the nnn=500 coin flips?
> Moreover, I would probably (excuse the pun) want the answer for a range of
> rrr values, for example rrr = 0:50
>
> Of course I am more interested in an analytical solution than a monte carlo
> simulation solution.
>
> Thanks in advance,
>
> Harvey
>
> * OR "a run of rrr heads or more ..."
>
>        [[alternative HTML version deleted]]
>
> ______________________________________________
> R-help at r-project.org mailing list
> https://stat.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide
http://www.R-project.org/posting-guide.html
> and provide commented, minimal, self-contained, reproducible code.
>


-- 
Jim Holtman
Cincinnati, OH
+1 513 646 9390

What is the problem that you are trying to solve?

On 10/10/2008, at 6:16 AM, Harvey wrote:
> Can someone recommend a method to answer the following type of  
> question:
>
> Suppose I have a coin with a probability hhh of coming up heads  
> (and 1-hhh
> of coming up tails)
> I plan on flipping the coin nnn times (for example, nnn = 500)
> What is the expected probability or frequency of a run of rrr  
> heads* during
> the nnn=500 coin flips?
> Moreover, I would probably (excuse the pun) want the answer for a  
> range of
> rrr values, for example rrr = 0:50
>
> Of course I am more interested in an analytical solution than a  
> monte carlo
> simulation solution.
I think this is a relatively deep problem analytically, and there  
appears to
be a substantial amount of literature.  Googling on ``probability of  
a sequence
of runs'' got a lot of hits, including a pointer to

	http://mathworld.wolfram.com/Run.html

which gives some interesting discussion and provides a number of  
references.
(Feller volume 1 seems to be a good place to start, as usual.)

		cheers,

			Rolf Turner

######################################################################
Attention:\ This e-mail message is privileged and confid...{{dropped:9}}

IIRC this is a standard problem in digital communications theory, so you 
might want to look for literature in that arena.

Carl


 > Can someone recommend a method to answer the following type of
 > question:
 >
 > Suppose I have a coin with a probability hhh of coming up heads
 > (and 1-hhh
 > of coming up tails)
 > I plan on flipping the coin nnn times (for example, nnn = 500)
 > What is the expected probability or frequency of a run of rrr
 > heads* during
 > the nnn=500 coin flips?
 > Moreover, I would probably (excuse the pun) want the answer for a
 > range of
 > rrr values, for example rrr = 0:50
 >
 > Of course I am more interested in an analytical solution than a
 > monte carlo
 > simulation solution.

I think this is a relatively deep problem analytically, and there appears to
be a substantial amount of literature. Googling on ``probability of a 
sequence
of runs'' got a lot of hits, including a pointer to

         http://mathworld.wolfram.com/Run.html

which gives some interesting discussion and provides a number of references.
(Feller volume 1 seems to be a good place to start, as usual.)

First of all, we must define what is a run of length r: is it a tail, then
EXACTLY r heads and a tail again or is it AT LEAST r heads.
Let's assume that we are looking for a run of EXACTLY r heads (and we toss
the coin n times).
Let X[1],X[2],...,X[n-r+1] be random variables such that Xi = 1 if there is a
run of r heads starting at place i and 0 otherwise. Then the number of runs of
length r is just sum(X), so the expected number of runs of length r is sum(E(X))
= sum(P(X[i]=1)).
Now, for i=2,3,...,n-r P(X[i] = 1) = (1-h)*h^r*(1-h) and also P(X[1] = 1) =
h^r*(1-h) and P(X[n-r+1] = 1) = (1-h)*h^r, so that the expected number of runs
of length r is
(1-h)*h^r*(2 + (n-r-1)*(1-h))

As to the distribution of the number of such runs, this is a much more difficult
question (as mentioned by some other people).


--- On Fri, 10/10/08, Harvey <modelers at gmail.com> wrote:
> From: Harvey <modelers at gmail.com>
> Subject: [R] runs of heads when flipping a coin
> To: r-help at r-project.org
> Received: Friday, 10 October, 2008, 4:16 AM
> Can someone recommend a method to answer the following type
> of question:
> 
> Suppose I have a coin with a probability hhh of coming up
> heads (and 1-hhh
> of coming up tails)
> I plan on flipping the coin nnn times (for example, nnn > 500)
> What is the expected probability or frequency of a run of
> rrr heads* during
> the nnn=500 coin flips?
> Moreover, I would probably (excuse the pun) want the answer
> for a range of
> rrr values, for example rrr = 0:50
> 
> Of course I am more interested in an analytical solution
> than a monte carlo
> simulation solution.
> 
> Thanks in advance,
> 
> Harvey
> 
> * OR "a run of rrr heads or more ..."
> 
> 	[[alternative HTML version deleted]]
> 
> ______________________________________________
> R-help at r-project.org mailing list
> https://stat.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide
> http://www.R-project.org/posting-guide.html
> and provide commented, minimal, self-contained,
> reproducible code.