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

- katastrofa
**Posts:**9855**Joined:****Location:**Alpha Centauri

What?Or B_Swinging_D?

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[$]

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:**9855**Joined:****Location:**Alpha Centauri

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!

[$]AB_n[$] - expected number of 1-R-runs in an n-sequence

[$]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!

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

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

That’s because I hate spoon feeding people!

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

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

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

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

- katastrofa
**Posts:**9855**Joined:****Location:**Alpha Centauri

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**

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,

Last edited by katastrofa on May 17th, 2020, 3:20 am, edited 1 time in total.

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!

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:**63819**Joined:****Location:**Amsterdam-
**Contact:**

Can someone define what a *run* is, precisely?

*After all, a length-n 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?

yeah, that's what I mean.

Changing OP's post

What's the expected number of 1-runs when tossing a fair coin

for example: THHTHTHTTH has

HHTHTHTHHTH has 5?

Is this correct?

My C++ Boost code gives

262537412640768743.999999999999250072597198185688879353856337336990862707537410378210647910118607313

http://www.datasimfinancial.com

http://www.datasim.nl

262537412640768743.999999999999250072597198185688879353856337336990862707537410378210647910118607313

http://www.datasimfinancial.com

http://www.datasim.nl

- katastrofa
**Posts:**9855**Joined:****Location:**Alpha Centauri

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.

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:**

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

- Cuchulainn
**Posts:**63819**Joined:****Location:**Amsterdam-
**Contact:**

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

My C++ Boost code gives

262537412640768743.999999999999250072597198185688879353856337336990862707537410378210647910118607313

http://www.datasimfinancial.com

http://www.datasim.nl

262537412640768743.999999999999250072597198185688879353856337336990862707537410378210647910118607313

http://www.datasimfinancial.com

http://www.datasim.nl

GZIP: On