You are waiting in line to be sorted into one of the four houses of Logwarts (a posh wizarding boarding school in the Scottish highlands) by an anthropomorphic sorting hat. The hat is a bit of a snob about the whole matter, and refuses to sort two students in a row into the same house. If a student requests a certain house, but the previously sorted student was already sorted into that same house, then the hat chooses randomly from among the three remaining houses. Otherwise, the hat grants the student’s request.
You are standing 10th in line, and you make plans to request Graphindor house for yourself. As for the other students in line, you can assume that they have random preferences from among the four houses.
The first student steps up, and has a brief, quiet conversation with the hat. After a few moments, the hat proclaims, “Graphindor!”
At this point, what is the probability that you will be sorted into Graphindor?
Let $P_n$ represent the represent the probability that the $n^\text{th}$ person in line will be randomly sorted into Graphindor. This will be used for Fiddler and the Extra Credit below. I will use induction to show that this is:
$$P_n = \frac{1}{4}\cdot\left(1 - \left(\frac{-1}{3}\right)^{n-1}\right)$$We are given the first person in line's information, and it checks out.
$$P_0 = \frac{1}{4}\cdot\left(1 - \left(\frac{-1}{3}\right)^{0-1}\right) = \frac{1}{4}\cdot(1-(-3)) = 1$$Since $P_0$ = 1, $P_1$ will never get sorted into Graphindor.
$$P_1 = \frac{1}{4}\cdot\left(1 - \left(\frac{-1}{3}\right)^{1-1}\right) = \frac{1}{4}\cdot(1-(1)) = 0$$Assume:
$$P_{k-1} = \frac{1}{4}\cdot\left(1 - \left(\frac{-1}{3}\right)^{k-2}\right)$$Note that the probability of not being sorted into Graphindor is
$$\begin{align} 1-P_{k-1} &= 1-\frac{1}{4}\cdot\left(1 - \left(\frac{-1}{3}\right)^{k-2}\right) \\ &= \frac{1}{4}\cdot\left(4 - 1 + \left(\frac{-1}{3}\right)^{k-2}\right) \\ &= \frac{3}{4}\cdot\left(1 - \left(\frac{-1}{3}\right)\left(\frac{-1}{3}\right)^{k-2}\right) \\ &= \frac{3}{4}\cdot\left(1 - \left(\frac{-1}{3}\right)^{k-1}\right) \\ \end{align}$$There are four possibilities based off the outcome of the previous and current students' preferences.
Adding from 3. and 4. to deterimine being sorted into Graphindor,
$$\begin{align} P_k &= \frac{1}{4}(1-P_{k-1}) + \frac{1}{12}(1-P_{k-1}) \\ &= \frac{1}{3}(1-P_{k-1}) \\ &= \frac{1}{3}\cdot\frac{3}{4}\cdot\left(1 - \left(\frac{-1}{3}\right)^{k-1}\right) \\ &= \boxed{\frac{1}{4}\cdot\left(1 - \left(\frac{-1}{3}\right)^{k-1}\right)} \\ \end{align}$$To check, adding from 1., 2., and 4. to deterimine not being sorted into Graphindor,
$$\begin{align} P_k &= \frac{1}{4}P_{k-1} + \frac{3}{4}P_{k-1} + \frac{2}{3}(1-P_{k-1}) \\ &= \frac{1}{3}\cdot P_{k-1} + \frac{2}{3}\\ &= \frac{1}{3}\cdot\frac{1}{4}\cdot\left(1 - \left(\frac{-1}{3}\right)^{k-2}\right) +\frac{8}{12} \\ &= \frac{1}{3}\cdot\frac{1}{4}\cdot\left(9 - \left(\frac{-1}{3}\right)^{k-2}\right) \\ &= \frac{9}{12}\cdot\left(1 - \left(\frac{1}{9}\right)\cdot\left(\frac{-1}{3}\right)^{k-2}\right) \\ &= \boxed{\frac{3}{4}\cdot\left(1 - \left(\frac{-1}{3}\right)^{k}\right)} \\ \end{align}$$The probability the student immediately before you will be sorted into Graphindor can be determined solving for $P_8$:
$$\begin{align} P_n &= \frac{1}{4}\cdot\left(1 - \left(\frac{-1}{3}\right)^{n-1}\right) \\ P_8 &= \frac{1}{4}\cdot\left(1 - \left(\frac{-1}{3}\right)^{7}\right) \\ &= \frac{1}{4}\cdot\left(\frac{2187+1}{2187}\right) \\ &= \frac{2188}{8748} = \frac{547}{2187}\\ \end{align}$$You will always request Graphindor, so your probability is:
$$1 - \frac{547}{2187} = \boxed{\frac{1640}{2187} \approx 0.7499}$$Suppose the answer to this week’s Fiddler is p.
Now, instead of being 10th in line, suppose you are Nth in line, where N is some value much greater than 10. Because so many students are being sorted in front of you, you decide you’ll take a nap. You wake up without any idea of how long you were out—it could have been a second, or it could have been an hour, you’re just not sure. It’s still not your turn to be sorted yet, but you see a student wearing the hat. After a brief moment, the hat shouts, “Graphindor!”
What is the smallest value of N such that your probability of being sorted into Graphindor is greater than p?
(To be clear, when you wake up, the student being sorted is anywhere from first in line to immediately before you in line with equal probability.)
This week's Fiddler solved for the probability of you being sorted into Graphindor if there are $9$ students before you, where the first in that line was sorted into Graphindor.
We are now to find the sum of probabilities of you being sorted into Graphindor if there are anywhere from $1$ to $N-1$ students before you with equal probability, given that the first student of the known subset of students in line was sorted into Graphindor
$$\begin{align}
\frac{1}{N-1}\sum\limits_{n=0}^{N-2} (1 - P_n) &> 1 - P_8 \\
\frac{1}{N-1}\sum\limits_{n=0}^{N-2} \left(\frac{3}{4}\cdot\left(1 - \left(\frac{-1}{3}\right)^{n}\right)\right) &> \frac{3}{4}\cdot\left(1 - \left(\frac{-1}{3}\right)^{8}\right) \\
\left[\frac{1}{N-1}\cdot\sum\limits_{n=0}^{N-2} 1\right] - \left[\frac{1}{N-1}\cdot\sum\limits_{n=0}^{N-2} \left(\frac{-1}{3}\right)^{n}\right] &> 1 - \left(\frac{-1}{3}\right)^{8} \\
\frac{1}{N-1}\sum\limits_{n=0}^{N-2} \left(\frac{-1}{3}\right)^{n} &< \left(\frac{-1}{3}\right)^{8} \\
\frac{1-\left(\frac{-1}{3}\right)^{N-1}}{1-\frac{-1}{3}} &< \frac{N-1}{3^8} \\
1-\left(\frac{-1}{3}\right)^{N-1} &< \frac{N-1}{\frac{3^9}{4}} \\
\end{align}$$
Because the left hand side is ~1,
$$\begin{align}
\frac{3^9}{4} + 1 &< N \\
4921.75 &< N \\
\end{align}$$