# Find expected number of tosses of an unbiased or biased coin, until there are m (>= 1) heads in a row

• /*
Find expected number of tosses of an unbiased or biased coin
until there are m (>= 1) heads in a row,
supposing the head probability in a toss is p: 0 < p <= 1.

If the result is not integer, round it.

Let X be number of tosses.
We can calculate the expectation E(X) via conditioning.
We have
For  0 < p < 1,
E(X) = (m*p^m + sum{k*q*p^(k-1): k = 1,..., m}) / (1 - sum{q*p^(k-1): k = 1,..., m}) ;
For p = 1,
E(X) = m.

For  0 < p < 1, the result can be simplified as
E(X) = (1-p^m) / (p^m*(1-p))

*/
{
double EX = 1.0e8; // p = 0, infinite number of tosses
if (p == 1.0)
EX = m + 0.0;
if ((0.0 < p) && (p < 1.0))
{
double pm = pow(p,m); // p^m
EX = (1.0 - pm) / (pm*(1.0-p));
}

return ((long)floor(EX+0.5));
}

>>
Expected number of tosses of a coin until there are m (>= 1) head in a row
p = 0.8:
m = 1, E(X) = 1
m = 2, E(X) = 3
m = 3, E(X) = 5
m = 4, E(X) = 7
m = 5, E(X) = 10
m = 6, E(X) = 14
m = 7, E(X) = 19
m = 8, E(X) = 25
m = 9, E(X) = 32
m = 10, E(X) = 42

p = 0.6:
m = 1, E(X) = 2
m = 2, E(X) = 4
m = 3, E(X) = 9
m = 4, E(X) = 17
m = 5, E(X) = 30
m = 6, E(X) = 51
m = 7, E(X) = 87
m = 8, E(X) = 146
m = 9, E(X) = 246
m = 10, E(X) = 411

p = 0.5:
m = 1, E(X) = 2
m = 2, E(X) = 6
m = 3, E(X) = 14
m = 4, E(X) = 30
m = 5, E(X) = 62
m = 6, E(X) = 126
m = 7, E(X) = 254
m = 8, E(X) = 510
m = 9, E(X) = 1022
m = 10, E(X) = 2046

p = 0.25:
m = 1, E(X) = 4
m = 2, E(X) = 20
m = 3, E(X) = 84
m = 4, E(X) = 340
m = 5, E(X) = 1364
m = 6, E(X) = 5460
m = 7, E(X) = 21844
m = 8, E(X) = 87380
m = 9, E(X) = 349524
m = 10, E(X) = 1398100

p = 0.166667:
m = 1, E(X) = 6
m = 2, E(X) = 42
m = 3, E(X) = 258
m = 4, E(X) = 1554
m = 5, E(X) = 9330
m = 6, E(X) = 55986
m = 7, E(X) = 335922
m = 8, E(X) = 2015538
m = 9, E(X) = 12093234
m = 10, E(X) = 72559410

• is this problem provided for research background ineterview?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.