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