For easier and less intimidating viewing, better use a bigger display. Unless you're watching a video or recalling something
The problems from the previous lesson primarily focused on counting, revolving mostly around "counting combinatorics". While we did introduce a few new terms, such as "probability model", these weren't new tools for solving problems or groundbreaking theorems. They were simply additions to our mathematical vocabulary. This is an important point, as well as a helpful way of looking at things here. I.e even though "Probability Theory" is ultra-applicable for solving many real-world problems, on a foundational level, the so-called "Discrete Probability Theory" (i.e not picking a point on an interval, or in a square) is just combinatorics: you count things, find the ratio of a particular type of combinations among the whole set of combinations and so on...
We are yet to put our new vocabulary in some use, in particular see how come probability theory is so applicable in real-life. We will get there, don't worry. But today we will stress the point above, in particular we will see yet again that even though the word "random" (or its synonyms) is used quite a lot in probability theory, there is no "randomness" involved in the maths behind it! It is all deterministic from the maths point of view.
This lesson will be mostly about problem-solving, and here a few comments before we move on to doing them:
Exercise 1.
An 8-digits number is picked at random. What is the chance that this number has at least one digit 4 in its decimal representation?
Explanation and comments
click on blur to reveal
The main idea of this exercise is to realise that the answer is $1 - \mathbb{P}$(no fours in decimal representation). Before we get to the answer though, let's clarify the Probability Model:
See, it does not take long to clarify this important bit :) Anyway, note that there are $8 \cdot 9^7$ eight-digits numbers which don't have digit 4 in their decimal representation. From here, it is easy to derive that the answer is
\[ 1 - \mathbb{P}(\text{no fours in decimal representation}) = 1 - \frac{8 \cdot 9^7}{9 \cdot 10^7} \]
Exercise 2.
A fair die is rolled 60 times. What is the probability that you will see 1 precisely 10 times?
Explanation and comments
click on blur to reveal
First of all, let's clearly define our probability model:
Now, all we need to calculate is the number of combinations in which there are precisely $10$ ones. This is not difficult if you are on good terms with standard counting combinatorics (which is a prerequisite for this lesson): there are $\binom{60}{10} \cdot 5^{50}$ such combinations. Therefore the final answer is \[ \frac{\binom{60}{10} \cdot 5^{50}}{6^{60}} \]
Exercise 3.
The letters of the word BEAR are mixed and then laid out in a random order. What is the probability that the same word is laid out? What if the word is BEER? What if its ABRACADABRA?
For this question especially: please specify your probability model clearly!
Explanation and comments
click on blur to reveal
Interestingly, there are two ways to construct a reasonable uniform probability model for this question. They are similar and both will lead to the same answers, but they are not exactly the same! In particular, one could argue that one is not as "reasonable" as the other ones. Here they are:
These two models are different, they have different number of simple events in some cases! Which one would you call "more reasonable"? I would argue, that the first one is, since it feels more natural to consider permutations of letters as a permutation of cards where all of the outcomes are equally likely. As for the second model: why would you say that all of the possible words you can get are "equally likely" (i.e symmetric)? Is it really that trivial and intuitive? So let us stick to the first model and le'ts solve the problem then:
Exercise 4.
Ellina has twelve blocks, two each of red (R), blue (B), yellow (Y), green (G), orange (O), and purple (P). Call an arrangement of blocks even if there is an even number of blocks between each pair of blocks of the same color, for example, the arrangement
{R B B Y G G Y R O P P O} is even. Ellina arranges her blocks in a row in random order. Find the probability that her arrangement is even.
Explanation and comments
click on blur to reveal
Unlike the problems from before, this one requires an insight. Consider labeling the positions where blocks can be placed as 1 through 12. To satisfy the requirement that there must be an even number of spaces between each pair of spots of the same color, the odd-numbered positions (1, 3, 5, 7, 9, 11) must contain a permutation of all six colored blocks. Similarly, the even-numbered positions (2, 4, 6, 8, 10, 12) must contain another set of six blocks of different colors.
On the other hand, by placing six differently colored blocks in the odd-numbered positions and another six in the even-numbered positions, we achieve an even configuration. Thus, the number of even configurations is $6! \cdot 6!$. The total number of possible arrangements of blocks is $\frac{12!}{(2!)^6}$, therefore the probability of achieving an even arrangement under the uniform probability model is: \[ \frac{6!\cdot6!}{12! / (2!)^6} \]
Exercise 5.
There are 35 children are in a class. Show that the probability two of them having a birthday the same day is greater than $\frac{1}{2}$.
You can assume that there are 365 possible birthdays and each day is equally likely to be someone’s birthday. But just so you know – this assumption is not true in reality... If you struggle to prove it, feel free to look up "Stirling's Approximation".
Explanation and comments
click on blur to reveal
First of all, without going through details like probability model and simple events, the answer is this: $1-\frac{365 \cdot 364 \cdot ... \cdot 331}{365^{35}}$.
Now, how do we show that $\frac{365 \cdot 364 \cdot ... \cdot 331}{365^{35}}$ is larger than a half (from where the conclusion will follow)? Both the denominator and the numerator are huge numbers, so what do we do? One of the ways, is to use a so-called Stirling's Approximation. In its simple form, it says that \[ n! \approx \sqrt{2\pi n} \cdot (n/e)^n .\] Yeap, the famous constants $\pi$ and $e$ both play a role here! But you do not really have to know much about them, maybe only the approximate value of $\pi$ (the $e$-s will cancel out in this problem). Surprisingly, this approximation is good even for small $n$, it is always a slight underestimate: \begin{array}{c|c|c|c} & n! & \text{Approximation} & \text{Ratio} \\\hline1 & 1 & 0.922 & 1.084 \\2 & 2 & 1.919 & 1.042 \\3 & 6 & 5.836 & 1.028 \\4 & 24 & 23.506 & 1.021 \\5 & 120 & 118.019 & 1.016 \\6 & 720 & 710.078 & 1.013 \\7 & 5040 & 4980.396 & 1.011 \\8 & 40320 & 39902.395 & 1.010 \\9 & 362880 & 359536.873 & 1.009 \\10 & 3628800 & 3598696.619 & 1.008 \\ \end{array}
It is totally fine if you do not know how to formalise the "approximately equal" (which involves talking about the limits of things). We do not expect you to at this stage. It is okay if you simply think about this result as "an approximately equal" without knowing how to formalise it or how to bound the ratio of $n!$ and the formula.
By the way, here are two interesting remarks on the exercise itself:
1) Even if there are just 23 students in a classroom, it is already true that the probability of two of them sharing a birthday is larger than 0.5. In fact: \begin{array}{c|c|c|c|c|c|c|c|c|c} n = 1 & n = 5 & n = 10 & n = 20 & n = 23 & n = 30 & n = 40 & n = 50 & n = 60 & n = 70 \\\hline 0.0\% & 2.7\% & 11.7\% & 41.1\% & 50.7\% & 70.6\% & 89.1\% & 97.0\% & 99.4\% & 99.9\% \\ \end{array}
2) Also, the probability of finding a triple with the same birthday exceeds 0.5 for $n \geq 88$.
We've practiced solving combinatorial problems that look like probability problems. The next step is to solve a bit more of these in the Problem Set and, if you get to it, Extra.