Finite Probability Counting Rules

Context

MIT6041 - Probability Counting uses elementary counting identities as the bridge from finite combinatorics to probability. This annex keeps the reusable formulas separate from the narrative source note while leaving Counting in Probability with enough technical detail to stand on its own.

Formal Statement

For a finite sample space Omega with equally likely outcomes,

$$P(A)=\frac{|A|}{|\Omega |}.$$

The basic selection count is

$$\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\frac{n!}{k!(n-k)!},$$

and the total number of subsets of an n-element set is

$$\sum _{k=0}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)=2^n.$$

For n independent Bernoulli trials with success probability p,

$$P(K=k)=\left(\genfrac{}{}{0ex}{}{n}{k}\right)p^k(1-p{)}^{n-k}.$$

When conditioning on an event B whose outcomes are equally likely,

$$P(A\mid B)=\frac{|A\cap B|}{|B|}.$$

Derivation / Construction

The binomial coefficient follows by counting ordered selections in two ways. There are

$$n(n-1)\cdots (n-k+1)=\frac{n!}{(n-k)!}$$

ordered selections of k distinct objects. Each unordered k-subset appears in k! orders, so dividing by k! gives binom(n,k).

The binomial probability formula groups length-n Bernoulli sequences by the number of successes: each sequence with k successes has probability p^k(1-p)^{n-k}, and there are binom(n,k) such sequences.

Implications

• Counting arguments are probability arguments only after the equally-likely-outcome assumption is explicit.
• Conditional counting should count configurations inside the conditioned event.
• Exact subset-sampling algorithms, such as Floyd’s Sampling Algorithm, are operational counterparts of the same combinatorial counts.

Links

• Counting in Probability
• MIT6041 - Probability Counting
• Floyd’s Sampling Algorithm