Chapter 02 - Counting and Repeated Trials

Counting

Theory

Theory 1

In many “games of chance,” it is assumed based on symmetry principles that all outcomes are equally likely. From this assumption we infer a rule for the probability measure $P[-]$.

$$P[A]=\frac{|A|}{|S|}$$

In words: the probability of event $A$ is the number of outcomes in $A$ divided by the total number of possible outcomes.

When this formula applies, it is important to be able to count the total outcomes as well as the outcomes that satisfy various conditions.

Permutations

Permutations count the number of ordered lists one can form from a set of items. For a list of $r$ items taken from a total collection of $n$ items, the number of permutations is:

$$P(n,r)=\frac{n!}{(n-r)!}$$

Why is this formula true?

There are $n$ choices for the first item. Then $n-1$ for the second item, after the first has been chosen and removed from the set of possibilities. Then $n-2$ for the third, then …, then $n-r+1$ for the $r^{\text{th}}$ item. So the total number of possibilities is the product:

$$n(n-1)(n-2)\cdots (n-r+1)$$

We can express this with factorials using a technical observation:

$$\begin{array}{c}\frac{n!}{(n-r)!}=\frac{n(n-1)(n-2)\cdots (n-r+1)(n-r)(n-r-1)\cdots 1}{(n-r)(n-r-1)\cdots 1}\\ \\ \gg \gg n(n-1)(n-2)\cdots (n-r+1)\end{array}$$

Combinations

Combinations count the number of subsets (ignoring order) one can form from some items. For a subset of $r$ items taken from a total collection of $n$ items, the number of combinations is:

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

This formula can be derived from the formula for permutations.

The set of possible permutations can be partitioned into combinations: each combination determines a subset. By additionally specifying an ordering of the elements in a chosen subset, we obtain a permutation. For a given subset of $r$ elements taken from $n$ items, there are $r!$ ways to determine an ordering of them in a list. Therefore, the number of permutations must be a factor of $r!$ times the number of combinations. (For every combination of size $r$, there are $r!$ ways to order the items in a list.)

The notation $\left(\genfrac{}{}{0ex}{}{n}{r}\right)$ is also called the binomial coefficient because it provides the coefficient values of a binomial expansion:

$$(x+y{)}^n=\sum _{i=1}^n(\genfrac{}{}{0ex}{}{n}{i})x^{n-i}{y}^i$$

For example:

$$(x+y{)}^4=x^4+4x^{3}y+6x^2{y}^2+4x{y}^3+y^4$$

There are also higher combinations that give multinomial coefficients:

Multinomial coefficient

The general multinomial coefficient is defined by the formula:

$$\left(\genfrac{}{}{0ex}{}{n}{r_1,r_2,\dots ,r_k}\right)=\frac{n!}{r_1!r_2!\cdots r_k!}$$

where $r_i\in \mathbb{N}$ and $r_1+r_2+\cdots +r_k=n$.

The multinomial coefficient measures the number of ways to partition $n$ items into subsets with sizes $r_1,r_2,\dots ,r_k$, respectively.

Notice that $\left(\genfrac{}{}{0ex}{}{5}{3,2}\right)=\left(\genfrac{}{}{0ex}{}{5}{3}\right)$, so we have already defined these values (i.e. with $k=2$) when we defined binomial coefficients. But when $k>2$, the formula gives new values. They correspond to the coefficients in multinomial expansions. For example, $k=3$ gives the coefficients for $(x+y+z{)}^n$.

Link to original

Illustration

Practice exercise

Counting teams with Cooper

A team of 3 student volunteers is formed at random from a class of 40. What is the probability that Cooper is on the team?

Solution

There are $\left(\begin{array}{c}39\\ 2\end{array}\right)$ teams that include Cooper, and $\left(\begin{array}{c}40\\ 3\end{array}\right)$ teams in total. So we have:

$$P=\frac{39!}{2!37!}/\frac{40!}{3!37!}=\frac{3}{40}$$

Link to original

Example - Counting VA license plates

Counting VA license plates

VA license plates have three letters (with no I, O, or Q) followed by four numerals. A random plate is seen on the road.

