[math] \newcommand{\NA}{{\rm NA}} \newcommand{\mat}[1]{{\bf#1}} \newcommand{\exref}[1]{\ref{##1}} \newcommand{\secstoprocess}{\all} \newcommand{\NA}{{\rm NA}} \newcommand{\mathds}{\mathbb}[/math]

(from Propp) In the previous problem, let [math]P[/math] be the probability that at the present time, each book is in its proper place, i.e., book [math]i[/math] is [math]i[/math]th from the top. Find a formula for [math]P[/math] in terms of the [math]p_i[/math]'s. In addition, find the least upper bound on [math]P[/math], if the [math]p_i[/math]'s are allowed to vary. Hint: First find the probability that book 1 is in the right place. Then find the probability that book 2 is in the right place, given that book 1 is in the right place. Continue.

Notes