Monte Carlo Methods - Prof Dulla - Appunti di Fabio Galizia

Corso di laurea magistrale in Monte Carlo methods

Prof. Sandra Dulla

Appunti di Fabio Galizia

Lezione 1

Basic of probability, Kolmogoroff axiom

Lezione 2

Conditional probability, total probability formula, Bayes formula, random variable, cumulative function, PDF

Lezione 3

Exercise session 1 – October 21, 2016

Basics on probability

Example from the movie 21 (just to start ...)

In a TV game, the participant can choose among three boxes, one containing the prize and the other two empty. Once the participant has made his choice, the game master, who knows where the prize is, opens the box among the other two which is empty. At this point, the participant can choose to stick with his box or change, taking the remaining one. Which is the best choice to make in order to win?

Definition of events:

• P[A] = probability the prize is in box 1
• P[B] = probability the prize is in box 2
• P[C] = probability the prize is in box 3

Since we have no other info, the three probabilities are the same, the three events are mutually exclusive (only one prize) and exhaustive, therefore \( P[A] = P[B] = P[C] = \frac{1}{3} \).

Let's suppose we choose box 1, we have thus \(\frac{1}{3}\) probability of winning, and \(\frac{2}{3}\) probability of losing, that is in other words: If we change box we increase probability to win \(\frac{2}{3}\).

\( P[B \cup C] = P[B] + P[C] = \frac{2}{3} \)

I can sum the probability because the events are mutually exclusive. If the game master opens the empty box between 2 and 3, still the probabilities \( P[A] = \frac{1}{3} \) are unmodified (the statistical characteristics of the problem are still these!), and if I keep my choice of box A I still have \(\frac{1}{3}\) probability of winning. Instead, if I change the box and pick the remaining one between 2 and 3, this option preserves the \(\frac{2}{3}\) probability of winning, because it is "as if" I chose both the boxes 2 and 3. Therefore, it is better to change.

Basic principle of counting

Ex 3.5.3 Ross (to show how statistics challenges our common sense)

If n persons are gathered in a room, how much is the probability that all people have their birthday on a different day? How large the number n needs to be in order to have this probability below 50%?

To solve this problem we consider that the probability of being born in any day of the year has the same probability, so each person has 365 options, all equally probable:

\( P[\text{one person}] = \frac{1}{365} \)

We neglect the leap year. Based on the fact that we are dealing with equally probable events, we evaluate the probability requested as the ratio of the favorable configurations over all the possible configurations. Since each person can be born in any day of the year,

• Number of possible configurations: \(365^n\)

and to combine all these cases we use the basic principle of counting multiplications of number of possible cases.

• Number of favorable configurations: again we apply the counting principle: 365 cases

- The first person interviewed can be born in any day of the year.

- The second person, to fulfill the requirement, cannot be born on the same day as the first, so he/she is left with 364 options.

- With the same logic the third has 363 options and so on ...

We apply the basic principle of counting and obtain: \(365 \cdot 364 \cdot 363 \cdot \ldots \cdot (365-n+1)\).

We then obtain the result:

\(\frac{365 \cdot 364 \cdot \ldots \cdot (365-n+1)}{365^n}\)

Interesting fact: this probability becomes less than 50% with n=23 (smaller number than what you would have thought) and for n=50 it is just 3%.

Ex from final (to show that sometimes is better to evaluate the complementary)

You are going to a restaurant that offers 4 main dishes, 3 side salads and 5 desserts. In one of the salads there are peanuts, as well as in 2 desserts, and you are allergic to peanuts. If you let the chef decide a menu of three courses (main dish + salad + dessert) for you, what is the probability that this dinner will send you to the hospital?

Since no info is given on how the menu is composed by the chef, we suppose a random choice so that each dish of the same category is equally probable. We use the basic principle of counting:

• Total possible configurations (menu): 4 mains · 3 sides · 5 desserts = 60

Since you go to the hospital with at least one dish with peanuts, but also with more than one, various configurations should be considered, and it becomes easy to forget something along the way. Better to evaluate the complementary event: no peanuts in the menu.