(a) What is the probability that the numerals occur in strictly increasing order?

(b) What is the probability that at least one number is repeated?

Solution

(a) Numerals in increasing order.

(1) Count total plates:

• Have $23\cdot 23\cdot 23$ options for letters.
• Have $10\cdot 10\cdot 10\cdot 10$ options for numbers.

Thus $23^3\cdot 10^4$ possible plates.

---

(2) Count ways to have 4 numerals that occur in increasing order:

There are $\left(\genfrac{}{}{0ex}{}{10}{4}\right)$ ways to choose 4 distinct numerals from 10 options.

For each choice of four distinct numerals (i.e. for each combination), there is exactly one ordering that’s increasing.

Therefore, there are $\left(\genfrac{}{}{0ex}{}{10}{4}\right)$ ways to have 4 numerals that occur in increasing order.

---

(3) Count ways to have a list of 3 letters (excluding I, O, Q).

There are 26 total letters, 3 are excluded, thus 23 options for each letter.

Repetition is allowed, thus we have $23\cdot 23\cdot 23=23^3$ total ways.

---

(3) Compute probability:

Total count of desired plates (taking the product of possibilities):

$$23^3\cdot \left(\genfrac{}{}{0ex}{}{10}{4}\right)$$

Let $E$ label the event that a plate has increasing numerals. The counting formula for probability is:

$$P[E]=\frac{|E|}{|S|}$$

Evaluate using our data:

$$P[E]\gg \gg \frac{23^3\cdot \left(\genfrac{}{}{0ex}{}{10}{4}\right)}{23^3\cdot 10^4}\gg \gg \frac{\frac{10!}{4!6!}}{10000}\gg \gg \frac{21}{1000}$$

---

(b) At least one number repeated.

“At least” is hard to work with! Lots of ways that can happen.

Try the complement event, which is much simpler: “no repetition”

Let $E^c$ be event that no numbers are repeated. All are distinct. Then $E$ is our desired event.

Count the possibilities:

$$|E^c|=23\cdot 23\cdot 23\cdot 10\cdot 9\cdot 8\cdot 7$$

The total number of plates is still $23^3\cdot 10^4$.

Therefore, license plates with at least one number repeated:

$$\begin{array}{c}|E|=|S|-|E|\\ \\ \gg \gg 23^3\cdot 10^4-23^3\cdot 10\cdot 9\cdot 8\cdot 7\gg \gg 60348320\end{array}$$

Desired outcomes over total outcomes:

$$\frac{|E|}{|S|}\gg \gg \frac{60348320}{23^3\cdot 10^4}\gg \gg 0.496$$ Link to original

Example - Combinations: Groups with Haley and Hugo

Haley and Hugo from 2 groups of 3

A UVA class has 40 students. Suppose the professor chooses 3 students on Wednesday at random, and again 3 on Friday. What is the probability that Haley is chosen today and Hugo on Friday?

Solution

(1) Count total outcomes:

• We have $\left(\genfrac{}{}{0ex}{}{40}{3}\right)$ possible groups chosen Wednesday.
• We have $\left(\genfrac{}{}{0ex}{}{40}{3}\right)$ possible groups chosen Friday.

Therefore $\left(\genfrac{}{}{0ex}{}{40}{3}\right)\times \left(\genfrac{}{}{0ex}{}{40}{3}\right)$ possible groups in total. (Product of possibilities.)

---

(2) Count desired outcomes:

The possible groups of 3 that include Haley can be counted by counting the subgroups of 2 formed of the other students in Haley’s group.

• Therefore we have $\left(\genfrac{}{}{0ex}{}{39}{2}\right)$ groups that contain Haley.
• Similarly, we have $\left(\genfrac{}{}{0ex}{}{39}{2}\right)$ groups that contain Hugo.

Therefore we count $\left(\genfrac{}{}{0ex}{}{39}{2}\right)\times \left(\genfrac{}{}{0ex}{}{39}{2}\right)$ total desired outcomes.

---

(3) Compute probability:

Let $E$ label the desired event. By the counting rule:

