A Card game problem related to Markov chain

Question

This card game problem originates from the killer game Sanguosha. We assume that all cards drawn in the game procedures below are with replacement, in order to keep the probabilities fixed when a card is drawn.

The game procedure:

1. Draw a card from a standard 52-card deck;

2. If you draw a red card from 2 to 10 in step 1, then repeat step 1;

3. If you draw a red JQK in step 1, you gain an additional s, in other words s+1, then return step 1.

4. If you draw a red ace in step 1, you gain an additional t, in other words t+1, then return step 1;

5. If you draw a black card in step 1, then go to step 6;

6. If s>0, then s=s-1, return step 1; else if s=0, then go to step 7;
7. If t>0 then t=t-1, you have two bonus chances to draw a card. You will gain s+1 each time you draw a red JQK or gain t+1 each time you draw a red ace, then return to step 1; else if t=0, game ends!

So the question is How to calculate the expectation of times of running step 1 until the game ends? My idea is to construct a Markov chain with status (s,t), and calculate the expectation number of steps starting from (0,0) returning (0,0)

The procedure diagram of the game:

Answer 1

Look through the diagram and calculate the chance of various changes in $(s,t)$. If you are at $(0,0)$ the chance of game ending is $\frac 12$ (a black card). The chance of gaining an $s$ is $\frac 6{52}$ The chance of gaining a $t$ is $\frac 2{52}$ If we delete the no action cases we have from $$(0,0)\to \begin {cases} end&\frac {26}{52}\\(0,0)&\frac {18}{52}\\(1,0)& \frac 6{52}\\ (0,1)& \frac 2{52} \end {cases}$$ Then if $s \gt 0$ from $(s,0)$ we have $$(s,0)\to \begin {cases} (s,0)&\frac{18}{52}\\(s+1,0)&\frac 6{52}\\(s,1)&\frac 2{52}\\(s-1,0)&\frac {26}{52} \end {cases}$$ Now you have to do the same for $(0,t)$ and $(s,t)$, which are a bit more complicated because of the redraws. The idea is the same. As $s$ and $t$ are more likely to decrease than to increase, you can ignore states where they are rather high. Then you can fill in a matrix with the expected time to end from each state. If $T((s,t))$ is the expected time to end from $(s,t)$, the first above says $T((0,0))=1+\frac {18}{52}T((0,0))+\frac 6{52}T((1,0))+\frac 2{52}T((0,1))$ This will give you a large simultaneous system to solve.

Answer 2

I don't really intend this to be the accepted answer, but the problem intrigued me and I felt compelled to play with it. So maybe this will give you some ideas to move forward, in addition to the others answers.

Being more programmer than mathematician these days, I decided to approach this from a different angle: to get a Monte-Carlo approximation by building a simulation of the game. I was able to do this with about 100 lines of Java code, shown below. I didn't even try to be efficient, just to get something that would play the game many, many times, record the number of turns in each game, and spit out the average result. The hundred-million repitition cases runs in less than 20 seconds on my machine.

My results were fairly consistent at approximately $1.480$.

package info.cobaltduck.cardgame;

public class SimulateGame {

/* Representations:
 * cards 1-13 are hearts
 * 14-26 are diamonds
 * 27-39 are spades
 * 28-52 are clubs
 * with each suit, the mod 13 is the rank
 * 1 = Ace, 11 = J, 12 = Q, 0 = K
 */

private static int s = 0;
private static int t = 0;

// edit this higher or lower for more/less precision
private static final int HOW_MANY_GAMES = 100000000;

public static void main(String[] args) {
    // play a bunch of games and record the number of turns
    int[] turnsPerGame = new int[HOW_MANY_GAMES];
    for (int gameCounter=0; gameCounter < HOW_MANY_GAMES; gameCounter++) {
        int turnsThisGame = playSingleGame();
        turnsPerGame[gameCounter] = turnsThisGame;
    }

    // Display the average number of turns
    int total = 0;
    for (int x: turnsPerGame) {
        total += x;
    }
    double turnsAverage = (double)total / (double)HOW_MANY_GAMES;
    System.out.println("The average turns per game was " + turnsAverage);
}

private static int drawFirstCard() {
    int card = (int) (1 + Math.round(Math.random()*52));
    return card;
}

private static int drawSecondCard(int firstCard) {
    int card = firstCard;
    do {
        card = (int) (1 + Math.round(Math.random()*52));
    }
    while (card == firstCard);
    return card;
}

private static int drawThirdCard(int firstCard, int secondCard) {
    int card = firstCard;
    do {
        card = (int) (1 + Math.round(Math.random()*52));
    }
    while (card == firstCard || card == secondCard);
    return card;
}

private static void checkForIncrementS(int card) {
    if (card % 13 == 0 || card % 13 > 10) {
        s++;
    }
}

private static void checkForIncrementT(int card) {
    if (card % 13 == 1) {
        t++;
    }
}

private static void doSingleTurn() {
    int firstCard = drawFirstCard();
    if (firstCard <= 26) { // red
        checkForIncrementS(firstCard);
        checkForIncrementT(firstCard);
    }
    else { // black
        if (s > 0) {
            s--;
        }
        else if(t > 0) {
            t--;
            int secondCard = drawSecondCard(firstCard);
            int thirdCard = drawThirdCard(firstCard, secondCard);
            checkForIncrementS(secondCard);
            checkForIncrementT(secondCard);
            checkForIncrementS(thirdCard);
            checkForIncrementT(thirdCard);
        }
    }
}

private static int playSingleGame() {
    int turnCount = 0;
    do {
        doSingleTurn();
        turnCount++;
    }
    while (!(s == 0 && t == 0));
    return turnCount;
}

}