• Number of configurations with no peanuts: 4 mains · 2 sides · 3 desserts = 24

Therefore \( \frac{24}{60} \) is the probability of NOT going to the hospital and \( \frac{36}{60} \) is the probability requested.

At home: try to solve the same exercise evaluating directly the probability requested.

Binomial coefficient

Ex 3.5.6 Ross

A basketball team is composed of 6 white players and 6 black players (ok, I should say Caucasian and Afroamerican, I am not politically correct just to make it simple). They go to a different town for a match and need to be divided into twos to fit in the double hotel rooms. Assuming a random subdivision, how much is the probability no black guy is in the same room with a white guy?

To solve the problem we "simulate" the process of picking the players randomly and place them in the rooms starting from the first to the sixth. Again we deal with equally probable events, so we take the ratio of the favorable configurations to the total and we use the principle of counting to obtain these two numbers.

Total possible configurations: \(\binom{12}{2} \binom{10}{2} \binom{8}{2} \binom{6}{2} \binom{4}{2} \binom{2}{2} = \frac{12!}{2^6 \cdot 6!}\)

Starting from the first room, we have 12 players available and different ways of picking two of them to fill the first room (i.e. couples composed by different persons). Then 10 people are left, we move to the second room and we have different ways of filling it. We proceed up to the last room, and the product of all these binomial coefficients account for all the different configurations ...

But with this procedure, we have distinguished one room from the other (room 1, room 2 ...) and so we have counted as different two configurations where the same couples have been formed and they have just been placed in a different room:

Example with just 4 people (A, B, C and D): we have counted as two different cases (room1: A and B room2: C and D) and (room1: C and D room2: A and B), that is the same case for our problem, since we are requested to focus only on the composition of the rooms, that are not distinguishable. So we need to divide by all the possible permutations of the 6 rooms, (6!)

\(\frac{12!}{2^6 \cdot 6!}\)

Now we calculate the number of favorable configurations (configurations fulfilling the request) with the same logic: we start from room1 and fit two white guys, the possible different ways of doing it are \(\binom{6}{2}\), then for room2 is \(\binom{4}{2}\) and the last two in room3. To account for the permutations of the rooms, as before, we divide by (3!)

And the same is done for the blacks, getting to the result

\(\left(\frac{\binom{6}{2} \binom{4}{2} \binom{2}{2}}{3!}\right)^2 = \frac{1}{90}\)

The ratio of these two numbers gives the probability of having rooms with only people of the same color, and this number is around 2%.

Statistical independent events

Exercise from finals

You go buy scratch cards (gratta e vinci). You know that:

• 1 card out of 2 will make you win 10 €
• 2 cards out of 10 will make you win 50 €
• 1 card out of 10 will make you win 100 €

If you buy two scratch cards, what is the probability that you will win at least 100 €?

First thing is to define correctly the events for which we have information on probability, and then identify the event to be evaluated.

• P[10€] = P[1/2]
• P[50€] = P[2/10]
• P[100€] = P[1/10]

Each purchase of a scratch card is an event that is statistically independent from the other, so the two events considered have the properties of statistically independent events: the probability of the intersection is the product of probability.

There are many ways of winning at least 100€ with two scratch cards, and the probability of each possible way has to be summed to consider the union of all these events. The single event is itself the intersection of two events, and the corresponding probabilities are to be multiplied. The only difficulty is not to forget some cases, especially remembering that (A_i, A_j) is a different event from (A_j, A_i), when i≠j:

• P[100€] = 1/10
• P[10€ ∩ 100€] = (1/2) * (1/10)
• P[50€ ∩ 50€] = (2/10) * (2/10)
• P[50€ ∩ 100€] = (2/10) * (1/10)
• P[100€ ∩ 100€] = (1/10) * (1/10)

The sum of these probabilities gives 0.23.

Note: this is the same statistical situation of rolling two dice with only four sides (0, 10, 50, and 100), not balanced (different probability for each side), and the probability requested is to get at least 100.