$$P[E]=\frac{|E|}{|S|}$$

Evaluate using our data:

$$\begin{array}{c}P[E]\gg \gg \frac{\left(\genfrac{}{}{0ex}{}{39}{2}\right)\times \left(\genfrac{}{}{0ex}{}{39}{2}\right)}{\left(\genfrac{}{}{0ex}{}{40}{3}\right)\times \left(\genfrac{}{}{0ex}{}{40}{3}\right)}\\ \\ \gg \gg {\left(\frac{\frac{39\cdot 38}{2!}}{\frac{40\cdot 39\cdot 38}{3!}}\right)}^2\gg \gg {\left(\frac{3}{40}\right)}^2\end{array}$$ Link to original

Counting out 4 teams

Counting out 4 teams

A board game requires 4 teams of players. How many configurations of teams are there out of a total of 17 players if the number of players per team is 4, 4, 4, 5, respectively.

Solution

This is just the multinomial coefficient with this data:

$n$	$r_1$	$r_2$	$r_3$	$r_4$
17	4	4	4	5

So we have:

$$\#\text{teams}=\frac{n!}{r_1!r_2!r_3!r_4!}\gg \gg \frac{17!}{4!4!4!5!}\gg \gg 214414200$$

Link to original

Repeated trials

Theory

Theory 1

Repeated trials

When a single experiment type is repeated many times, and we assume each instance is independent of the others, we say it is a sequence of repeated trials or independent trials.

The probability of any sequence of outcomes is derived using independence together with the probabilities of outcomes of each trial.

---

A simple type of trial, called a Bernoulli trial, has two possible outcomes, 1 and 0, or success and failure, or $T$ and $F$. A sequence of repeated Bernoulli trials is called a Bernoulli process.

• Write sequences like $TFFTTF$ for the outcomes of repeated trials of this type.
• Independence implies

$$P[TFFTTF]=P[T]\cdot P[F]\cdot P[F]\cdot P[T]\cdot P[T]\cdot P[F]$$

• Write $p=P[T]$ and $q=P[F]$, and because these are all outcomes (exclusive and exhaustive), we have $q=1-p$. Then:

$$P[TFFTTF]\gg \gg pqqppq\gg \gg p^3{q}^3$$

• This gives a formula for the probability of any sequence of these trials.

---

A more complex trial may have three outcomes, $A$, $B$, and $C$.

• Write sequences like $ABBACABCA$ for the outcomes.
• Label $p=P[A]$ and $q=P[B]$ and $r=P[C]$. We must have $p+q+r=1$.
• Independence implies

$$P[ABBACABCA]\gg \gg pqqprpqrp\gg \gg p^4{q}^3{r}^2$$

• This gives a formula for the probability of any sequence of these trials.

---

Let $S$ stand for the sum of successes in some Bernoulli process. So, for example, “$S=3$” stands for the event that the number of successes is exactly 3. The probabilities of $S$ events follow a binomial distribution.

Suppose a coin is biased with $P[H]=20\%$, and $H$ is ‘success’. Flip the coin 20 times. Then:

$$P[S=3]\gg \gg \left(\genfrac{}{}{0ex}{}{20}{3}\right)\cdot (0.2{)}^3\cdot (0.8{)}^{17}$$

Each outcome with exactly 3 heads and 17 tails has probability $(0.2{)}^3\cdot (0.8{)}^{17}$. The number of such outcomes is the number of ways to choose 3 of the flips to be heads out of the 20 total flips.

The probability of at least 18 heads would then be:

$$\begin{array}{c}P[S\ge 18]\gg \gg P[S=18]+P[S=19]+P[S=20]\\ \\ \gg \gg \left(\genfrac{}{}{0ex}{}{20}{18}\right)\cdot (0.2{)}^{18}\cdot (0.8{)}^2+\left(\genfrac{}{}{0ex}{}{20}{19}\right)\cdot (0.2{)}^{19}\cdot (0.8{)}^1+\left(\genfrac{}{}{0ex}{}{20}{20}\right)\cdot (0.2{)}^{20}\cdot (0.8{)}^0\end{array}$$

---

