Expected Value of Guessing Game I'm playing a guessing game with my friend. He chooses a permutation of the numbers $1$ through $n$ (i.e., if $n = 9$, one permutation is $934512678$). I guess the numbers in order, and he tells me if I'm right after every guess. My strategy is to make the same guess until I am correct, then make a different guess and repeat. Let $X$ equal the number of correct guesses. What is $E(X)$?
My attempt:
I know that I have a $1/n$ chance of guessing the first number correctly. If I do not guess the first number correctly, then I have a $1/(n-1)$ chance of guessing the second number correctly and so on. I'm confused by what happens when I make a correct guess and start guessing a different number. If I've already passed that number, I have $0$ chance of guessing that number correctly, but if I haven't, I have a non-zero chance. How can I think about this so I can calculate $E(X)$?
 A: For concreteness, let's say that the number you'll keep guessing first is $1$; then if you get $1$, you'll move on to $2$, and so on.
Then the number of correct guesses you'll have at the end is the longest subsequence $1, 2, 3, \dots, k$ that appears in ascending order in the permutation.
Specifically, the probability of at least $k$ correct guesses is $\frac1{k!}$ for $1 \le k \le n$: the probability that the numbers $1,2,\dots, k$ appear in ascending order.
Therefore the probabily of exactly $k$ correct guesses is $\frac1{k!} - \frac1{(k+1)!}$ when $k<n$, and just $\frac1{n!}$ for $k=n$. The expected number of correct guesses is
$$
   \sum_{k=1}^{n-1} k \left(\frac1{k!} - \frac1{(k+1)!}\right) + n\left(\frac1{n!}\right)
$$
For $1 \le j \le n$ total coefficient of $\frac1{j!}$ that appears anywhere inside the sum is $1$: $\frac1{j!}$ appears with a coefficient of $j$ when $k=j$, and with a coefficient of $-(j-1)$ when $k=j-1$. Therefore the sum can also be written as
$$
   \sum_{j=1}^n \frac1{j!}.
$$
This has no closed form, but as $n \to \infty$, it tends to $e-1 \approx 1.71828$.
A: Partial answer below. I don't think a closed-form solution exists -- but you could script up a simulation.

However, there are components of this problem that are amenable to simple analysis:
The expected number of guesses to get the first correct guess (let's call this $X_1$ is given by:
$$E[X_1] = \frac{N+1}{2}$$
Derivation:
We know $P(X_1=i) = \frac{1}{N}$ (see a derivation)
Therefore $E[X_1] = \sum_{k=1}^N kP(X_1=i) = \frac{\sum_{k=1}^N k}{N} = \frac{N(N+1)}{2N} \;\;\square$
So, not surprisingly, for $N=9$ we have $E[X_1] = 5$
The tricky part is the branching logic of the subsequent events.
For $X_2$ and beyond, we need to look at conditional expectations. For the second correct guess, we have a new issue (that you identified). If we've guessed $X_1$ times, then one of the $X_1 -1$ numbers that didn't match our first number could be the second number we pick. In that case, $X_2$ does not exist (we can't guess correctly).
The probability that the second number was in one of the slots already guessed at is:
$$\frac{X_1-1}{N-1}$$
Assuming it's not passed then we get the conditional expected value of the number of guesses till you hit that number:
$$E[X_2|X_1] = \frac{N-X_1+1}{2}$$
Turning this around, we can get the distribution of correct guesses ($X$):
$$P(X=1) = \sum_{k=2}^N  \frac{k-1}{N-1}\cdot \frac{1}{N}$$
This just says that the second number must be in the $X_1 -1$ positions already guessed that were not the first number you selected.
For $X=2$ we need to have the second number among the "yet to be guessed" slots and the third among those already guessed.
$$P(X=2) = \sum_{k=2}^N \frac{N-1-k}{N(N-1)}\sum_{j=1}^{N-k}\frac{k+j-2}{N-2}\cdot \frac{1}{N-k}$$
This pattern will continue for each value of $X\leq n$
It get's pretty messy, but a simulation script isn't too bad:
from itertools import permutations

N = 4 # we are permuting the first N consecutive integers for this game
guess_sequence = list(range(N)) # doesn't really matter what we pick here

def game(guess_sequence,hidden_sequence) -> int:
    correct_guesses = 0
    iter_guess = iter(guess_sequence)
    current_guess = next(iter_guess)    
    try:
        for i in hidden_sequence:
            if i == current_guess:
                correct_guesses += 1
                current_guess = next(iter_guess)
    except StopIteration:
        pass
    return correct_guesses
            

results = [game(guess_sequence, x) for x in permutations(guess_sequence)]
counts = [results.count(i) for i in range(1,max(results) + 1)]
n_obs = sum(counts)
hist = [counts[i]/n_obs for i in range(len(counts))]

print(f"counts of X:{counts}")
print(f"pmf of X:{list(round(i,6) for i in hist)}")
print(f"Expected value of X is: {round(1 + sum(i*p_i for i,p_i in enumerate(hist)),4)}")
print(f"CHECKSUM:{sum(hist)}") 

What you'll see is that the expected value of $X$ is essentially constant at approx $1.7$ past $n=4$, so it appears your strategy is very unlikely to result in being right more than twice.
