PaC Exercise 1.1

import numpy as np

Exercise 1.1

We flip a fair coin ten times. Find the probability of the following events.

(a)

The number of heads and the number of tails are equal.

Let N = 10. Then by simple combinatorics or using the Binomial distribution the desired probality is

$$ {N \choose N/2} \left(\frac 1 2\right)^{N/2} \left(\frac 1 2\right)^{N/2} = {10 \choose 5} \frac{1}{2^{10}} = \frac{63}{256} = 0.24609\dots . $$

We can verify this empirically:

N = 10
num_samples = 100000

samples = np.random.randint(low=0, high=2, size=(num_samples, N))

(samples.sum(axis=1) == N / 2).sum() / len(samples)

0.24615

(b)

There are more heads than tails.

Since the coin is fair this probability can be computed by symmetry as

$$ \frac{1-p_1}{2}, $$

where p₁ denotes the probability found in part (a). Alternatively, it can be determined by using the binomial distribution:

$$ \sum_{i=N/2+1}^N {N \choose i}\left(\frac 1 2\right)^N. $$

Both ways evaluate to 193/512 = 0.37695….

Again we check empirically:

N = 10
num_samples = 100000

samples = np.random.randint(low=0, high=2, size=(num_samples, N))

(samples.sum(axis=1) > N / 2).sum() / len(samples)

0.37536

(c)

The ith flip and the (11 − i)th flip are the same for i = 1, …, 5.

The probability that the (11 − i)th flip equals the ith is 1/2 for a single i. The event that this holds for all i = 1, …, 5 therefore is (1/2)⁵ = 0.03125.

Again we check empirically:

N = 10
num_samples = 100000

samples = np.random.randint(low=0, high=2, size=(num_samples, N))

np.product([samples[:,i] == samples[:, N-i-1] for i in range(5)], axis=0).sum() / len(samples)

0.0317

(d)

We flip at least four consecutive heads.

Let E_i, i = 1, …, 7, be the event that the first series of consecutive heads in the 10 tosses start at toss i. The probability of these events can than be computed quite easily. Note that beginning with E₅ the probability are ever so slightly more difficult to compute.

Another way is to solve this by recursion. Let E_N, i denote the event that in N tosses there occur at least i consecutive heads. Then, P(E_N, i) = 0 if i > N. Otherwise, the probability of P(E_N, i) can be split as follows. Either the k consecutive heads already occurred in the first N − 1 tosses or the first N − i − 1 tosses do not contain a consecutive series of i heads and the series of n heads (out of all N throws) start at toss N − i. This consideration yields

$$ \begin{align*} P(E_{4,4}) &= (1/2)^4,\\ P(E_{5,4}) &= P(E_{4,4}) + (1/2)^5 =(1/2)^4 + (1/2)^5,\\ P(E_{6,4}) &= P(E_{5,4}) + (1/2)^5 = (1/2)^3,\\ P(E_{7,4}) &= P(E_{6,4}) + (1/2)^5 = (1/2)^3 + (1/2)^5\\ P(E_{8,4}) &= P(E_{7,4}) + (1 - P(E_{3,4})(1/2)^5 = P(E_{7,4}) + (1/2)^5=(1/2)^3 + (1/2)^4\\ P(E_{4,4}) &= (1/2)^4,\\ P(E_{9,4}) &= P(E_{8,4}) + (1 - P(E_{4,4}) (1/2)^5 = (1/2)^3 + (1/2)^4 +(1-(1/2)^4) (1/2)^5\\ P(E_{5,4}) &= (1/2)^4 + (1/2)^5,\\ P(E_{10,4}) &= P(E_{9,4}) + (1 - P(E_{5,4})) (1/2)^5 = (1/2)^3 + (1/2)^4 +(1-(1/2)^4) (1/2)^5 + (1-(1/2)^4 + (1/2)^5) (1/2)^5. \end{align*} $$

N = 10
num_samples = 100000

samples = np.random.randint(low=0, high=2, size=(num_samples, N))

def check_consecutive_head(sample, n=4):
    current_max = 0
    current_streak = 0
    for i in sample:
        current_streak = current_streak + 1 if i else 0
        current_max = max(current_streak ,current_max)
    return current_max

(np.array([check_consecutive_head(s) for s in samples]) >= 4).sum() / len(samples)

0.24448