Problem Statement
Suppose you have a fair dice with $$$m$$$ faces, numbered from $$$1$$$ to $$$m$$$. You roll this dice $$$n$$$ times independently, and each face has an equal probability of $$$ \frac{1}{m} $$$. Find the expected value of the maximum number obtained after these $$$n$$$ rolls.
Expected Maximum
If you roll an $$$m$$$-faced dice $$$n$$$ times, then there are $$$m^n$$$ possible combinations of rolls. The expected maximum is the average of the maximum values obtained from all $$$m^n$$$ combinations of rolls.
Intuition:
We have to compute the expected maximum value. That is:
Where $$$P(\max = i)$$$ = probability that the maximum number across $$$n$$$ rolls is exactly $$$i$$$.
Calculating $$$ P(\max = i) $$$
- Each dice roll can result in one of $$$m$$$ outcomes: $$$1$$$ to $$$m$$$.
- The probability that one roll gives a value ≤ $$$i$$$ is $$$\frac{i}{m}$$$.
- For $$$n$$$ independent rolls, the probability that all of them are ≤ $$$i$$$ is: $$$ P(\text{all rolls} \le i) = \left( \frac{i}{m} \right)^n $$$
Now,
So,
This formula gives the expected maximum of rolling an $$$m$$$ faced dice $$$n$$$ times without enumerating all possible outcomes (which would be $$$m^n$$$).
- Time Complexity: $$$O(m⋅logn)$$$
- Space Complexity: $$$O(1)$$$
Problem Link: 453A - Little Pony and Expected Maximum
Solution Link: 332049084
Well Explained!!
Challenge — Solve this for $$$m \leq 10^9$$$ and $$$n \leq 10^9$$$
Is this possible? if you could calculate this in something faster than $$$O(n+m)$$$ wouldn't that imply a faster-than-$$$O(n+k)$$$ way to calculate $$$\sum_{i=1}^ni^k$$$?
The EV here is (by tail sum formula) $$$E = \sum_{i=1}^m\left(1 - \left(\frac{i-1}{m}\right)^n\right) = m - \frac{1}{m^n}\sum_{i=1}^m (i-1)^n$$$, so if you can calculate $$$E$$$ quickly then $$$m^n(m - E) = \sum_{i=1}^{m-1}i^n$$$. I was under the impression that the RHS there cannot be calculated faster than the naive method for large $$$m$$$ and $$$n$$$ but perhaps that's wrong.
Sorry for my poor English, I meant to say one of the cases should hold. If both hold, then it is actually difficult.
Next, to find $$$\sum\limits_{i=1}^{n} i^k$$$, we can use lagrange interpolation the complexity is $$$O(k \cdot log(n))$$$, which definitely works for large $$$n$$$. So, the original problem can be solve in $$$O(min(m \cdot log(n), n \cdot log(m)))$$$.