Edit Problem

Year

Paper

Question Number

Course

Section

Worksheet Citation (for copying)

Click the copy button or select the text to copy this citation for use in worksheets.

Problem Text

Each day, books returned to a library are placed on a shelf in order of arrival, and left there. When a book arrives for which there is no room on the shelf, that book and all books subsequently returned are put on a trolley. At the end of each day, the shelf and trolley
are cleared. There are just two-sizes of book: thick, requiring two units of shelf space; and thin, requiring one unit. The probability that a returned book is thick is $p$, and the probability that it is thin is $q=1-p.$ Let $M(n)$ be the expected number of books that
will be put on the shelf, when the length of the shelf is $n$ units and $n$ is an integer, on the assumption that more books will be returned each day than can be placed on the shelf. Show, giving reasoning,
that 
\begin{questionparts}
\item $M(0)=0;$
\item $M(1)=q;$
\item $M(n)-qM(n-1)-pM(n-2)=1,$ for $n\geqslant2.$
\end{questionparts}
Verify that a possible solution to these equations is 
\[
M(n)=A(-p)^{n}+B+Cn,
\]
where $A,B$ and $C$ are numbers independent of $n$ which you should express in terms of $p$.

Solution (Optional)

\begin{questionparts}
\item $M(0) = 0$ since if there's no space on the shelf, we wont be able to put any books on the shelf.

\item If the shelf has length $1$ it can only fit a thin book. For a thin book to be placed on the shelf, the very first book which comes to be placed must be thin. But this happens with probability $q$. Therefore $M(1) = q$.

\item Suppose no books have been placed on the shelf, then with probability $p$ a large book gets placed on the shelf, and the expected number of books to be placed on the shelf is equivalent to how many books will be placed on the shelf if the shelf only had $n-2$ spaces. This is $M(n-2)$. Similar if the book which arrives first is thin (with probability $q$) then there will be $M(n-1)$ more books placed on the shelf in expectation. We've just added $1$ more book, therefore $M(n) = 1+pM(n-2) + qM(n-1)$ or rearranging $M(n) - qM(n-1) - pM(n-2) = 1$.
\end{questionparts}

Suppose $M(n) = (-p)^n$, notice that:

\begin{align*}
M(n) - qM(n-1) - pM(n-2)  &= (-p)^n - (1-p)(-p)^n - p(-p)^{n-2} \\
&= (-p)^{n-2}(p^2+(1-p)p-p) \\
&= 0
\end{align*}

Suppose $M(n) = B$, notice that:

\begin{align*}
M(n) - qM(n-1) - pM(n-2)  &= B - (1-p)B - pB \\
&= 0
\end{align*}

Finally, if $M(n) = Cn$ notice that:

\begin{align*}
M(n) - qM(n-1) - pM(n-2)  &= Cn - (1-p)C(n-1) - pC(n-2) \\
&= C(n(1-(1-p)+p)+(1-p)+2p) \\
&= C(1+p)
\end{align*}

Therefore if $C = \frac{1}{1+p}$ we have that:

$M(n) = A(-p)^n + B + Cn$ satisfies our recurrence.

We also need $M(0) = 0$ and $M(1) = q$

\begin{align*}
0 &= M(0) \\
&= A + B \\
1-p &= M(1) \\
&= -pA+B 
\end{align*}
$(1+p)A = p-1 \Rightarrow A = \frac{p-1}{1+p}, B = \frac{1-p}{1+p}$.

Therefore:

\[ M(n) = -\frac{1-p}{1+p}(-p)^n + \frac{1-p}{1+p} + \frac{n}{1+p} \]

is a possible solution to this equation

Preview

Problem

Solution

Cancel

Current Ratings

Difficulty Rating: 1700.0

Difficulty Comparisons: 0

Banger Rating: 1486.2

Banger Comparisons: 1