[FrontPage] [TitleIndex] [WordIndex

Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

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

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 + z2 + 2zF + 3z2F, since a Scheme-- expression is either an empty sequence (1) one of two variables of length 1 (2z), a constant of length 2 (z2), 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 (3z2F; note that it doesn't really matter that the parentheses surround the expression instead of coming before it). Solving for F gives:

F &= \frac{1+2z+z^2}{1-2z-3z^2}
&= \frac{(1+z)^2}{(1+z)(1-3z)}
&= \frac{1+z}{1-3z}
&= \frac{1}{1-3z} + \frac{z}{1-3z}.

The first term gives the sequence 3n; the second gives 3n-1, except when n = 0, where it gives 0. So we have 3n + 3n-1 = 4⋅3n-1 Scheme-- expressions of any length n > 0, and 30 = 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 B1 be independent events, and let A and B2 also be independent events, on some probability space Ω.

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

  2. Prove or disprove: A and B1∩B2 are independent events.

  3. Prove or disprove: If A and B1∪B2 are independent events, then B1 and B2 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∩B1] = Pr[A]⋅Pr[B1] and Pr[A∩B2] = Pr[A]⋅Pr[B2], but otherwise we don't know much about A, B1, and B2.

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

  2. Disproof: Construct the uniform discrete probability space { HH, HT, TH, TT } corresponding to two independent fair coin-flips. Let B1 = { HH, HT } be the event that the first coin comes up heads, B2 = { 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∩B1] = Pr[{ HT }] = 1/4 = Pr[A]⋅Pr[B1] = (1/2)⋅(1/2); similarly for A and B2. But Pr[A∩B1∩B2] = Pr[∅] = 0 ≠ Pr[A]⋅Pr[B1∩B2] = (1/2)⋅(1/4).

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

  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)2 = 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=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.

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

2014-06-17 11:57