1. The Scheme-- programming language

The Scheme-- programming language is a simplified version of lambda calculus that incorporates the exciting reference (&) and dereference (*) operators from C but otherwise doesn't actually work. Scheme-- expressions are of the form

• <> (the empty string)

• x

• y

• 17

• &α

• *α

• λxα

• λyα

• (α)

where in each case α represents another Scheme-- expression. The lack of variables other than x and y, constants other than 17, and any notion of function application, is a feature of the language, intended to encourage users to write simple (though useless) programs. Some examples of Scheme-- expressions: &*λxy, (**&λyλy(17)), x. These have length 5, 13, and 1, respectively.

Compute the number of Scheme-- expressions of length n.

1.1. Solution

Let F be the generating function for Scheme-- expressions. Observe that F = 1 + 2z + z² + 2zF + 3z²F, since a Scheme-- expression is either an empty sequence (1) one of two variables of length 1 (2z), a constant of length 2 (z²), one of two length-1 operations concatenated with a Scheme-- expression (2zF), or one of three weight-2 structures with a Scheme-- expression attached to it (3z²F; note that it doesn't really matter that the parentheses surround the expression instead of coming before it). Solving for F gives:

The first term gives the sequence 3ⁿ; the second gives 3^n-1, except when n = 0, where it gives 0. So we have 3ⁿ + 3^n-1 = 4⋅3^n-1 Scheme-- expressions of any length n > 0, and 3⁰ = 1 Scheme-- expression of length 0.

(One could also do this with guess-but-verify, but the guessing part might be tricky.)

2. Independent events

Let A and B₁ be independent events, and let A and B₂ also be independent events, on some probability space Ω.

1. Prove or disprove: A and Ω-B₁ are independent events.

2. Prove or disprove: A and B₁∩B₂ are independent events.

3. Prove or disprove: If A and B₁∪B₂ are independent events, then B₁ and B₂ are independent events.

2.1. Solution

Recall that two events A and B are independent if and only if Pr[A∩B] = Pr[A]⋅Pr[B]. We are thus given that Pr[A∩B₁] = Pr[A]⋅Pr[B₁] and Pr[A∩B₂] = Pr[A]⋅Pr[B₂], but otherwise we don't know much about A, B₁, and B₂.

1. Proof: Compute Pr[A∩(Ω-B₁)] = Pr[A - (A∩B₁)] = Pr[A] - Pr[A∩B₁] = Pr[A] - Pr[A]⋅Pr[B₁] = Pr[A]⋅(1-Pr[B₁]) = Pr[A]⋅Pr[Ω-B₁].

2. Disproof: Construct the uniform discrete probability space { HH, HT, TH, TT } corresponding to two independent fair coin-flips. Let B₁ = { HH, HT } be the event that the first coin comes up heads, B₂ = { HH, TH } be the event that the second coin comes up heads, and A = { HT, TH } be the event that exactly one coin comes up heads. Then Pr[A∩B₁] = Pr[{ HT }] = 1/4 = Pr[A]⋅Pr[B₁] = (1/2)⋅(1/2); similarly for A and B₂. But Pr[A∩B₁∩B₂] = Pr[∅] = 0 ≠ Pr[A]⋅Pr[B₁∩B₂] = (1/2)⋅(1/4).

3. Disproof: Let B₁ = B₂ = B for some event B with Pr[B] ∉ {0,1}, and let A be independent of B. Then Pr[A∩(B₁∪B₂)] = Pr[A∩B] = Pr[A]⋅Pr[B], showing A is independent of B₁∩B₂. We also have A independent of each of B₁ and B₂ individually, as required by introduction to the problem. But B₁ and B₂ are not independent, since Pr[B₁∩B₂] = Pr[B] ≠ Pr[B]². (Curiously, this example shows that the events ∅ and Ω are both technically independent of themselves.)

3. Small poker hands

A standard 52-card poker deck contains one each of the cards {A,2,3,4,5,6,7,8,9,10,J,Q,K} in each of the four suits {♣,♢,♡,♠}. The J (Jack), Q (Queen), and K (King) cards collectively make up the 12 face cards.

Suppose the deck is shuffled uniformly (so that all 52! orderings are equally likely), and you are dealt the first two cards.

1. What is the probability that both cards are face cards?
2. What is the probability that both cards are face cards, given that the first card you are dealt is a Jack?
3. What is the probability that both cards are face cards, given that exactly one of them is a Jack?
4. What is the probability that both cards are face cards, given that at least one of them is a Jack?

3.1. Solution

Given the second case is ordered, it's probably easiest to do this all with ordered hands, of which there are 52⋅51 = 2652 equally likely possibilities. Throughout, let A be the event that both cards are face cards.

1. There are 12 face cards, giving (12)₂ = 12⋅11 = 132 ways to pick two face cards. This gives Pr[A] = 132/2652 = 11/221.

2. Suppose the first card dealt is a Jack. There are 11 face cards left in the deck, out of 51 remaining cards; this gives a probability of 11/51 that the second card will also be a face card.

3. Let J₌₁ be the event that we get exactly one Jack. There are 2 places to put the Jack and 4 choices of Jack, times 48 choices for the remaining card, giving Pr[J₌₁] = 48/(52⋅51). Now consider Pr[A∩J₌₁]. Again we have 2 places to put a Jack and 4 choices of Jack, but there are now only 8 cards we can put in the other position; this gives Pr[A∩J₌₁] = 8/(52⋅51). But then Pr[A∩J₌₁]/Pr[J₌₁] = 8/48 = 1/6.

4. Let J_≥1 be the event that we get at least one Jack. Then J₌₁ = J₁∪J₂ where J_i is the event that the i-th card is a Jack. It is easy to see that Pr[J₁] = Pr[J₂] = 4/52 = 1/13, since if we draw one card we have 4 chances in 52 that it's a Jack. We can similarly argue that Pr[J₁∩J₂] = (4⋅3)/(52⋅51). Using Inclusion-Exclusion, we have Pr[J₌₁] = Pr[J₁] + Pr[J₂] - Pr[J₁∩J₂] = 1/13 + 1/13 - (4⋅3)/(52⋅51) = 33/221. Similarly, we can write the event A∩J_≥1 as (A∩J₁)∪(A∩J₂), so Pr[A∩J_≥1] = Pr[A∩J₁] + Pr[A∩J₂] - Pr[A∩J₁∩J₂] = 2⋅(1/13)⋅(11/51) - (4⋅3)/(52⋅51) = 19/663 (we calculated Pr[A∩J₁] in a previous case, and Pr[A∩J₁∩J₂] = Pr[J₁∩J₂] since both cards are face cards if both are Jacks). Now dividing gives Pr[A|J_≥1] = 19/99.

As a check, this program calculates the same numbers by brute force.