שנה שפה

English

היכנס אל מתיגון

אוֹ

חשבון חדש     אפס הסיסמה     

Probability
by Samuel S. Watson
Introduction
Counting
Probability Models
Random Variables
Probability Distributions
Joint Distributions
Conditional Probability
Independence
Expectation and Variance
Covariance
Continuous Distributions
Conditional Expectation
Common Distributions
Central Limit Theorem

שתף

אפס התקדמות

פעולה זו תמחק את ההתקדמות ואת נתוני הצ'אט עבור כל הפרקים בקורס זה, ולא ניתן לבטל אותה!

מילון מונחים

בחר אחת ממילות המפתח משמאל...

ProbabilityCounting

זמן קריאה: ~30 min

We begin our study of probability with a closely related topic: counting.

We first learn to count the number of elements in a set by mentally traversing it while reciting a sequence of natural numbers: "one, two, three, ...". The last number recited when all elements have been counted is the number of elements in the set. However, that approach quickly becomes impractical if the set is large, and it doesn't yield much insight. Therefore, we will build up a toolkit of principles for reasoning about counting problems.

The fundamental principle of counting

Exercise
If you flip a coin and roll a die, there are possible flip-roll pairs.

This exercise is a special case of the fundamental principle of counting:

Theorem (Fundamental principle of counting)
If one experiment has m possible outcomes, and if a second experiment has n possible outcomes for each of the outcomes in the first experiment, then there are mn possible outcomes for the pair of experiments.

One simple way to prove the fundamental theorem of counting is to observe that the possible outcomes for the pair of experiments can be arranged to form an m\times n rectangle:

\begin{align*}\begin{array}{c|cccccc} & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline \texttt{H} & (\texttt{H},1) & (\texttt{H},2) & (\texttt{H},3) & (\texttt{H},4) & (\texttt{H},5) & (\texttt{H},6) \\ \texttt{T} & (\texttt{T},1) & (\texttt{T},2) & (\texttt{T},3) & (\texttt{T},4) & (\texttt{T},5) & (\texttt{T},6) \end{array}\end{align*}

The fundamental principle of counting may be used to solve problems that have a different setup than the flip-roll problem.

Exercise
The number of ordered triples of distinct elements from \{1,2,3,4\} is .

Solution. This problem is different from the previous one because the choice for which number goes in the first slot in the tuple affects the subsequent choices. If we choose 3 first, then we can't choose it for the second or third slots. However, the number of options for each choice is the same regardless of the previous choices: we have four choices for the first slot, then three for the second (once the first choice has been made), then two for the third. Thus there are 4 \times 3 \times 2 = 24 ordered triples.

So that it's extra clear there's no sleight of hand involved in this argument, here's a graphic organizer for all 24 triples and the choices made along the way:

We can generalize this idea to count the number of ordered r-tuples of distinct elements of an n-element set. We begin forming an r-tuple by selecting any one of the n possibilities for the first entry. Given any of the choices for the first entry, there are n-1 choices for the second entry. By the fundamental principle of counting, there are n(n-1) choices for the first two entries. Continuing in this way, we find that there are

\begin{align*}n(n-1)(n-2) \cdots (n-r+1)\end{align*}

choices for filling in all r entries. We write n(n-1)(n-2) \cdots (n-r+1) as (n)_r, read as "n falling r".

Exercise
There are three-digit positive integers with distinct digits.

Note: a positive integer must be between 100 and 999 (inclusive) to count as a three-digit integer.

Solution. There are 9 choices for the first digit, then for any of those choices there are 9 choices for the second digit. Finally, given any pair of digits in the first two positions, there are 8 choices for the last entry. So there are 9\cdot 9 \cdot 8 = \boxed{648} choices in total.

Binomial coefficients

The number of r-element subsets of an n-element set is denoted \binom{n}{r}. Expressions of the form \binom{n}{r} are called binomial coefficients.

Example
We have \binom{4}{3} = 4, since there are four ways to choose a 3-element subset of a 4-element set. The sets

\begin{align*}\{1,2,3\}, \{1,2,4\}, \{1,3,4\}, \{2,3,4\}\end{align*}

are all of the 3-element subsets of \{1,2,3,4\}.

