Probability of winning high-low with full deck

Question

I play a game on a site I use that's a version of the casino game of "High Low." A standard 52-card deck is shuffled, and the top card is revealed. The player guesses whether the next card on the top of the deck is higher or lower than the revealed card. This continues iteratively until either (1) the player guesses wrong or (2) there are no more cards left to reveal. If the next card is the same as the revealed card, it is a "freebie" for the player and the game continues. Suit is not relevant, just value, with 10 < J < Q < K < A. There is no card replacement.

What I am wondering is what is the probability of "winning the game" (guessing correctly 51 times in a row) under different strategies. I am just not sure how to abstract the problem. I figure that once you settle on a strategy, it really becomes a question of how the deck is shuffled, i.e. the probability of a specific type of permutation of the cards. These are the two strategies I'm interested in:

1. A "naive" strategy where you always guess higher for 2 through 7, always guess lower for 9 through A, and flip a coin for 8. I presume this is an easier question to answer.
2. A "card counter" strategy where you keep track of all the cards you have seen, and then choose the more likely option. For example, if the first card is a 2, and the second card is an 8, you would guess the third card is higher since it has a slightly higher probability (24/50 vs. 23/50).

For example, imagine the deck was simply sequential (2, 2, 2, 2, 3, 3, ..., K, A, A, A, A). The naive strategy would guess correctly until you got to the first 9, while the card counter strategy would win this game.

I was able to make a simulation of the game and the strategies in Python very easily, which provided interesting results for probabilities of lower scores, but because the probability of getting all 51 is correct is so low it doesn't converge meaningfully for higher scores even after millions of trials.

How could I go about abstracting the game to determine this probability? The number of permutations of the deck is large but finite, so it seems like a straightforward combinatorics question to me, but I'm getting tripped up on how each element needs to relate to all of those before it and also incorporating the coin flips. I thought about a Markov model but the probability of the next card depends on more than just the last card flipped over. Is this even a tractable question?

Answer 1

Notice that the entire state of the game can be encoded as (# of cards remaining of each rank, last rank revealed), and also that this tree only goes downwards as more and more cards are drawn - you can never return to the same state, or state with higher (or equal) number of cards again.

The standard way of solving this kind of non-recurrent Markov chain is backwards induction (dynamic programming): start from states where you immediately know what to do (i.e. with an empty deck, you win).

The inductive step is: suppose you know the probability of winning starting from that state for all possible states with $n$ cards remaining in the deck. From each possible state with $n+1$ cards remaining, you can tell

1. the probabilities of drawing into each $n$-card state,
2. therefore the (weighted) probability of winning should you choose high or low from that original $n+1$-card state,
3. and using that, which choice to make.

Repeat until you hit the very initial state, that is, right when the first card is drawn. This provably generates the optimal solution, its strategy, and its winrate (or the winrate of any fixed strategy).