Suppose a student has $n$ pencils, each of them sharpened. He has his final exams lined up. Each day, before the exam, he randomly chooses a pencil to write the test. What is the probability that on the $k$-th day, the pencil he picks up is (still) sharp? Note that once a pencil is used, it becomes blunt and a blunt pencil is never re-sharpened.
The answer that's given is $\left(1-\frac{1}{n}\right)^{k-1}$.
My understanding is that if $P(k)$ is the probability that the pencil chosen on the $k$th day is sharp: Then, $P(k=1) = 1$ since every pencil is sharp. For $k>1,$ $\displaystyle P(k) = \sum_{i=1}^{k-1} \frac{n-i}{n}$ since we can have $i=1,2, \cdots k-1$ blunt pencils. But this is clearly wrong as probability can not exceed $1$ which it does here.
Questions:
- Where did I go wrong?
- I see the recursion $P(k) = P(k-1) \left(1-\frac{1}{n}\right)$ which may be of use. Can I solve it using this recursion?
Best Answer
The probability space consists of sequences $(p_1,p_2,\dots,p_k)$ of length $k$, where $p_i$ denotes the pencil chosen for the $i^{th}$ exam for each $i\in \{1,\dots,k\}$. The sample space has $n^k$ outcomes, and the assumptions of the problem imply these are all equally likely. Therefore, you just need to count the number of favorable outcomes where the $k^{th}$ pencil is different from all of the other chosen pencils, and divide by $n^k$.
The number of favorable outcomes is $n\times (n-1)^{k-1}$. This is because in order to specify $(p_1,\dots,p_{k-1},p_k)$, there are $n$ choices for the last pencil, $p_k$, and then there are $n-1$ choices for each of the first $k-1$ pencils, as they each can be any of the $n-1$ pencils besides $p_k$.
The probability is therefore $$ \frac{n\times (n-1)^{k-1}}{n^k}=(1-\tfrac1n)^{k-1}.\tag*{$\blacksquare$} $$
In your attempt, you are applying the law of total probability incorrectly. Let $A$ be the event that the $k^{th}$ pencil is sharp, and for each $i\in \{1,\dots,k-1\}$, let $B_i$ be the event that there are $i$ blunt pencils at the time you are choosing your $k^{th}$ pencil. It is true that $$ P(A)=\sum_{i=1}^{k-1} P(A\mid B_i)P(B_i) $$ Furthermore, it is true that $P(A\mid B_i)=\frac{n-i}{n}$. Therefore, the correct answer is $$\sum_{i=1}^{n-1} \frac{n-i}{n}\cdot \color{red}{P(B_i)}.$$ This is semantically close to what you wrote, but you forgot the $P(B_i)$. Since $P(B_i)$ is not easy to compute, I do not recommend this method.
As for the recurrence method, I think you are correct that something like that might work. In order for the $k^{th}$ pencil to be sharp, two things need to happen.
The $k^{th}$ pencil needs to be different from the first pencil. The probability of this is $(1-\frac1n)$.
The $k^{th}$ pencil needs to be different from pencils $2$ through $k-1$. By induction, the probability of this is $(1-\frac1n)^{k-2}$.
As long as you can convince yourself these two events are independent, it follows by induction that the probability of the $k^{th}$ pencil being sharp is $(1-\tfrac1n)\times (1-\tfrac1n)^{k-2}=(1-\frac1n)^{k-1}$.