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


  • 0
    J
    /*
    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))
    
    */
    long expectedNumTosses_mHeadInARow(double p, int m)
    {
    	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

  • 0
    R

    is this problem provided for research background ineterview?


Log in to reply
 

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