SERVING THE QUANTITATIVE FINANCE COMMUNITY

 
User avatar
Paul
Posts: 10794
Joined: July 20th, 2001, 3:28 pm

Re: expected number of 1-runs

May 15th, 2020, 10:56 pm

I'd give you my solution but I'm afraid of all the accolades...
 
User avatar
katastrofa
Posts: 9575
Joined: August 16th, 2007, 5:36 am
Location: Alpha Centauri

Re: expected number of 1-runs

May 15th, 2020, 11:07 pm

Or B_Swinging_D?
What?
 
User avatar
Paul
Posts: 10794
Joined: July 20th, 2001, 3:28 pm

Re: expected number of 1-runs

May 15th, 2020, 11:12 pm

There might be an easier way, but this is my classical, albeit a bit tedious, way.

The trick is to figure out what variables you need to keep track of the kind of path dependency that's in this. I used

[$]a_n=\mbox{ Expected number of 1 runs when sequence ends on H and is a 1 run}[$], i.e. second to last toss was T
[$]b_n=\mbox{ Expected number of 1 runs when sequence ends on H and is not a 1 run}[$], i.e. second to last toss was H
[$]c_n=\mbox{ Expected number of 1 runs when sequence ends on T}[$]

Then you get coupled difference equations for these three. And solutions are trivial.

End result [$]n/8+1/4, n\ge 2[$]
 
User avatar
katastrofa
Posts: 9575
Joined: August 16th, 2007, 5:36 am
Location: Alpha Centauri

Re: expected number of 1-runs

May 15th, 2020, 11:27 pm

I'm afraid the correct solution is the other way around:
[$]AB_n[$] - expected number of 1-R-runs in an n-sequence starting with AB

[$]HH_n = \frac{1}{2} HT_{n-1} + \frac{1}{2} HH_{n-1}[$]
[$]HT_n = \frac{1}{2} TT_{n-1} + \frac{1}{2} TH_{n-1}[$]
[$]TH_n = \frac{1}{2} (HT_{n-1} + 1) + \frac{1}{2} (HH_{n-1}+1)[$]
[$]TT_n = \frac{1}{2} (TH_{n-1} - 1) + \frac{1}{2} TT_{n-1}[$]

Solving the above you get the correct solution, which happens to be the same as yours.

Startians vs endians. Let the kombat begin!
Image
 
User avatar
Paul
Posts: 10794
Joined: July 20th, 2001, 3:28 pm

Re: expected number of 1-runs

May 15th, 2020, 11:46 pm

I'm sure that if I put my mind to it I could do it with five variables!
 
User avatar
Alan
Posts: 10318
Joined: December 19th, 2001, 4:01 am
Location: California
Contact:

Re: expected number of 1-runs

May 16th, 2020, 1:51 pm

I don't think we have a winner yet.

Paul starts with definitions, but then hand-waves to the answer. 
He needs to fill in the steps.

Kats doesn't seem to be correct. Take n=3 and TT(3). 

