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. From RosenBook

Do Exercises 5.3.26, 5.3.30, and Supplementary Exercise 5.20 (on pages 396-397) from RosenBook.

Hint: For Supplementary Exercise 5.20, it may be possible to eliminate a summation by expressing one of your answers in terms of the harmonic numbers H_n, where

latex error! exitcode was 1 (signal 0), transscript follows:

This is pdfTeX, Version 3.1415926-2.5-1.40.14 (TeX Live 2013)
entering extended mode
(./latex_a9240121e444c6b7a556d6dff4ff38f548b3c83b_p.tex
LaTeX2e <2011/06/27>
Babel <3.9f> and hyphenation patterns for 78 languages loaded.
(/usr/local/texlive/2013/texmf-dist/tex/latex/base/article.cls
Document Class: article 2007/10/19 v1.4h Standard LaTeX document class
(/usr/local/texlive/2013/texmf-dist/tex/latex/base/size12.clo))
(/usr/local/texlive/2013/texmf-dist/tex/latex/base/inputenc.sty
(/usr/local/texlive/2013/texmf-dist/tex/latex/base/utf8.def
(/usr/local/texlive/2013/texmf-dist/tex/latex/base/t1enc.dfu)
(/usr/local/texlive/2013/texmf-dist/tex/latex/base/ot1enc.dfu)
(/usr/local/texlive/2013/texmf-dist/tex/latex/base/omsenc.dfu)))
No file latex_a9240121e444c6b7a556d6dff4ff38f548b3c83b_p.aux.
! Missing $ inserted.
<inserted text> 
                $
l.8 \end{document}
                  
! Display math should end with $$.
<to be read again> 
                   \par 
l.8 \end{document}
                  
[1] (./latex_a9240121e444c6b7a556d6dff4ff38f548b3c83b_p.aux) )
(see the transcript file for additional information)
Output written on latex_a9240121e444c6b7a556d6dff4ff38f548b3c83b_p.dvi (1 page,
 604 bytes).
Transcript written on latex_a9240121e444c6b7a556d6dff4ff38f548b3c83b_p.log.

Further clarification: for parts (c) and (d) of Supplementary Exercise 5.20, do not assume any limit on how many times you put a ball into a bin; in each case you only stop when the condition (either filling a particular bin or filling all bins) is satisfied.

2. Not from RosenBook

Suppose that n basketball players, no two of whom have the same height, are tossed into an urn and then sampled uniformly at random without replacement until none are left. Let X_i be the height of the i-th basketball player removed from the urn.

As a function of i, compute the probability that X_i > X_j for all j < i; i.e., the probability that the i-th basketball player removed from the urn sets a new height record.
Let Y be the number of times that a new height record is set. Compute E[Y].
Compute the exact probability that Y=n and compare this to the upper bound you get applying Markov's inequality to the value of E[Y] you just computed.