Probability of success in a simplified welcome to the dungeon game

Question

This is for a game, calculating the probability of success if one were to enter the dungeon, but removing the game and simplifying, it comes down to this:

Given a set of cards with numbers on, and a number of cards to draw, what is the probability the sum of the cards is greater than or equal to a specified number?

The deck is a specified variable, and cards are removed once drawn.

kinda bad example because I don't know how to calculate non trivial things efficiently yet which is why I'm asking

specified number to draw: 1

deck: 1 1 1 2

number to reach: 2


= probability: 1/4

I know that if I wanted to calculate the expected value, I would just get the expected value of each card and multiply by the cards drawn, because of magic expected value maths, but this obviously does not apply here, because the expected value is a compromise between probability and effect.

Answer 1

The easiest way to do this is to write a program. Like this Python program:

from fractions import Fraction

def prob_of_success(to_draw, goal, deck):
    # state[i][j] will be the number of ways to get to j so far with i
    # cards drawn.  We can be at 0, 1, ... , to_draw which is to_draw + 1
    # possibilities.
    state = [[] for _ in range(to_draw + 1)]

    # We start with 1 way to get to 0 with 0 cards drawn.
    state[0] = [1]

    for card in deck:
        # state already represents ways to not draw this card.
        # We need to add the possibilities where we do.
        # We update from the most cards back.
        for i in reversed(range(to_draw)):
            for k in range(len(state[i])):
                result = min(card + k, goal)
                while len(state[i+1]) <= result:
                    state[i+1].append(0)
                state[i+1][result] = state[i+1][result] + state[i][k]
    if len(state[to_draw]) <= goal:
        return Fraction(0, 1)
    else:
        return Fraction(state[to_draw][goal], sum(state[to_draw]))

# Example usage
print(prob_of_success(2, 3, [1, 1, 1, 1, 2]))