Probability a draw-until-threshold score ends at or below a limit

A player starts with 0 points and draws repeatedly. Each draw adds an integer chosen uniformly at random from 1 to max_points (inclusive) to the player's total, independently of all other draws. The player keeps drawing while the total is strictly less than threshold and stops as soon as the total reaches threshold or more. Return the probability that the final total is at most limit.

Function Signature

def probability_within_limit(limit: int, threshold: int, max_points: int) -> float:

Rules

• If threshold is 0, the player never draws and the final total is 0.
• Return the probability as a float. An answer is accepted if it is within 1e-5 (absolute) of the exact probability.

Constraints

• 0 <= threshold <= limit <= 10^4
• 1 <= max_points <= 10^4

Examples

Example 1

Input:  limit = 6, threshold = 1, max_points = 10
Output: 0.6

The player draws exactly once and stops. The total is uniform on 1 to 10, and 6 of those 10 values are at most 6.

Example 2

Input:  limit = 2, threshold = 2, max_points = 2
Output: 0.75

With probability 0.5 the first draw is 2 and the player stops at 2. Otherwise the total is 1 and the player draws again, ending at 2 or 3 with probability 0.5 each. The final total is at most 2 with probability 0.5 + 0.25 = 0.75.

Example 3

Input:  limit = 4, threshold = 3, max_points = 3
Output: 0.85185

The final total is 3, 4 or 5 with probabilities 16/27, 7/27 and 4/27, so the answer is 23/27, about 0.85185.