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.
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's define our probability space such that it will be useful for the this problem. Of course, as stated there are three other houses with fanciful names (perhaps Hufflepath, Ravenndiagram and Slytheorem), but as far as you're concerned it is Graphindor or bust, so luckily all of these outcomes are indistinguishable to you. Let $p_{i,k}$ be the probability that the $i$th wizardling on line is sorted into Graphindor, subject to the fact that the $k$th wizardling on line was the last one to actually be sorted to Graphindor.
As far as you are concerned, you get to Graphindor as long as the 9th wizard is not sorted there, since you will always ask the hat to sort you into Graphindor. So, given that the 1st wizardling on line was just sorted into Graphindor, the probability that you will be sorted into Graphindor is $p=1-p_{9,1}.$ All that remains now is to divine what the formula for $p_{i,k}$ is anyway.
Let's say that we know $p_{i,k}$ for some $1 \leq k \leq i.$ There are two ways for the $(i+1)$th wizardling to end up sorted into Graphindor: either (a) the $i$th wizard is sorted to some ``not Graphindor'' house and the $(i+1)$th wizardling requested Graphindor; or (b) the $i$th wizard is sorted to some ``not Graphindor'' house and the $(i+1)$th wizardling requested that same ``not Graphindor'' house. In both cases, the probability of event (a) is $1/4$ while the probability of event (b) is $1/12 = 1/4 \cdot 1/3.$ Putting these two together, we get the recursion relationship $$p_{i+1,k} = \frac{1}{4} (1-p_{i,k}) + \frac{1}{12} (1-p_{i,k}) = \frac{1-p_{i,k}}{3}, \,\,\text{for $i \geq k \geq 1.$}$$ By construction, we have $p_{k,k} = 1,$ for each $k \geq 1.$
This recursive formula leads to the explicit formula $$p_{i,k} = \frac{1}{4} \left(1 + 3 \cdot (-3)^{k-i}\right), \,\,\, \text{for all $i \geq k \geq 1.$}\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\star$$ We see that for $i=k \geq 1$ that we recover $p_{k,k} = \frac{1}{4} (1 + 3 \cdot (-3)^0 ) = 1,$ as our base case. If we assume that the formula $\star$ holds for some $i \geq k \geq 1,$ then from the recursive formula we see that \begin{align*}p_{i+1,k} = \frac{1-p_{i,k}}{3} &= \frac{1 - \frac{1}{4} \left(1 + 3 \cdot (-3)^{k-i} \right)}{3} \\ &= \frac{\frac{3}{4} - \frac{3}{4} \cdot (-3)^{k-i}}{3} \\ &= \frac{1}{4} \left( 1 + \frac{3}{-3} (-3)^{k-i} \right) \\ &= \frac{1}{4} \left( 1 + 3 \cdot (-3)^{k-i-1} \right),\end{align*} which follows formula $\star$ for the case $i+1$. Thus by induction we have proven the formula. This therefore allows us to answer that if you are $10$th in line and have resolved to request Graphindor no matter what that your probability of getting sorted into Graphindor after the first wizard is sorted into Graphindor is $$p=1-p_9 = 1 - \frac{1}{4} \left(1 + 3 \cdot (-3)^{1-9}\right) = \frac{3-3^{-7}}{4} = \frac{6560}{8748} = \frac{1640}{2187} \approx 0.7498856882....$$
Now, instead of being 10th in line, suppose you are $N$th 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.)
OK, so now it becomes a little clearer why I chose such obscure nomenclature for the earlier problem. However, in this case where you are sitting at $N$th in line and then dozed off only to wake up as the wizardling in uniformly randomly distributed position $M$ is sorted into Graphindor, so we have the expected probability of being sorted into Graphindor is still dependent on whether or not the person immediately in front of you is sorted into Graphindor, that is $q=1-p_{N-1,M}$. However, here since $M$ is random we have \begin{align*} q = 1 - p_{N-1,M} &= 1 - \sum_{i=1}^{N-1} \mathbb{P} \{ M = i \} p_{N-1,i} \\ &= 1 - \frac{1}{N-1} \sum_{i=1}^{N-1} \frac{1}{4} \left(1 + 3 \cdot (-3)^{i-N+1} \right) \\ &= \frac{3}{4} - \frac{3 \cdot (-3)^{1-N}}{4(N-1)} \sum_{i=1}^{N-1} (-3)^i \\ &= \frac{3}{4} - \frac{3 \cdot (-3)^{1-N}}{4(N-1)} \frac{(-3) - (-3)^N}{1-(-3)} \\ &= \frac{3}{4} \left( 1 - \frac{ 9 \cdot (-3)^{-N} + 3}{4(N-1)} \right) \\ &= \frac{3}{16} \frac{4N-7-9\cdot(-3)^{-N}}{N-1}\end{align*} If we then want to know what is the minimal $N$ such that $q = q(N) \gt p = \frac{1640}{2187},$ we need get a nonlinear, monotonically increasing equation that we can just as easily guess and check for a solution.
In particular, if we solve the approximation where we ignore that pesky exponential function and equally ignore the integrality of $N$, we get $$\tilde{q}(x) = \frac{3 (4x-7)}{16(x-1)}.$$ If we were to solve $$\tilde{q}(x) = \frac{3(4x-7)}{16(x-1)} = p$$ for a non-integer value of $x$, we get $$x^* = \frac{21-16p}{12-16p} = \frac{19687}{4} = 4921.75.$$ This seems like a very good place to start hunting and pecking with $N^* = \lceil x^* \rceil = 4922.$ Let's first check $$\tilde{q}(N^*) = \frac{3 \cdot (4 \cdot 4922 -7)}{16 \cdot 4921} = \frac{59043}{78736} \approx 0.7498856939.....,$$ which is roughly $6 \times 10^{-9}$ larger than $p.$ Since $9 \cdot (-3)^{-N^*} \ll 10^{-9},$ we can confirm that $N^* = 4922$ is the smallest integer value such that if you fell asleep and randomly woke up to some wizardling ahead of you in line is being sorted to Graphindor then your probability of also getting sorted to Graphindor is $q(N) \gt p = \frac{1640}{2187}.$