Sequences of Bernoulli Outcomes with the Same Probability

The Question

There are many possible success-failure sequences in an i.i.d. (independent and identically distributed) Bernoulli experiment with \(n\) trials and \(k\) successes.

Do sequences with exactly \(k\) successes have the same conditional probability once we know \(X = k\)?
Does the common success probability \(p\) affect that conditional probability?

Short answer: yes, in the i.i.d. case, all compatible sequences are equally likely after conditioning on \(X = k\). Each one has conditional probability \(1 / \binom{n}{k}\), and the value of \(p\) cancels out as long as \(P(X = k) > 0\).

Why I Care

Prof. Blitzstein says that "conditioning is the soul of statistics." At least to me, that sentence can feel vague until you see conditioning in action. This problem helps with that: the key insight is to condition on \(X = k\), which lets us simplify the math, as we will see.

Setup and Definitions

The conditional probability rule is:

\begin{aligned} P(A \mid B) &= \frac{P(A, B)}{P(B)} \\ &= \frac{P(A \cap B)}{P(B)} \end{aligned}

Let \(X_i \in \{0, 1\}\) indicate whether trial \(i\) is a success or failure. Then:

X = X_1 + X_2 + \cdots + X_n

So \(X\) is the total number of successes. If \(X \sim \mathrm{Bin}(n, p)\), then:

P(X = k) = \binom{n}{k}p^k q^{n-k}, \quad q = 1 - p

Concrete example: if we throw a coin 5 times and get 2 tails, there are many ways to get 2 tails. If we treat tails as success, then examples include TTHHH and THHHT.

Do all these ways have equal probability?
Does this depend on whether or not the coin is fair?

Minimal Derivation

Fix \(k\) and take any sequence \((a_1, \ldots, a_n)\) where each \(a_i\) is either \(0\) or \(1\), and:

a_1 + \cdots + a_n = k

We want to compute:

P(X_1 = a_1, \ldots, X_n = a_n \mid X = k)

By the definition of conditional probability:

P(X_1 = a_1, \ldots, X_n = a_n \mid X = k) = \frac{ P(X_1 = a_1, \ldots, X_n = a_n, X = k) }{ P(X = k) }

The key insight is that the event \(\{X_1 = a_1, \ldots, X_n = a_n\}\) already implies \(\{X = k\}\), because \(a_1 + \cdots + a_n = k\). So we can simplify the numerator and get rid of the annoying condition:

P(X_1 = a_1, \ldots, X_n = a_n, X = k) = P(X_1 = a_1, \ldots, X_n = a_n)

By independence:

P(X_1 = a_1, \ldots, X_n = a_n) = p^k q^{n-k}

The binomial probability is:

P(X = k) = \binom{n}{k}p^k q^{n-k}

Therefore:

\begin{aligned} P(X_1 = a_1, \ldots, X_n = a_n \mid X = k) &= \frac{p^k q^{n-k}}{\binom{n}{k}p^k q^{n-k}} \\ &= \frac{1}{\binom{n}{k}} \end{aligned}

This does not depend on the particular sequence \((a_1, \ldots, a_n)\), so all sequences with exactly \(k\) successes are equally likely once we condition on \(X = k\). It also does not depend on \(p\), as long as \(P(X = k) > 0\).

Statistics has a name for this: the count \(X\) is a sufficient statistic for \(p\). Once we know \(X = k\), the exact sequence carries no extra information about \(p\). The concept goes back to Fisher (1922).

What I Think I Learned

If event \(A\) already implies event \(B\), then the event \(A \cap B\) is really just the event \(A\). In that case:

P(A \cap B) = P(A)

So conditioning on \(B\) does not add a new restriction to \(A\); it only changes the denominator:

P(A \mid B) = \frac{P(A)}{P(B)}

Open Questions

What changes if the Bernoulli trials are independent but have different probabilities?
What changes if the trials are not independent?
How often does this "the event already implies the condition" trick appear in other probability problems?

References

My Stat 110 random variables notes
Stat 110 Strategic Practice and Homework 3
Blitzstein & Hwang, Introduction to Probability—the Stat 110 book, free from the authors.
Fisher, On the Mathematical Foundations of Theoretical Statistics (1922)—where sufficient statistics were introduced.