probability of a draw from a distribution of average digits being greater than y

53 Views Asked by At

Imagine the set of all strings of integers of length $n$. (So if n=1, it's just the set 0-9. If n=2, it's 00, 01,02...99, etc).

Now, $a(x)$ is defined as the average of digits in string $x$. So if $x=0123$, $a(x) =(0+1+2+3)/4 = 1.5$.

Let's call $A_n$ the set of values of $a(x)$ for every possible string of length $n$.

$A_1$ is a discrete uniform distribution from 0-9.

For $n>1$,$A_n$ starts to take the shape of a (discrete) bell-shaped curve with mean 4.5 and range 0-9. As $n$ increases, the density around 4.5 increases.

My question: As a function of $n$ and some number $y$, what is the probability of a draw from $A_n$ being greater than (or less than) $y$?

1

There are 1 best solutions below

3
On BEST ANSWER

We will compute the coefficient of $x^m$ in $$f(x)=\left(\frac{x^{10}-1}{x-1}\right)^n=\sum_{m=0}^\infty a_mx^m$$

This expression can be expanded as $$f(x)=\left(\sum_{k=0}^n(-1)^k\binom nk x^{10k}\right)\left(\sum_{j=0}^{\infty}\binom{j+n-1}{n-1}x^j\right)$$

So the coefficient of $x^m$ is:

$$a_m=\sum_{k=0}^{n}(-1)^k\binom nk \binom{m-10k+n-1}{n-1}$$

Given a random $Y,$ then $$P(nY=m)=\frac{a_{m}}{10^n}.$$

So you get:

$$\begin{align}P(nY<m) &=\frac1{10^n}\sum_{j=0}^{m-1} a_j\\ &= \frac1{10^n}\sum_{j=0}^{m-1} \sum_{k=0}^{n}(-1)^k\binom nk \binom{j-10k+n-1}{n-1}\\ &= \frac1{10^n}\sum_{k=0}^{n}(-1)^k\binom nk \sum_{j=0}^{m-1}\binom{j-10k+n-1}{n-1}\\ &= \frac1{10^n}\sum_{k=0}^{n}(-1)^k\binom nk \binom{m+n-10k-1}n \end{align}$$ This formula only works for $m=0,\dots, 10n.$

That’s not likely to have a much nicer formula.

Then $P(nY>m)=1-P(ny<m+1).$


Aside: I guess you can prove the formula for $P(Y<m)$ easier by seeing as the coefficient of $x^{m-1}$ in $f(x)/(1-x).$