Serving the Quantitative Finance Community

 
User avatar
AnonymousQuantus
Topic Author
Posts: 3
Joined: May 9th, 2012, 12:15 pm

expected number of 1-runs

May 6th, 2020, 12:10 pm

What's the expected number of 1-runs when tossing a fair coin 100 times;
where 1-run (for heads) is defined as HT or H for the last toss;
for example: THHTHTHTTH has 3 1-runs.
 
User avatar
katastrofa
Posts: 7440
Joined: August 16th, 2007, 5:36 am
Location: Alpha Centauri

Re: expected number of 1-runs

May 7th, 2020, 3:09 pm

The max number is 50, the min number is 0, the average is 25.
 
User avatar
AnonymousQuantus
Topic Author
Posts: 3
Joined: May 9th, 2012, 12:15 pm

Re: expected number of 1-runs

May 7th, 2020, 6:57 pm

Can not find fault in your reasoning: (50+0)/2 = 25 and it works for n=2;
althought n=100 and we are looking for a mean not an average.
 
User avatar
Alan
Posts: 2958
Joined: December 19th, 2001, 4:01 am
Location: California
Contact:

Re: expected number of 1-runs

May 10th, 2020, 2:11 pm

Numerically, it looks like 

[$]\mbox{mean}_{100} \approx 12.75 \pm 0.003[$], 

and for n draws,

[$]\mbox{mean}_n \sim \frac{1}{8} n[$], as [$]n \rightarrow \infty[$].

Also, makes sense that the [$]\mbox{mean}_n/n[$] is decreasing with [$]n[$], as the above suggests. 
After all, a length-[$]n[$] sequence ending in TH would have a 1-run counted there, but not necessarily if that sequence was continued. 

Looking at Feller, he suggests looking at this type of problem as a recurrent process, but I didn't have the patience. In other words, once a 1-run occurs (say in a sequence of indefinite length), the problem of the next 1-run is (an independent) probabilistic replica of the original problem. 

I'm sure there must be a nice argument for my asymptotic guess; maybe even a nice formula for finite n. I would be interested to see them. 

Anyway, that's as far as I got -- I suggest Feller Vol. I for general strategy hints.  
 
User avatar
AnonymousQuantus
Topic Author
Posts: 3
Joined: May 9th, 2012, 12:15 pm

Re: expected number of 1-runs

May 10th, 2020, 4:15 pm

That's spot on. It is exactly 12.75 (and stdDev = 3.326...).
my computation indicates that

mean(n) = n/8 + 1/4 for n > 1
 
User avatar
Alan
Posts: 2958
Joined: December 19th, 2001, 4:01 am
Location: California
Contact:

Re: expected number of 1-runs

May 10th, 2020, 4:19 pm

Nice and simple. Can you post how you got it?
 
User avatar
Alan
Posts: 2958
Joined: December 19th, 2001, 4:01 am
Location: California
Contact:

Re: expected number of 1-runs

May 13th, 2020, 2:03 pm

Too bad the OP seems to be MIA. 

I thought the problem was interesting. 

Can anybody derive AQ's (likely correct) formula? 
(I will try again at some point). 
 
User avatar
katastrofa
Posts: 7440
Joined: August 16th, 2007, 5:36 am
Location: Alpha Centauri

Re: expected number of 1-runs

May 15th, 2020, 12:18 am

Now I understand the question is about just H or just T single runs -?
The guessed formula isn't correct IMHO.
It can be solved either inductively or deductively. Who do you like more, Newton or Sherlock Holmes?
 
User avatar
Cuchulainn
Posts: 20250
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

Re: expected number of 1-runs

May 15th, 2020, 12:07 pm

Too bad the OP seems to be MIA. 
Ask Naughtius Maximus?

www.youtube.com/watch?v=kx_G2a2hL6U
 
User avatar
Alan
Posts: 2958
Joined: December 19th, 2001, 4:01 am
Location: California
Contact:

Re: expected number of 1-runs

May 15th, 2020, 1:32 pm

Now I understand the question is about just H or just T single runs -?
The guessed formula isn't correct IMHO.
It can be solved either inductively or deductively. Who do you like more, Newton or Sherlock Holmes?

Single H runs in a sequence of n coin tosses consist of:
 HT...       at the beginning
.. THT … prior to the end
… TH      at the end

Looking for a formula + derivation for the mean number of single H runs in a sequence of n tosses.

The proposed formula seems likely correct, given my numerics and small n cases. If so, all we need is the derivation. Whoever provides it shall be named honorary BD (see Monty Python link) 
 
User avatar
katastrofa
Posts: 7440
Joined: August 16th, 2007, 5:36 am
Location: Alpha Centauri

Re: expected number of 1-runs

May 15th, 2020, 4:52 pm

If you like that formula, I will rather not post the solution, which shows that it's incorrect (-:
 
User avatar
Paul
Posts: 6603
Joined: July 20th, 2001, 3:28 pm

Re: expected number of 1-runs

May 15th, 2020, 5:29 pm

Where’ve you been for the last two months? The more wrong the formula the more we lap it up!
 
User avatar
Alan
Posts: 2958
Joined: December 19th, 2001, 4:01 am
Location: California
Contact:

Re: expected number of 1-runs

May 15th, 2020, 5:49 pm

Come on, people -- this problem can't be that hard! Let's wrap it up so we can go back to the pandemic. 
 
User avatar
Cuchulainn
Posts: 20250
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

Re: expected number of 1-runs

May 15th, 2020, 6:57 pm

Or B_Swinging_D?
 
User avatar
Alan
Posts: 2958
Joined: December 19th, 2001, 4:01 am
Location: California
Contact:

Re: expected number of 1-runs

May 15th, 2020, 7:10 pm

Michael Lewis or Monty Python -- take your pick.