Probability of a minimum sum of card values when drawing cards from a custom deck

Question

Apologies if this question has been answered -- I tried searching for an answer but wasn't sure what terminology to use.

Suppose I have a deck of cards, consisting of $n_1$ ones, $n_2$ twos, etc. (where each $n_x$ can be a different number).

I draw $k$ cards from the deck, and I want to know the probability that they will add up to at least $x$.

I'm looking for a general-purpose formula that I can use for different amounts and values of $n$s, and different values of $k$ and $x$.

Example:

I have a deck of 7 ones, 4 twos, 13 threes, and 9 fours. What is the probability of drawing 6 cards and having them add up to at least 13?

I have a basic knowledge of probability, but this problem has a few too many variables for me to work it out. An explanation of the solution would be most welcome, if anyone is willing and able.

Answer 1

I am almost sure the answer to such general question will not be an simple analytical formula, but it can be computed numerically.

First we start with a simple statement: if you choose m objects amongst n, and objects can be of 2 types (e.g. black and white - let there be n_b black objects), than the probability that the number of black objects among the selection $m_b$ is $$\binom{m}{m_b}\binom{n-m}{n_b - m_b} / \binom{n}{n_b} $$

I have used this formula to implement the algorithm below. The idea is that we iterate over denominations, and for each denomination we condition on how many cards of this denomination (black objects) were selected among whatever number of cards is remaining to select, given total number of cards that remain in the deck and total number of cards of this denomination.

It appears that, for the numbers you give, the answer to your question is 0.674

The code is below. I have checked it on a few simpler deck compositions, and it seems to give correct result, but please do check it yourself. It is written in Python, your can get it for free and run this code if you need it.

def binomialCoefficient(n, m):
    if (n-m) < m:
        return binomialCoefficient(n, n-m)
    result = 1.0
    for i in range(0, m): #0 inclusive, n+1 non inclusive
        result *= (n-i)
    for i in range(2, m+1): #m+1 inclusive, n+1 non inclusive
        result /= (i)
    return result

def probChooseQtyCardsGivenDenomination(qtyCardsDenomination, qtyCardsTotal, 
                                        qtySelectedDenomination, qtySelectedTotal): 
    return (binomialCoefficient(qtySelectedTotal, qtySelectedDenomination) 
           * binomialCoefficient(qtyCardsTotal - qtySelectedTotal, qtyCardsDenomination - qtySelectedDenomination)
           / binomialCoefficient(qtyCardsTotal, qtyCardsDenomination))

# we assume that deckDefinition starts with the biggest denomination
def findDistributionCards(deckDefinition, numberCardsToDraw):

    # initial value if howManyCardsRemain is the cards quantity
    totalNbCards = 0
    for _, cardsQuantity in deckDefinition:
        totalNbCards += cardsQuantity

    # while exploring the tree of possibilities, build an array (per level of tree)
    # which elements are, for each node at this level, 
    # 1. how many cards have already been drawn, 
    # 2. what is the sum of the points of these cards
    # 3. what is the probability to reach this node     
    nbDrawnCardsSoFar_sumValues_Probabilities = [[0, 0, 1.0]]
    for cardDenomination, qtyCardsDenomination in deckDefinition[:-1]: # -1 because we exclude the last element
        new_nbDrawnCardsSoFar_sumValues_Probabilities = []
        for nbDrawnCardsSoFar, sumValues, probability in nbDrawnCardsSoFar_sumValues_Probabilities:
            nbCardsRemainToDraw = numberCardsToDraw - nbDrawnCardsSoFar
            maxNbCanBeDrawn = min(qtyCardsDenomination, nbCardsRemainToDraw)
            for nbDrawnCardsOfThisDenomination in range(0, maxNbCanBeDrawn+1): # up to maxNbCanBeDrawn inclusive
                probToDrawThisNumberOfCards = probChooseQtyCardsGivenDenomination(
                                                    qtyCardsDenomination, totalNbCards, 
                                                    nbDrawnCardsOfThisDenomination, nbCardsRemainToDraw);
                new_nbDrawnCardsSoFar_sumValues_Probabilities.append([
                                                nbDrawnCardsSoFar + nbDrawnCardsOfThisDenomination, 
                                                sumValues + nbDrawnCardsOfThisDenomination * cardDenomination, 
                                                probability*probToDrawThisNumberOfCards]) 
        nbDrawnCardsSoFar_sumValues_Probabilities = new_nbDrawnCardsSoFar_sumValues_Probabilities
        totalNbCards -= qtyCardsDenomination

    # we rely on the fact that numberCardsToDraw < number of cards of the  last denomination
    resultDistribution = []
    last_denomination = deckDefinition[-1][0]
    for nbDrawnCardsSoFar, sumValues, probability in new_nbDrawnCardsSoFar_sumValues_Probabilities:        
        nbOfCardsOfTheLastDenomination = numberCardsToDraw - nbDrawnCardsSoFar
        resultDistribution.append([sumValues + last_denomination * nbOfCardsOfTheLastDenomination, probability])

    return resultDistribution    

if __name__ == '__main__':
    distribution = findDistributionCards(deckDefinition =  [[1, 4], [2, 4], [3, 4], [4, 4]], 
                                         numberCardsToDraw  = 2)
    cumulativeProbability = 0.0
    for sumValues, probability in distribution:
        if sumValues >= 8:
            cumulativeProbability += probability  

    print cumulativeProbability

    distribution = findDistributionCards(deckDefinition = [[1, 7], [2, 74], [3, 13], [4, 9]], 
                                         numberCardsToDraw  = 6)
    cumulativeProbability = 0.0
    for sumValues, probability in distribution:
        if sumValues >= 13:
            cumulativeProbability += probability
    print cumulativeProbability

Answer 2

[Note that this doesn't include number of draws]

Suppose we have a deck of cards of value $v$(minimum 1 and maximum n) and each cards multiples are $m_v$. The ways of selection cards so that their sum is $s$ are same as the coeffecient of $x^s$ in: $$\prod_{v=1}^n\left(\sum_{k=1}^{m_v}x^{kv}\right)$$ For your case that is equal to the coefficient of $x^{13}$ in: $$\prod_{v=1}^{4}\left(\large\sum_{k=0,0,0,0}^{7,4,13,9}x^{kv}\right)\\ =(x^8-1)(x^5-1)(x^{14}-1)(x^{10}-1)(x-1)^{-4}$$ That is equal to: $$\huge30$$