Exercise on sequence of statistically independent events

Analysis of the various situations that may occur when gambling. If I play one single number at the roulette the probability of winning is:

\( P[\text{number}] = \frac{1}{37} \)

And the probability that the number does not come out is the complementary:

\( P[\text{not number}] = \frac{36}{37} \)

Case 1: probability of winning two times in a row

Each round is statistically independent from the other:

\( P[\text{win two times}] = \left(\frac{1}{37}\right)^2 = 0.0007 \)

Case 2: probability of playing 4 times and winning only once

Need to consider all different sequences:

• P[win once in 4] = 4 * \(\left(\frac{1}{37}\right) * \left(\frac{36}{37}\right)^3\) = 0.0996

Case 3: probability of playing 4 times and winning once at the fourth time

\( P[\text{win once at fourth}] = \left(\frac{36}{37}\right)^3 * \left(\frac{1}{37}\right) = 0.0249 \)

Case 4: probability of playing 4 times and winning at least once

Easier to evaluate complementary, because many different cases should be considered:

\( P[\text{win at least once}] = 1 - \left(\frac{36}{37}\right)^4 = 0.1038 \)

Note: this case includes Case 2 + all the situations where you win more than once.

At home: try to solve the same exercise evaluating directly the probability requested.

Case 5: probability of winning, having decided to play a maximum of 4 times and to stop the moment you win once

\( P[\text{win in max 4}] = \left(\frac{1}{37}\right) + \left(\frac{36}{37}\right) * \left(\frac{1}{37}\right) + \left(\frac{36}{37}\right)^2 * \left(\frac{1}{37}\right) + \left(\frac{36}{37}\right)^3 * \left(\frac{1}{37}\right) = 0.1038 \)

Note: it converges to one with infinite tries ... and it is statistically equivalent to Case 4! The equivalence is clear if you factorize P[W] from the expression of Case 5 and remember that P[W]=1-P[W^c].

Total probability formula

Exercise from finals

The Monte Carlo Methods students can take the exam in three sessions (winter, summer, and fall).

• 55% of the students take the exam for the first time in the winter session, 25% in the summer session, and the rest in the fall session.
• The students taking the exam for the first time in the winter session pass it with a 63% probability, while the students coming in the summer session have a 45% probability of passing it. The students of the fall session pass the exam with a 74% probability.

What is the probability that a student passes the exam the first time he tries it?

First define properly the input data:

• P[winter] = 0.55
• P[summer] = 0.25
• P[fall] = 0.20

These three events are mutually exclusive and exhaustive.

Typical problem involving conditional probabilities:

• P[pass | winter] = 0.63
• P[pass | summer] = 0.45
• P[pass | fall] = 0.74

The requested probability is a total probability that can be obtained from the data available through the total probability formula:

P[pass] = 0.63 ∙ 0.55 + 0.45 ∙ 0.25 + 0.74 ∙ 0.20 = 0.607

Note: always have a critical analysis of the results you obtain; the result here has to be included in the range of the conditional probabilities involved, if you find something larger than 0.74 or smaller than 0.45 you made the calculations wrong.

Bayes formula

Ex 1.23 Vicario Levi (explain the misleading/mistake on the book)

A medical test to diagnose a rare disease has the following performance:

• Sensitivity: the test is positive for 95% of the cases affected
• Morbidity: this disease affects 0.5% of the population
• False positive: the test is positive even though the patient is healthy in 4% of the cases (THIS DATA IS NOT GIVEN IN THE BOOK AND IS INDUCED INCORRECTLY FROM THE OTHER DATA!)

Question: Probability of getting a correct diagnosis for a patient (i.e., the probability that, being the test positive, the patient is actually sick in reality).

Let us define correctly the events and probabilities involved:

• A = person is sick
• T = test is positive

P[A] = 0.005 (Morbidity)

P[T | A] = 0.95 (Sensitivity)

P[T | not A] = 0.04 (False positive)