SERVING THE QUANTITATIVE FINANCE COMMUNITY

Paul
Posts: 10773
Joined: July 20th, 2001, 3:28 pm

### Re: expected number of 1-runs

I'd give you my solution but I'm afraid of all the accolades...

katastrofa
Posts: 9212
Joined: August 16th, 2007, 5:36 am
Location: Alpha Centauri

### Re: expected number of 1-runs

Or B_Swinging_D?
What?

Paul
Posts: 10773
Joined: July 20th, 2001, 3:28 pm

### Re: expected number of 1-runs

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$

katastrofa
Posts: 9212
Joined: August 16th, 2007, 5:36 am
Location: Alpha Centauri

### Re: expected number of 1-runs

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!

Paul
Posts: 10773
Joined: July 20th, 2001, 3:28 pm

### Re: expected number of 1-runs

I'm sure that if I put my mind to it I could do it with five variables!

Alan
Posts: 10167
Joined: December 19th, 2001, 4:01 am
Location: California
Contact:

### Re: expected number of 1-runs

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.

Paul
Posts: 10773
Joined: July 20th, 2001, 3:28 pm

### Re: expected number of 1-runs

That’s because I hate spoon feeding people!

But ok I’ll write it up! (Some of it!)

Paul
Posts: 10773
Joined: July 20th, 2001, 3:28 pm

### Re: expected number of 1-runs

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}.$

Alan
Posts: 10167
Joined: December 19th, 2001, 4:01 am
Location: California
Contact:

### Re: expected number of 1-runs

Very nice!

katastrofa
Posts: 9212
Joined: August 16th, 2007, 5:36 am
Location: Alpha Centauri

### Re: expected number of 1-runs

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.

Paul
Posts: 10773
Joined: July 20th, 2001, 3:28 pm

### Re: expected number of 1-runs

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!

Cuchulainn
Posts: 62122
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

### Re: expected number of 1-runs

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?

katastrofa
Posts: 9212
Joined: August 16th, 2007, 5:36 am
Location: Alpha Centauri

### Re: expected number of 1-runs

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: 1
Joined: May 8th, 2020, 8:06 am

### Re: expected number of 1-runs

Can anyone explain the solution,I couldn't understand the formula.

Cuchulainn
Posts: 62122
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

### Re: expected number of 1-runs

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.