# 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^{2} + 2zF + 3z^{2}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^{2}), 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^{2}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^{n}; the second gives 3^{n-1}, except when n = 0, where it gives 0. So we have 3^{n} + 3^{n-1} = 4⋅3^{n-1} Scheme-- expressions of any length n > 0, and 3^{0} = 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_{1} be independent events, and let A and B_{2} also be independent events, on some probability space Ω.

Prove or disprove: A and Ω-B

_{1}are independent events.Prove or disprove: A and B

_{1}∩B_{2}are independent events.Prove or disprove: If A and B

_{1}∪B_{2}are independent events, then B_{1}and B_{2}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_{1}] = Pr[A]⋅Pr[B_{1}] and Pr[A∩B_{2}] = Pr[A]⋅Pr[B_{2}], but otherwise we don't know much about A, B_{1}, and B_{2}.

Proof: Compute Pr[A∩(Ω-B

_{1})] = Pr[A - (A∩B_{1})] = Pr[A] - Pr[A∩B_{1}] = Pr[A] - Pr[A]⋅Pr[B_{1}] = Pr[A]⋅(1-Pr[B_{1}]) = Pr[A]⋅Pr[Ω-B_{1}].Disproof: Construct the uniform discrete probability space { HH, HT, TH, TT } corresponding to two independent fair coin-flips. Let B

_{1}= { HH, HT } be the event that the first coin comes up heads, B_{2}= { 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_{1}] = Pr[{ HT }] = 1/4 = Pr[A]⋅Pr[B_{1}] = (1/2)⋅(1/2); similarly for A and B_{2}. But Pr[A∩B_{1}∩B_{2}] = Pr[∅] = 0 ≠ Pr[A]⋅Pr[B_{1}∩B_{2}] = (1/2)⋅(1/4).Disproof: Let B

_{1}= B_{2}= B for some event B with Pr[B] ∉ {0,1}, and let A be independent of B. Then Pr[A∩(B_{1}∪B_{2})] = Pr[A∩B] = Pr[A]⋅Pr[B], showing A is independent of B_{1}∩B_{2}. We also have A independent of each of B_{1}and B_{2}individually, as required by introduction to the problem. But B_{1}and B_{2}are not independent, since Pr[B_{1}∩B_{2}] = Pr[B] ≠ Pr[B]^{2}. (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.

- What is the probability that both cards are face cards?
- What is the probability that both cards are face cards, given that the first card you are dealt is a Jack?
- What is the probability that both cards are face cards, given that exactly one of them is a Jack?
- 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.

There are 12 face cards, giving (12)

_{2}= 12⋅11 = 132 ways to pick two face cards. This gives Pr[A] = 132/2652 = 11/221.- 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.
Let J

_{=1}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_{=1}] = 48/(52⋅51). Now consider Pr[A∩J_{=1}]. 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_{=1}] = 8/(52⋅51). But then Pr[A∩J_{=1}]/Pr[J_{=1}] = 8/48 = 1/6.Let J

_{≥1}be the event that we get at least one Jack. Then J_{=1}= J_{1}∪J_{2}where J_{i}is the event that the i-th card is a Jack. It is easy to see that Pr[J_{1}] = Pr[J_{2}] = 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_{1}∩J_{2}] = (4⋅3)/(52⋅51). Using Inclusion-Exclusion, we have Pr[J_{=1}] = Pr[J_{1}] + Pr[J_{2}] - Pr[J_{1}∩J_{2}] = 1/13 + 1/13 - (4⋅3)/(52⋅51) = 33/221. Similarly, we can write the event A∩J_{≥1}as (A∩J_{1})∪(A∩J_{2}), so Pr[A∩J_{≥1}] = Pr[A∩J_{1}] + Pr[A∩J_{2}] - Pr[A∩J_{1}∩J_{2}] = 2⋅(1/13)⋅(11/51) - (4⋅3)/(52⋅51) = 19/663 (we calculated Pr[A∩J_{1}] in a previous case, and Pr[A∩J_{1}∩J_{2}] = Pr[J_{1}∩J_{2}] 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.