Blackjack Probability

Tags

Blackjack Probability

Category

Recursion

Difficulty

Medium

Problem Statement

In a simplified blackjack game, you are dealt cards with values 1 through 10. You must draw cards until your hand total reaches or exceeds a given target value. Calculate the probability that you will bust (exceed the target). You are given the target value and a starting hand total.

Intuition

At each draw, you have an equal probability (1/10) of drawing any card from 1 to 10. If your current total is below the target, you must draw. If drawing a card puts you over the target, you bust. We can recursively compute the probability of busting from any hand total, using memoization to avoid redundant calculations. The key insight is that once your total reaches or exceeds the target, you stop drawing.

Approach

  1. Define a recursive function that takes the current hand total.
  2. Base case: if the current total >= target, return 0 if total <= target (safe stop) or return 1 if total > target (busted). More precisely, if currentTotal >= target, you stop. You bust only if currentTotal > target.
  3. Wait - you draw until you reach or exceed target. So if currentTotal >= target, you stop. Busting means currentTotal > target at that point.
  4. Recursive step: if currentTotal < target, you draw a card. The probability of busting is the average of the probabilities of busting after drawing each card (1 through 10).
  5. Use memoization keyed on the current total to avoid recomputation.
  6. Call the function with the starting hand total.

Pseudocode

function blackjackProbability(target, startingHand):
    memo = {}
    return calculateBustProbability(startingHand, target, memo)

function calculateBustProbability(currentHand, target, memo):
    if currentHand in memo:
        return memo[currentHand]
    if currentHand > target:
        return 1.0
    if currentHand >= target:
        // currentHand == target exactly, we stop and don't bust
        return 0.0

    // We must draw: equal probability for cards 1..10
    totalProbability = 0
    for card from 1 to 10:
        totalProbability += calculateBustProbability(currentHand + card, target, memo)

    memo[currentHand] = totalProbability / 10.0
    return memo[currentHand]

Time & Space Complexity

  • Time: O(t * 10) = O(t) where t is the target value. Each unique hand total from startingHand to target + 10 is computed once, and each computation considers 10 possible draws.
  • Space: O(t) for the memoization table and recursion stack.

Key Insights

  • The problem has overlapping subproblems: many paths lead to the same hand total, making memoization highly effective.
  • The state space is one-dimensional (just the current hand total), making this very efficient to memoize.
  • You stop drawing when your hand total >= target. Busting only happens if you go strictly over.
  • Cards have equal probability (1/10 each), simplifying the probability calculation.

Edge Cases

  • Starting hand already >= target: if equal, probability is 0 (you stop and are safe); if greater, probability is 1.0 (already busted).
  • Target of 1: any card drawn will be >= 1, so if starting hand is 0, you never bust (you stop immediately upon drawing).
  • Very large target: more draws are needed, but memoization keeps it efficient.
  • Starting hand of 0: you must draw at least once.

Linked mentions