The possibilities, each with prob 1/2, are TTH and TTT, 
so TT(3) =  E[#1-runs | TT start]  = 1/2 x 1 + 1/2 x 0  = 1/2.

But TT(3) = (1/2)(TH(2) - 1) + (1/2) TT(2) = (1/2)(1 - 1) + (1/2) 0 = 0.
 
User avatar
Paul
Posts: 10794
Joined: July 20th, 2001, 3:28 pm

Re: expected number of 1-runs

May 16th, 2020, 4:53 pm

That’s because I hate spoon feeding people!

But ok I’ll write it up! (Some of it!)
 
User avatar
Paul
Posts: 10794
Joined: July 20th, 2001, 3:28 pm

Re: expected number of 1-runs

May 16th, 2020, 5:10 pm

See previous definitions. Looking at probabilities of getting from {a, b, c} to {a, b, c} we get

[$]a_{n+1}=c_n+1[$]
[$]b_{n+1}=\tfrac{1}{2}b_n+\tfrac{1}{2}(a_n-1)[$]

(You lose one 1-run.)

[$]c_{n+1}=\tfrac{1}{4}a_n+\tfrac{1}{4}b_n+\tfrac{1}{2}c_n[$]

All for [$]n\ge 2[$] (N.b. not true for [$]n=1[$].)

Now eliminate to get, e.g., one equation for [$]a_n[$]. Potentially this is quite high order but since lots of terms cancel it makes me think that there's a simpler solution. Anyway you get

[$]a_{n+3}-a_{n+2}=\tfrac{1}{8}.[$]

But since this is only valid for [$]n\ge 2[$] use initial condition [$]a_4=\tfrac{3}{2}.[$]

And so

[$]a_n=\tfrac{n}{8}+1.[$]

Similarly for [$]b_n[$] and [$]c_n[$].

And the answer you want is then

[$]\tfrac{1}{4}a_n+\tfrac{1}{4}b_n+\tfrac{1}{2}c_n.[$]

Which results in an expectation of 

[$]\tfrac{n}{8}+\frac{1}{4}.[$]
 
User avatar
Alan
Posts: 10318
Joined: December 19th, 2001, 4:01 am
Location: California
Contact:

Re: expected number of 1-runs

May 16th, 2020, 7:51 pm

Very nice!
 
User avatar
katastrofa
Posts: 9575
Joined: August 16th, 2007, 5:36 am
Location: Alpha Centauri

Re: expected number of 1-runs

May 16th, 2020, 9:34 pm

Sorry, one key off, I meant probability of 1-T-runs.

Solving my system of equations I get the expected number of 1-T-runs in an n-sequence as follows:

[$]E_n = \frac{1}{4}(HH_n + TH_n + HT_n + TT_n) = [$]
[$]\quad=\frac{1}{4}(HT_{n-1} + HH_{n-1} + TH_{n-1} + TT_{n-1}) + \frac{1}{8} = E_{n-1} + \frac{1}{8}[$]
Since E_3 = 1/4 (1/2 + 3/2 + 1/2 + 0) = 5/8, E_n = 5/8 + (n-3)/8
Last edited by katastrofa on May 17th, 2020, 3:20 am, edited 1 time in total.
 
User avatar
Paul
Posts: 10794
Joined: July 20th, 2001, 3:28 pm

Re: expected number of 1-runs

May 16th, 2020, 10:39 pm

Ends in:

HH then H No change
HH then T No change
HT then H +1
HT then T No change
TH then H -1
TH then T No change
TT then H +1
TT then T No change

Expectation goes up by 1/8

N runs then also easy.

Standard deviation similar. Exercise for the reader!
 
User avatar
Cuchulainn
Posts: 62889
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

Re: expected number of 1-runs

May 19th, 2020, 4:02 pm

Can someone define what a run is, precisely?


After all, a length- sequence ending in TH would have a 1-run counted there, but not necessarily if that sequence was continued. 
yeah, that's what I mean.

Changing OP's post
What's the expected number of 1-runs when tossing a fair coin 10 times; where 1-run (for heads) is defined as HT or H for the last toss;
for example: THHTHTHTTH has 4 1-runs.


HHTHTHTHHTH has 5?

Is this correct?
Step over the gap, not into it. Watch the space between platform and train.
http://www.datasimfinancial.com
http://www.datasim.nl
 
User avatar
katastrofa
Posts: 9575
Joined: August 16th, 2007, 5:36 am
Location: Alpha Centauri

Re: expected number of 1-runs

May 25th, 2020, 8:51 pm

1-run is a run of the length 1. You're asking about the number of H-runs (of any length), I believe.
The number of runs (both H and T) for a fair coin is 1 + (n-1) / 2 (the coin needs to change side n-1 times to start a new run). By symmetry, the number of H-runs is a half of it.
 
TabrezSyed
Posts: 2
Joined: May 8th, 2020, 8:06 am

Re: expected number of 1-runs

May 26th, 2020, 5:30 pm

Can anyone explain the solution,I couldn't understand the formula.
 
User avatar
Cuchulainn
Posts: 62889
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

Re: expected number of 1-runs

May 27th, 2020, 11:07 am

1-run is a run of the length 1. You're asking about the number of H-runs (of any length), I believe.
The number of runs (both H and T) for a fair coin is 1 + (n-1) / 2 (the coin needs to change side n-1 times to start a new run). By symmetry, the number of H-runs is a half of it.
Is this the only way to solve the problem? I was thinking of ML, or more prosaically, genetic algos, RNG  and a bit of string ( searching.
Step over the gap, not into it. Watch the space between platform and train.
http://www.datasimfinancial.com
http://www.datasim.nl
ABOUT WILMOTT

PW by JB

Wilmott.com has been "Serving the Quantitative Finance Community" since 2001. Continued...


Twitter LinkedIn Instagram

JOBS BOARD

JOBS BOARD

Looking for a quant job, risk, algo trading,...? Browse jobs here...


GZIP: On