What is the probability of getting the exact number of expected digits ($0-9$) in $10^6$ digits of $\pi$?

Question

I noticed that at $1$ million digits of $\pi$, none of the digits has the "perfect" expected $100{,}000$ occurrences. My question is what is the probability (if the digits are truly random) of at least one of the digits having the "perfect" # of occurrences (in this case $100{,}000$)? To be more accurate as one reader pointed out, what is the probability of $1$ million randomly generated digits from $0$ to $9$ having this property?

Answer 1

First an exact answer, then an approximate one.

The number of sequences in which the digit $0$ appears exactly 100,000 times is $\binom{1000000}{100000}9^{900000}$.

The number of sequences in which $0$ and $1$ each appear exactly 100,000 times is $\binom{1000000}{100000}\binom{900000}{100000}8^{800000}$.

In general, the number of sequences in which the first $k$ digits each appear exactly 100,000 times is $$ (10 - k)^{1000000 - 100000k} \prod_{i=0}^{k-1} \binom{1000000 - 100000i}{100000}.$$

Using the inclusion-exclusion formula, the probability of at least one digit appearing exactly 100,000 times is $$10^{-1000000}\sum_{k = 1}^{10} (-1)^{k-1} \binom{10}{k} (10 - k)^{1000000 - 100000k} \prod_{i=0}^{k-1} \binom{1000000 - 100000i}{100000}.$$

I'm not sure what this number works out to be (though it seems feasible to put it into a computer), but if you call $X$ the number of times you get the digit $1$, it can be approximated by a normal variable with mean 100,000 and standard deviation $[1000000 (0.1)(0.9)]^{1/2} = 300$. So the probability that $X = 100000$ will be quite close to $\frac{1}{300\sqrt{2\pi}}$. I think the probability of more than one digit occurring exactly 100,000 times is relatively small, so I would expect the answer to be quite close to $10$ times this number, namely $\frac{1}{30\sqrt{2\pi}}$. This estimate can be improved by using a normal (or Stirling) approximation for the second term in the formula above.

EDIT: The first-level approximation gives you a probability of 1.3298%. The more accurate second-level approximation gives you a probability of 1.3218%.

EDIT: Using the full inclusion-exclusion formula, I get $1.321827895126123\%$.

Answer 2

Consider a specific digit ($7$, say). The probability of $k$ $7$'s in $n$ random digits is (see here)

$$\binom{n}{k}\left(\frac{1}{10}\right)^k\left(\frac{9}{10}\right)^{n-k}$$

With $n=1,000,000$ and $k=100,000$, Wolfram Alpha evaluates this as 0.001329806480909191...

This agrees with user187373's approximation $\frac{1}{300\sqrt{2\pi}} \approx 0.001329807601338108...$ to six significant figures, which supports user187373's final probability of $\frac{1}{30\sqrt{2\pi}}$ (about $1$ in $75$).

Answer 3

The problem is equivalent to throwing $N=10^6$ balls into $m=10$ urns (equiprobably) and asking for the probability that at least one urn $i$ has $X_i=N/m$ balls.

This can be approximated (Poissonization) as $m$ iid Poisson variables $Y_i$ with mean $\lambda=E(X_i)=N/m$

The probability that one given urn gets $Y_i=\lambda$ balls is

$$p = \frac{\lambda^\lambda}{\lambda!} e^{-\lambda} \approx \frac{\lambda^\lambda}{(\lambda/e)^\lambda \sqrt{2 \pi \lambda}} e^{-\lambda}= \sqrt{ \frac{m}{2 \pi N}} \approx 0.00126$$

The probabilty that some ball gets $Y_i=\lambda$ is $ 1-(1-p)^m \approx $ (which can be approximated by $m \, p$ - if you want to).

Then, the desired probability is $0.012544\cdots$

Both approximations (the Poissonization and the Stirling formula) can be refined. Anyway, it's seen that the probability decreases as $1/\sqrt{N}$. Notice, BTW, that this gives the probability of "success" for fixed $N=10^6$ , not for all "tries" $n\le N$ - which would be a more difficult problem.