Regarding worst case:
Example to demonstrate worst case:
If with N = 5, we have deck:
1010001011
We will use 10 moves making the guesses:
0000011111
After this, we have two 1:s and two 0:s left, which might shuffle into:
1010
And we use 4 moves to guess:
0000
After this, we still have two 1:s left. So we will need two more moves, totalling 16 (which is worse than 3N = 15).
The reason why probability_guess algorithm may become worse than the two_pass algorithm is becuase it might requires more than one reshuffle. The two_pass algorithm is guaranteed to never need more than one reshuffle. Already at N=3 and N=4, probability_guess algorithm may require an additional reshuffle, but in these cases, it will still not become worse than two_pass. When N=5, though, the impact of the additional required reshuffle may cause the worst case performance to become worse than two_pass, as shown above.
Regarding average case:
Interesting things happen around N = 26. For N = 26, two_pass and probability_guess have approximately equal performance in the average case. When N > 26, probability_guess algorithm will degrade in performance, becoming worse than two_pass algorithm, even in the average case.
Speculative reasoning around average case performance:
Lets compare benefits and drawbacks of probability_guess for two cases. Benefit of probability_guess is that you use available information from past observations which improves your probability to guess subsequent guesses correctly. Drawback of probability_guess is that there is a risk that you may need more than one reshuffle.
For the simplistic case N = 1:
We have 50% to guess the first card correctly. For the second card, we have a 100% chance to guess it correctly. In this case, the probability_guess algorithm increased our chance to guess correctly (from 50% to 100%) for that second card (which is half of the total number of cards). Ie. the benefit is quite big.
Consider case when we let N tend towards infinity. Take N=10^9 as an example of a big N. When picking the second card, our probability to guess the second card correctly is 500,000,000 / 999,999,999 which is approximately 50%. Ie. probability_guess didn't help much in improving the probability to get it correct. The same reasoning applies for the majority of the guesses for the initial shuffle. Only when you are near the end of the deck will the probability_guess give a significant improvement to the probability to guess correctly. But "near the end of the deck" is a very small portion of the entire deck. The drawback, however, has become larger. Now we do not only risk having to reshuffle twice. We might have to reshuffle several times. The benefit does not outweigh the drawback.
As a specific example, I did one million solution attempts for N=500. Out of these, 94.7% were slower than the two-pass alogrithm. And in the worst case, 7 reshuffles were necessary.
Summary:
N < 5 : probability_guess better than two_pass in average case, and equal in worst case
5 <= N < 26 : probability_guess better than two_pass in average case, but worse in worst case
N == 26 : probability_guess roughly equal to two_pass in average case, but worse in worst case
N > 26 : probability_guess worse than two_pass in average case
two_score = N*2+N
:D) $\endgroup$