### Basic probability. Counting. Generating random numbers.

`#basic-probability`

**Problem #1.1**

How can you generate random numbers `1`

to `7`

with a single die?

Or more formally, you're given a random integer generator that outputs integers `1 2 3 4 5 6`

. Describe a procedure that uses this generator to generate a random number between `1`

and `7`

.

**Problem #1.2**

You're given a procedure `random01`

that outputs `0`

or `1`

with equal probability. How can you use it to generate random numbers between `0`

and `9`

?

**Problem #1.3**

Given a biased coin (ie. heads and tails don't have the same probability), how can you use it to simulate a fair coin toss?

**Problem #1.4**

There are two balls in a bag. I tell you that at least one of them is red. What is the probability that both are red? (Solution)

**Problem #1.5**

In how many ways can you divide 12 people into 3 groups of 4?

**Problem #1.6**

Take 2 random chords of a circle. What is the probability that they intersect?

### Laws of probability. Random variables.

**Problem #2.1**

You have `N`

locks, labeled `1`

to `N`

each with a corresponding key. Unfortunately, you lost all the labels from the keys, so you decide to relabel the keys with unique random labels from `1`

to `N`

.

What is the expected number of keys that end up with a correct label?

**Problem #2.2**

You're given an array `A`

of real numbers, sampled from $Uniform(0, 1)$.

Let's consider the following algorithm for finding the maximum of the array:

```
max := -1
for i in 0 .. length(A) {
if A[i] > max {
max := A[i]
}
}
```

What is the expected number of times the `max`

variable will be updated? That is, what is the expected number of times the line `max := A[i]`

is executed?

**Problem #2.3**

A disease has a *base rate* of 1 in 1000 (ie. 1 in 1000 people in a population will have the disease). Let's say you take a test that has 97% *true positive* rate, and 3% *false positive* rate.

You just tested positive - what is the probability that you actually have the disease?

**Problem #2.4**

You're drawing cards from a shuffled deck. How many cards do you *expect* to draw before drawing the first ace?

### Probability flavoured algorithms

**Problem #3.1**

Given a function `F(x)`

returning the value of a cumulative distribution function of a continuous random variable $X$, implement a function `sample(F)`

that returns a sample of $X$.

**Problem #3.2**

Given a circle centered at $(x, y)$ with radius $r$, implement a function `random_point(x, y, r)`

that returns a random point inside this circle.

**Problem #3.4**

Given a function `Bernoulli()`

that returns `0`

or `1`

with equal probability, write a function `Normal(mean, std)`

that returns a random sample from a Normal distribution with mean `mean`

and standard deviation `std`

.