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

• <> (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.

# 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.

# 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?

2014-06-17 11:57