%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

State machines:
(10 min)

State machine supposed to find GCD of three positive integers, a, b,
and c.
Has state consisting of a,b,c,a',b',c'.
Algorithm is nondeterministic:

Pick any two of a', b', c' that aren't equal.
Replace the greater one by the difference.

Prove:  If all are equal then they are equal to the GCD.
Use invariants and the Invariant Theorem.
State carefully any number theory facts you use, but you need not
prove them.

A: Key invt is gcd(a',b',c') = gcd(a,b,c).
Also use fact that if x > y then gcd(x,y) = gcd(x-y,y)
Or if x > y then gcd(x,y,z) = gcd(x-y,y,z)


Prove:  Eventually all are equal.
Use decreasing derived variable.

sum always decreases

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Sums of series:

(a) 1 + 1/2 + 1/(2)(3) + 1/(2)(3)(4) + ...  
 
A: e - 1

(I use this in another problem, below...make separate?)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Combinatorics:
(10 min)

Give them a binomial coefficient identity, e.g.:

(n choose m)(m choose r)(r choose s) = (n choose s)(n-s choose
r-s)(n-r choose m-r)

(a) Prove this by working out the expressions directly.

(b) Prove this by describing an interpretation for each side as a
method of counting some set of elements (same set for both sides).

A:  Choosing committee and subcommittee and subsubcommittee.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Generating functions:
(10 min)

Can give a question saying ``match up the series in the left column
with their generating functions in the right column''.
This should be a one-to-one correspondence.

Alternatively, just ask them to find the generating function for some
sequences, e.g.:

(a) 1,0,0,1,0,0,1,0,0,1,0,0,1,...

(b) 1,2,3,4,5,6,7,8,...

(c) 1,2,3,3,3,3,3,3,...

(d) 1,1,3,4,4,6,7,7,8,...

(e) 1,2,3,5,7,9,12,15,18,22,...

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Expectation
(10 min)

A box initially contains n black balls.
The experiment involves repeatedly removing a black ball and replacing
it with a new ball that is
  black with probability p,
  white with probability 1-p
 
What is the expected time until all the balls are white?

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Wald's Theorem
(5 min)

Late, random Christmas shopping:
From 11-12PM on Dec. 24, between 0 and 100 people will enter Filene's
Basement to do their Christmas shopping, with equal probability of
1/101 for each possible number of people, 0 to 100.
Each person who enters the store will toss a fair coin until it comes up
heads, and will use the number of tails to determine how many presents to
buy.
For each present, each person will throws a fair die and spend from
$1 to $6 depending on the outcome of the die.

What is the expected amount of money that will be spent at Filene's
basement during that hour?

A: Can use Wald twice, multiply (50)(1)(3.5) = 175

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Wald's Theorem
(10 min)

Experiment:
Start with a sack containing one W and one B ball.
Repeatedly:
  Pick a ball from sack. 
    If W, then halt.
    If B, then:
        Play the Monty Hall game (with a Theory Pig and two goats), using the
          smart strategy.
        Replace the B ball.
        Add another W ball to the sack.

(a) Write down a series whose sum gives the expected number of times
the player gets to play the Monty Hall game and give the sum.

A:

E(games)
Pr(games > 0) + Pr(games > 1) + Pr(games > 2) +...
= 1/2 +  1/(2)(3) + 1/(2)(3)(4) + ...  

= e - 2

(b) What is the expected number of Theory Pigs the player will win?

2/3 (e - 2)

(c) What is the expected number of goats?

1/3(e - 2)


Another possibility for Wald is to do some variant of the labyrinth
problem from tutorial.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Mean and variance

Can ask them to calculate the mean and variance for some particular
distribution, e.g.,

Pr(x) = p (1-p)^x



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Variance
(10 min)

Prove some equation involving variance carefully, justifying each step
with a precise reason.
E.g.:

Var[R1 + R2] = Var[R1] + Var[R2] (assuming independence)

Or maybe we give them the steps and they fill in the reasons.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Markov, Chebyshev
(15 min)

One could argue that MIT GPAs are determined by a probability
distribution.
Suppose the mean of that distribution is 4.0.

(a) Find a tight upper bound on the probability that any particular
student gets a GPA of 4.5 or higher.

A. Markov, pr(GPA >= 4.5)  <= (4.0)/(4.5) = 8/9

(b) Describe a particular probability distribution of GPAs
showing your bound in (a) is tight.

A. Pr(0) = 1/9,  Pr(4.5) = 8/9

(c)  Now also assume that the probability distribution has a standard
deviation of .1.
Give a tight bound on the probability that any particular student gets
a GPA of 4.5 or higher.

A. Chebyshev one-way:
Pr(X \geq E[X] + c (s.d.)) \leq 1/(1 + c^2)
Pr(GPA \geq 4.0 + 5 (s.d)) \leq 1/(1 + 5^2) = 1/26

(d)  Describe a particular probability distribution of GPAs showing
that your bound in (c) is tight.

A. Pr(3.98) = 25/26, Pr(4.5) = 1/26

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Chernoff, etc.

Consider 1000 MIT seniors, with GPAs determined by a probability
distribution with mean 4.0 and s.d. .1.
Suppose all are independent.
Suppose that for this distribution,
the probability pr(GPA >= 4.5)  is exactly equal to 1/100.

%[[[Check that I don't give conflicting assumptions...]]]

(a) What is the expected number of students with GPAs >= 4.5?

A: 10

(b) Using the Chernoff bound, give an upper bound on the probability that
there are at least

sqrt(e) times this expectation students with GPAs geq 4.5.

Set it up with a formula.

A: e^{-(ln sqrt(e) + 1/sqrt(e) - 1)sqrt(e) (10)}

which reduces to {1 \over e^{10(1 - sqrt(e)/2)}}


(c) Give a rough estimate of the result
(within an order of magnitude is fine).

A: ??? looks like about .3
???

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Gambler's ruin

Consider game with T = 2n.

(If this is too easy, what about T = 3n?)
What is prob of winning:

(a) If p = 1/2?

A: n/T = 1/2

(b) If p = .49?

(51/49)^n - 1             1
_____________  =  ________________, which is about 1 over (1.04)^n

(51/49)^2n - 1    (51/49)^n + 1


(c) If p = .51?

1 - (49/51)^n              1
_____________  =  ________________, which is about ...

1 - (49/51)^2n    1 + (49/51)^n 

But then can also get this answer by doing 1 - answer to (b).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