With three possible outcomes, $A$, $B$, and $C$, we can write sum variables like $S_A$ which counts the number of $A$ outcomes, and $S_B$ and $S_C$ similarly. The probabilities of events like $\text{“}(S_A,S_B,S_C)=(2,3,5)\text{”}$ follow a multinomial distribution.

Link to original

Illustration

Example - Multinomial: Soft drinks preferred

Multinomial: Soft drinks preferred

Folks coming to a party prefer Coke (55%), Pepsi (25%), or Dew (20%). If 20 people order drinks in sequence, what is the probability that exactly 12 have Coke and 5 have Pepsi and 3 have Dew?

Solution

The multinomial coefficient $\left(\genfrac{}{}{0ex}{}{20}{12,5,3}\right)$ gives the number of ways to assign 20 people into bins according to preferences matching the given numbers, $C=12$ and $P=5$ and $D=3$.

Each such assignment is one sequence of outcomes. All such sequences have probability $(0.55{)}^{12}\cdot (0.25{)}^5\cdot (0.2{)}^3$.

The answer is therefore:

$$\left(\genfrac{}{}{0ex}{}{20}{12,5,3}\right)\cdot (0.55{)}^{12}\cdot (0.25{)}^5\cdot (0.2{)}^3\gg \gg \frac{20!}{12!5!3!}\cdot (0.55{)}^{12}\cdot (0.25{)}^5\cdot (0.2{)}^3$$Link to original

Hypergeometric

Problem

01

Hypergeometric distribution: male chickens

It is notoriously difficult to determine the sex of a chicken before it matures. Suppose that a randomly chosen chick from a pen of $N$ chicks is male with probability $1/3$. Suppose you draw $n$ chicks from the pen. Do the odds that $k$ of them are male depend upon the value of $N$?

Link to original

Reliability

Theory

Theory 1

Consider some process schematically with components in series and components in parallel:

• Each component has a probability of success or failure.
• Event $W_i$ indicates ‘success’ of that component (same name).
• Then $P[W_i]$ is the probability of $W_i$ succeeding.

---

Success for a series of components requires success of each member.

• Series components rely on each other.
• Success of the whole is success of part 1 AND success of part 2 AND part 3, etc.

Failure for parallel components requires failure of each member.

• Parallel components represent redundancy.
• Success of the whole is success of part 1 OR success of part 2 OR part 3, etc.

For series components, stack successes:

$$P[W]=P[W_1{W}_2{W}_3]=P[W_1]\cdot P[W_2]\cdot P[W_3]$$

For parallel components, stack failures:

$$\begin{array}{c}P[W^c]=P[W_1^c{W}_2^c{W}_3^c]\\ \\ \gg \gg (1-P[W_1])(1-P[W_2])(1-P[W_3])\end{array}$$

E.g. if $P[W_i]=p$ for all components $i$, then:

• Series components: $P[W]=p^3$
• Parallel components: $P[W]=1-(1-p{)}^3$

---

To analyze a complex diagram of series and parallel components, bundle each:

• pure series set as a single compound component with its own success probability (the product)
• pure parallel set as a single compound component with its own success probability (using the failure formula)

This is like the analysis of resistors and inductors.

Link to original

Illustration

Example - Series, parallel, series

Reliability: Series, parallel, series

Suppose a process has internal components arranged like this:

Write $W_i$ for the event that component $i$ succeeds, and $W_i^c$ for the event that it fails.

The success probabilities for each component are given in the chart:

1	2	3	4	5
92%	89%	95%	86%	91%

Find the probability that the entire system succeeds.

Solution

For intersections, use $P[AB]=P[A]P[B]$ (independence) and for unions, use $P[A\cup B]=1-P[A^c{B}^c]$.

So $P[(W_2{W}_3{)}^c]=1-(.89)(.95)$ and:

$$\begin{array}{c}\text{success}=W_1(W_2{W}_3\cup W_4\cup W_5)\\ \\ \gg \gg P[\text{success}]=(.92)(1-(1-(.89)(.95))(.14)(.09))\gg \gg \approx 0.918\end{array}$$Link to original