Question

Suppose that the probability of getting a head on the ith toss of an ever-changing coin is f(i). How would you efficiently compute the probability of getting exactly k heads in n tosses?

Answer 1

Let us say p = Pi, and q = 1- Pi. Then the probability of a given sequence, e.g., 100010..., in which k heads appear in n flips e.g pqqqpq... can be given by pk. gn-k There are a total of 2" possible sequences. Only some of these give k heads and n - k tails. Their number is (*) n! k!(n – k)! Since any one or another of these sequences will do, the probability that exactly k heads occur in n flips would be q"-k