Problem 489989 · easy · Level 04 Non-Linear Data Structures

Is a Six Due?

law of large numbers · gambler's fallacy · seeded simulation · independence

A board-game player is convinced that after a long wait without a six, a six becomes more likely. Test the claim with a simulated die.

Write six_is_due(n, d, seed) that follows these rules exactly:

  • Create one generator rng = random.Random(seed) and roll the die n times with rng.randint(1, 6), one call per roll and no other use of randomness.
  • A roll comes after a drought when it has at least d rolls before it and none of the d rolls just before it was a six. (With d = 0 every roll comes after a drought.)

Return a dict with:

  • "share": the fraction of all n rolls that were sixes,
  • "gap": the number of sixes minus n / 6 (the count's distance from its expected value),
  • "after_drought": how many rolls came after a drought,
  • "share_after_drought": the fraction of those rolls that were sixes (0.0 if there were none).

Examples

Input:  n = 12, d = 2, seed = 1
Output: {"share": 0.08333333333333333, "gap": -1.0, "after_drought": 8, "share_after_drought": 0.125}
Explanation: the rolls are 2 5 1 3 1 4 4 4 6 4 2 1. One six, one fewer than 12 / 6.
The rolls at positions 2 to 8 and 11 (counting from 0) follow two rolls without a six;
one of those 8 rolls is the six.

Input:  n = 60000, d = 10, seed = 3
Output: {"share": 0.16525, "gap": -85.0, "after_drought": 10071, "share_after_drought": 0.1624466289345646}

With five times as many rolls (n = 300000, same seed), the share becomes 0.16589, closer to 1/6, while the gap grows to -233: the law of large numbers dilutes the imbalance rather than reversing it. And after a drought of 10 rolls, a six is no more frequent than usual (0.1647).

Constraints

  • 1 <= n <= 300000, 0 <= d <= 100, 0 <= seed < 2**32
  • floats are compared with a tolerance of 1e-6
  • the result must not depend on the clock or on any randomness other than rng

Goals

  • Simulate many independent trials with one seeded generator
  • See the share of an outcome settle while the count's distance from the expected count grows
  • Test the gambler's fallacy by looking only at trials that follow a drought
Starting Python…