Coin Tosses

####You have an unbiased coin which you want to keep tossing until you get N consecutive heads.You’ve tossed the coin M times and surprisingly, all tosses resulted in heads.
What is the expected number of additional tosses needed until you get N consecutive heads?

Input: #####The first line contains the number of cases T. Each of the next T lines contains two numbers N and M.

Output: #####Output T lines containing the answer for the corresponding test case. Print the answer rounded to exactly 2 decimal places. Sample Input:4 2 0 2 1 3 3 3 2 Sample Output:6.00 4.00 0.00 8.00 Sample Explanation:

If N = 2 and M = 0, you need to keep tossing the coin until you get 2 consecutive heads. It is not hard to show that on average, 6 coin tosses are needed.

If N = 2 and M = 1, you need 2 consecutive heads and have already have 1. You need to toss once more no matter what. In that first toss, if you get heads, you are done. Otherwise, you need to start over, as the consecutive counter resets, and you need to keep tossing the coin until you get N=2 consecutive heads.
The expected Number of coin tosses is thus 1 + (0.5 * 0 + 0.5 * 6) = 4.0

If N = 3 and M = 3, you already have got 3 heads, so you do not need any more tosses.

Constraints:1 <= T <= 100
1 <= N <= 1000
0 <= M <= N

Hint

This problem is a Mathematical Expectation problem

Mathematically, for a discrete variable X with probability function P(X), the expected value E[X] is given by Σ x_iP(x_i) the summation runs over all the distinct values x_i that the variable can take.

For Eg.

Find number of coin flips for getting a single head.

Let Expected number of coin flips for getting a head is x

a. If the first flip is the head, then we are done. The probability of this event is 1/2 and the number of coin flips for this event is 1. 

b. If the first flip is the tails, then we have to start over.The probability of this event is 1/2 and the expected number of coins flips now onwards is x. But we have already wasted one flip, so the total number of flips is x+1.

this gives ,

x = (1/2)(1) + (1/2) (1+x)

Solving, we get x = 2.

Similarly for n consecutive heads ,

if 1st , 2nd , 3rd or nth flip gives tail then we have to start all over again.
else we are done

Combining 1 & 2 gives x = (1/2)(x+1) + (1/4)(x+2) + ... + (1/(2^k))(x+k) + .. + (1/(2^N))(x+N) + (1/(2^N))(N)

we get,

x = 2^N+1-2 .

We can also understand it this way ,

let En be the probability for n consecutive heads means

In order to obtain n consecutive heads, we must first obtain n-1 consecutive heads, followed by:

with probability ½, a further head; or
with probability ½, a tail, after which we must obtain n consecutive heads.

It follows that En = ½(En-1 + 1) + ½(En-1 + 1 + En), from which En = 2En-1 + 2. which also give En = 2^N+1-2 .

Now as per given problem we already have M number of heads therefore let rest number of coin flips required be x.

let k =N-M be the consecutive heads required.

so,

if 1st , 2nd , 3rd or kth flip gives tail then we have to start all over again ie. to find n consecutive heads.
else we are done

which gives

y = (1/2)(x+1) + (1/4)(x+2) + ... + (1/(2^k))(x+k) + (1/(2^N-k))(k)

and x = 2^N+1-2.

solving this gives ,

y = 2^N+1 - 2^M+1

####Important Note : In the problems where there are two events, where one event is desirable and other is undesirable, and the probability of desirable event is p, then the expected number of trials done to get the desirable event is 1/p Proof : a. If we get the event, the probability of this is p and we are done. b. If we don’t get the event, the probability of this is (1-p) and we have to start all over again and we wasted one chance so x = p + (1-p)*(x+1) solving we get x = 1/p ——

Generalizing on the number of events. If there are K events, where one event is desirable and all others are undesirable, and the probability of desirable 	event is p, then also the expected number of trials done to get the desirable event is 1/p.
--------

Expected number of bernaulli trials to ensure that there are atleast N successes, if the probability of each success is p
	E[N] = p(E[N-1]+1)+(1-p)(E[N]+1)
	Solving we get ,
		E[N] = n/p

Code (Java)

1
2
3
4
5
6
7
8
9
10
11
12
13
14 import java.math.BigInteger;
import java.util.Scanner;
public class Solution {
    public static void main(String[] args) {
        Scanner a = new Scanner(System.in);
        int t= a.nextInt();
        while(t--!=0){
            int n=a.nextInt();
            int m = a.nextInt();
            BigInteger b = BigInteger.valueOf(2).pow(n+1);
            BigInteger c= BigInteger.valueOf(2).pow(m+1);
            System.out.println(b.subtract(c)+".00");
    }}
}