To work out a general procedure for evaluating \binom{n}{r}, we may first count the number of r-tuples and then account for all of the repeats. For example, if r = 3, then the tuples

\begin{align*}(1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1)\end{align*}

should collectively contribute 1, rather than 6, to the total count. Since every set of r elements corresponds to r(r-1)(r-2)\cdots (2)(1) $r$-tuples of distinct elements, we divide the number of r-tuples by this number to obtain an expression for \binom{n}{r}:

\begin{align*}\binom{n}{r} = \frac{n(n-1)(n-2)\cdots (n-r+1)}{r(r-1)(r-2)\cdots (2)(1)}.\end{align*}

We often abbreviate the product r(r-1)(r-2)\cdots (2)(1) as r!. Thus

\begin{align*}\binom{n}{r} = \frac{(n){}_r}{r!}\end{align*}

Exercise
Of the 1024 total length-10 strings composed of the symbols H and T, of them have exactly 6 T's and 4 H's. (For example, HHTHTTTHTT is one such string).

Solution. For each 6-element subset of the 10 positions in the string, we can place T's in those six positions and H's in the remaining positions to get a sequence of the given description. Therefore, there are \binom{10}{6} = 210 total strings with exactly 6 T's.

Exercise (Principle of Inclusion-Exclusion)
Let \Omega = \{0, 1, 2, \cdots, 100\} be the set of natural numbers up to and including 100. Let A \subset \Omega the subset of integers divisible by 3, and B \subset \Omega the subset of integers divisible by 5.

  • Compute |A|.
  • Compute |B|.
  • Compute |A \cap B|.
  • Explain why |A \cup B| = |A| + |B| - |A \cap B|.
  • Use the prior steps to find |A \cup B|.

Solution.

  • There are 33 multiples of 3 between 1 and 100. Including zero in the count as well, we get |A| = 34.

  • There are 20 multiples of 5 between 1 and 100. Adding 1 to account for zero gives |B| = 21.

  • Elements of A \cap B are zero and multiples of 15 in \Omega. It thus follows that |A \cap B| = 7.

  • |B| - |A \cap B| gives the numer of elements that are in B but not in A. Adding |A| gives the total number of elements in A \cup B.

  • Using values calculated above, we have |A\cup B| = 34 + 21 - 7 = 48.

Exercise
The English alphabet has subsets. (Hint: you can get Bruno to do arithmetic calculations for you!)

For example, \{\mathrm{a}, \mathrm{r}, \mathrm{w}\} and \{\mathrm{d}, \mathrm{g}, \mathrm{m}, \mathrm{x}, \mathrm{y}, \mathrm{z}\} are two such subsets.

Solution. There are 2^{26} = 67{,}108{,}864 subsets of the alphabet, because we can form a subset by choosing for each letter whether to include it or exclude it. By the fundamental principle of counting, the number of ways to make these 26 choices is 2 \times 2 \times \cdots \times 2 = 2^{26}.

Exercise
Expand the algebraic expression (x+y)^3. Show that the coefficients of this expansion are given by the binomial coefficients of the form \binom{3}{r} where r ranges from 0 to 3:

\begin{align*}(x+y)^3 = \binom{3}{0}x^3y^0 + \binom{3}{1}x^2y^1 + \binom{3}{2}x^1y^2 + \binom{3}{3}x^0y^3\end{align*}

Write an analogous expansion for (x+y)^4.

Solution. The first equation holds since both sides work out to (x+y)^3 = x^3 + 3x^2y + 3xy^2 + y^3. The second holds since both sides are equal to

\begin{align*}(x+y)^4 = x^4 + 4x^3y + 6x^2y^2 + 4xy^3 + y^4.\end{align*}

Generally, we have

\begin{align*}(x+y)^n = \binom{n}{0}x^ny^0 + \binom{n}{1}x^{n-1}y^1 + \cdots + \binom{n}{n-1}x^1y^{n-1} + \binom{n}{n}x^0y^3\end{align*}

because a term of the form x^{n-r}y^r is formed when expanding the product (x+y)(x+y)\cdots(x+y) if and only if the x was selected from n-r of the (x+y) factors and y was selected from the remaining r factors. This can happen in \binom{n}{r} ways, so the coefficient of x^{n-r}y^r is \binom{n}{r}.

Bruno
Bruno Bruno