Sorting Hat
Sorting Hat
Solutions to this weeks Fiddler.
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?
Solution
We use notation \(X_n = 1\) to indicate the event that the \(n\)’th person in the queue got Griffindor and \(X_n = 0\) to denote that they did not.
When \(n=1\) we have \(\text{ }\text{Pr}\left[X_1 = 1\right] = 1\) and when \(n=2\), \(\text{ }\text{Pr}\left[X_2 = 1\right] = 0\). Here the randomness is over the sorting hats coins.
For any \(n \geq 3\) we can write down the probability of getting Griffindor with the following equation, which follows from Bayes rule
\[\begin{align*} \text{ }\text{Pr}\left[X_n = 1\right] &= \text{ }\text{Pr}\left[X_n = 1 \land X_{n-1} = 1\right] + \text{ }\text{Pr}\left[X_n = 1 \land X_{n-1} = 0\right] \\ &= 0 + \text{ }\text{Pr}\left[X_n = 1 | X_{n-1} = 0\right]\text{ }\text{Pr}\left[ X_{n-1} = 0\right]\\ &= \frac{1}{3}\left(1 - \text{ }\text{Pr}\left[ X_{n-1} = 1\right]\right) \end{align*}\]
Plugging in \(n=10\) (you could just plug it into a computer as in the code described below) or solve it analytically to get
\[\begin{align*} \text{ }\text{Pr}\left[X_n = 1\right] &= \sum_{i=1}^{\frac{n-3}{2}-1}1/3^{2i+1} - \sum_{i=0}^{\frac{n-2}{2}-1}1/3^{2i} \\ &= 1/3 + 1/3^3 + 1/3^5 - 1/3^2 - 1/3^4 - 1/3^6 \\ &= 0.249 \end{align*}\]