Exercises C.2-10

Three prisoners problem.
Six cases, which upper case means which one will be executed, and the name in bracket is guard’s answer.
Case 1: X Y z [Y]
Case 2: X Y z [Y]
Case 3: X y Z [Z]
Case 4: X y Z [Z]
Case 5: x Y Z [Y]
Case 6: x Y Z [Z]

In the original, the probability of X is 2/3. After guard telled Y is executed, the probability is the same.

Exercises C.2-9

Monty Hall Problem.
Not change = 1/3
Change = 2/3

Exercises C.2-8

Toss two biased coins. Let A be the first coin’s outcome, B be the second coin’s outcome. Since coins are biased, A and B are dependent. Therefore, let C be the coin baised toward head. If C is given, then A and B are independent.

Exercises C.2-7

Solution wanted!

Exercises C.2-6

Principle of deferred decisions.
Proof by induction.
Base case: = .
Induction case: Assume that for all n < k. Then .

Exercises C.2-5

= = 1

Exercises C.2-4

Solution wanted!

Exercises C.2-3

= 1/6

Exercises C.2-2

The only possibility is R: Head G: Tail, Tail. The probability is 1/8.

Exercises C.2-1

Union bound.
Proof by induction.
Base case: .
Induction step: Assume that for all n < k.
Then = = .