Probability of Two Consecutive Same-Value Cards in a Shuffled Deck

[Office_Shredder]

Given that there are no matches in the first 51 draws, what is the probability the last two match? Might be a helpful step for solving analytically. This doesn't seem easy to me.

 

[PeroK]

I have written a program based on the above idea to maintain the probability of each valid configuration. I.e. starting from $(0,0,0,0,13)$ the only valid configuration for 51 cards remaining is $(0,0,0,1,12); 3$ (probability $1$). And the only valid configuration for 50 cards remaining is $(0,0,0,2,11); 3$. This means that we have 2 face values with 3 cards remaining, 11 with four cards remaining; and the last card in the sequence has 3 cards of the same value remaing. The next step (49 cards remaining produces two configs):
$(0,0,1,1,11);2$ and $(0,0,0,3,10); 3$.

The key point is that the total number of valid configurations is limited to about 7,000. Although the number of valid paths exponentiates with the number of cards. By consolidating the number of valid configurations and their associated probabilities at each step, the processing is minimised. The following code only takes about 1 second to execute:

################################################################################################################
## Program to calculate the probability that in a shuffled deck of cards there are no adjacent cards with     ##
## the same face value.  The number of suits is hardcoded, but the number of face values can vary (< 100)     ##
## The idea that as each card is chosen we have a configuration that can be represented as follows:           ##
## a = ([a_0, a_1, a_2, a_3, a_4], last_i)                                                                    ##
## where a_i is the number of face values for which i cards remain; and last_i relates to the last card. E.g. ##
## a = ([1,4,1,6,1],1) indicates that there is 1 face value with 4 cards remaining; 6 with 3 remaining etc.;  ##
## and the last card in the sequence is one of the 4 with 1 card remaining.  We can also see that for this    ##
## configuration we have 24 cards in the sequence and 28 cards remaining.                                     ## 
## We also maintain the probability of achieving each configuration.                                          ##
## From this configuration we can generate valid configurations for 27 cards remaining.  E.g. we can choose   ##
## one of four cards (with probability 4/28) to achieve ([1,4,1,7,0],3).  Or, one of 18 cards to achieve      ##
## ([1,4,2,5,1], 2). Note that there are only 3 cards that we can choose to achieve ([2,3,1,6,1]) as one of   ##
## 4 singletons was the last card chosen, which we must avoid.                                                ## 
## Starting with ([0,0,0,0,13],0) (probability 1) we can proceed to generate all valid configurations after   ##
## each card, ending with the final configuration ([13,0,0,0,0],0) and the final probability of success.      ##
## Note that the variable a_0 is redundant and is not actually maintained in this program.                    ##
##                                                                                                            ##
## For ease of processing, the configurations are coded and decoded using base 100:                           ##
## code_a = last_i + 100*a[1] + (100^2)*a[2] ... (100^4)*a[4]                                                 ##
##                                                                                                            ##
## The critical reason that the program runs quickly is that there are relatively few valid configurations.   ##
## At each step duplicate configurations are combined and their probabilities added.  Otherwise, the number   ##
## of valid paths exponentiates.                                                                              ##
################################################################################################################
#
def code_config(a, last_i):
    code_a = last_i + (100*a[1]) + ((100**2)*a[2])+((100**3)*a[3])+((100**4)*a[4])
    return code_a
#
def decode_config(code_a):
    last_i_out = int(code_a % 100)
    #
    a_out = [0,0,0,0,0]
#
    code_temp = (code_a - last_i_out)/100
#    print(code_temp)
#
    for i in range(1,5):
        a_out[i] = int(code_temp % 100)
        code_temp = (code_temp - a_out[i])/100
#
    return(a_out, last_i_out)
#
# Procedure to decode and print configs (for interest and debugging)
#
def print_configs(configs, probs):
    for k in range(0,len(configs)):
        (a, last_i) = decode_config(configs[k])
        print(configs[k], a, last_i, probs[k])
#
###################################################################################################################
# Main recursive procedure to generate the next set of valid configurations and merge those that are the same.    #
###################################################################################################################
def next_configs(configs, probs, nr):
#
# When there are no cards remaining, we have the probability for the final configuration.
#
    if nr == 0:
        print(f"Probability = {probs[0]}")
        return
#
    configs_out = []
    probs_out = []
    nr_out = nr - 1
#
    for k in range(0,len(configs)):
        (a_temp, last_i_temp) = decode_config(configs[k])
        p_temp = probs[k]
#
        for i in range(1, 5):
            if a_temp[i] == 0:
                continue
#
            if i == last_i_temp and a_temp[i] ==1:
                continue
#
# Generate new probabilities for the next valid configurations
#
            if i == last_i_temp:
                p_out = p_temp*(i*(a_temp[i] -1))/nr
            else:
                p_out = p_temp*i*a_temp[i]/nr
#
# Generate and code next valid configurations
#
            last_i_out = i - 1
            a_out = [0,0,0,0,0]

            for n in range(0,5):
                if n == i:
                     a_out[n] = a_temp[n] -1
                elif n == i -1:
                    a_out[n] = a_temp[n] + 1
                else:
                    a_out[n] = a_temp[n]
#
            code_out = code_config(a_out, last_i_out)
#
# Check whether valid configuration already exists (and only add the probability if it does)
#
            code_found = False
#
            for m in range(0, len(configs_out)):
                if code_out == configs_out[m]:
                    code_found = True
                    probs_out[m] += p_out
                    break
#
            if not code_found:
                configs_out.append(code_out)
                probs_out.append(p_out)
#
    print_configs(configs_out, probs_out)
#
    next_configs(configs_out, probs_out, nr_out)
#
nr = 52
a = [0, 0, 0, 0, 13]
last_i = 0
#
code_a = code_config(a, last_i)
configs = [code_a]
probs = [1]
#
next_configs(configs, probs, nr)