Normal approximation to a dice total

The central limit theorem says a total of many dice is nearly normal. Compare the exact probability with the normal approximation.

What to build

A program that computes P(total ≤ s) exactly and approximately.

Requirements

  • Print exact A (the exact P(total of n dice ≤ s)), normal B (the normal approximation with continuity correction) and difference D (the size of A − B), each to 4 decimal places.

Input

One line: n and s.

Output

Three lines.

Constraints

1 ≤ n ≤ 30; n ≤ s ≤ 6n.

Example

Input:

2 7

Output:

exact 0.5833
normal 0.5820
difference 0.0013

Why it works

One die has mean 3.5 and variance 35/12, independent dice add both, and adding 0.5 lets the smooth curve cover the whole bar of the total s.

Examples

Example 1 · Input
2 7
Expected output
exact 0.5833
normal 0.5820
difference 0.0013
Example 2 · Input
10 35
Expected output
exact 0.5363
normal 0.5369
difference 0.0005

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

Exact: build the counts of each total die by die, then add those up to s and divide by 6ⁿ.

Hint 2

Approximate: mean 3.5n, variance 35n ÷ 12, and the normal area up to s + 0.5.

Solution

Show one correct solution (try it yourself first)
from math import erf, sqrt

n, s = map(int, input().split())
ways = {0: 1}
for _ in range(n):
    nxt = {}
    for total, count in ways.items():
        for face in range(1, 7):
            nxt[total + face] = nxt.get(total + face, 0) + count
    ways = nxt
exact = sum(c for total, c in ways.items() if total <= s) / 6 ** n
z = (s + 0.5 - 3.5 * n) / sqrt(35 * n / 12)
normal = 0.5 * (1 + erf(z / sqrt(2)))
print(f"exact {exact:.4f}")
print(f"normal {normal:.4f}")
print(f"difference {abs(exact - normal):.4f}")

Lesson: Sampling and the central limit theorem →