A wavy histogram from a maximum likelihood algorithm

Question

This question is based on a Puzzling Stack question I answered.

Suppose you have a loaded $10$-sided die that gives one value with probability $\frac7{25}$ and the rest with probability $\frac2{25}$ each, but you do not know the favoured value. A maximum likelihood method to determine this favoured value is as follows:

1. Set probabilities $p_1=\dots=p_{10}=\frac1{10}$, where $p_i$ is the likelihood of $i$ being the favoured value.
2. Roll the die repeatedly; for each value $c$ that comes up multiply $p_c$ by $3.5$, the ratio of probabilities of a favoured face to an unfavoured face. Normalise after each update and stop when one $p_i$ becomes dominant enough.

This strategy is quite efficient, for simulating it $4121000$ times gave a mean of about $35.47$ rolls until one $p_i$ exceeded $0.99$ and a median of $32$ rolls. The histogram of rolls needed, however, looks very odd with its wavy top:

Is there any logical explanation for the histogram's peculiar shape? The number of simulations I made certainly seems high enough to rule out sample size as an explanation.

---

Here is the histogram corresponding to a d3 with one value twice as likely ($1/2$) to come up as the other two ($1/4$): Clearly there is a dependence on the number of possibilities, but what kind?

Answer 1

This can be computed more exactly using a Markov chain, but my impression is that you're looking for some sort of intuitive explanation.

Suppose we rolled all 10 numbers once. Each number would have its factor multiplied by 3.5 (before normalization), but since all numbers get the same factor, the result after normalization is unchanged.

Thus, a crude approximation is that the cumulative process at exit time is the sum of two types of sets of rolls:

• A set of 1 roll in which only the favored number is rolled, which results in progress towards the 0.99 threshold. Specifically, the favored number's factor has to grow from 1 : 9 to 99 : 1, which is $\log(99 \cdot 9) / \log(3.5) \gtrapprox 5.42$ occurrences of this set.
• A set of 10 rolls in which each number is rolled once, which results in zero net progress towards the 0.99 threshold.

If this approximation was exact, we would have nonzero probabilities at 6, 16, 26, 36, ... and zero probability everywhere else, since exactly 6 of the first type of set is rolled and some integer number of the second type. This approximation isn't exact, because you will get partial sets of the second type, some non-favored numbers might be rolled more than others, etc. which smooths out those spikes---but not completely.

Answer 2

To corroborate Oscar Cunningham’s comment and HighDiceRoller’s answer, here’s a histogram disaggregated according to the number of times the favoured face came up. The aggregated histogram is the purple one. You can see nicely how it’s composed of the individual components whose spread and overlap increases with the number of favoured rolls; at low values they’re sufficiently separated to make their peaks stand out in the sum.