0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ do you want to calculate the probability that all of the cards are greater than that value? $\endgroup$ – Jorge Fernández Hidalgo Jun 14 '17 at 0:00
  • 2
    $\begingroup$ Could you give an example to clarify the question? $\endgroup$ – AHusain Jun 14 '17 at 0:04
  • $\begingroup$ You’re going to have to provide more information: What is the composition of this deck of cards? Is a card replaced in the deck before drawing the next one? $\endgroup$ – amd Jun 14 '17 at 0:32
  • $\begingroup$ the decks composition is variable. the card is not placed back in the deck. I guess I will edit $\endgroup$ – Destructible Lemon Jun 14 '17 at 0:38
1
$\begingroup$

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]))
$\endgroup$
  • $\begingroup$ hmmm, I was kind of hoping there would be a cool way to do it... :/ +1 anyway $\endgroup$ – Destructible Lemon Jun 14 '17 at 23:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.