# If someone wins 3000 rounds of a game out of 100000 numbered rounds of a game, what is the expected no. of last-3-digits of a round that they solved?

I participate in r/picturegame on Reddit. Each round is numbered from Round 0 (1 actually, but let's say it was 0) up to Round 111400 at the moment.

Suppose the top player of this game had won 3000 rounds out of all the rounds up to and including round 99999 and has been playing since the beginning (this is roughly true and keeps the numbers convenient I think.) Let's also suppose that he isn't especially trying to win rounds of a certain number, and the round numbers don't follow any particular pattern relative to his sleep schedule. (This is also realistic.)

Now let's take the last 3 digits of each round that he won, so round 89345 would be "345", round 40080 would be "080" and (for the sake of argument) round 66 would be "066".

Out of the 3000 rounds that he won, what is the expected number of round-endings, from "000" to "999", that are not represented amongst those rounds?

• Are you looking for an exact or approximate answer? May 19 at 1:51
• I was hoping for an exact answer based on math. I have run a little simulation in Python already to find an approximate answer. I mean I guess it depends how approximate we are talking... May 19 at 1:53
• According to the simulation, the answer is ~48.8. May 19 at 2:18
• Randomly choosing distinct integers is nontrivial programming. May 19 at 20:00

## 3 Answers

(Note: close but not quite correct approach) A simple way to look at this problem is to say that wins happen $$3\%$$ of the time, so on any given round a particular set of ending digits has a $$97\%$$ chance of not being a winner. Each set of ending digits occurs $$100$$ times among the full set of rounds, giving $$.97^{100}$$ as the chance that set will never be a winner. Apply this as the average across all the sets of digits to get $$.04755...$$ or $$4.755\%$$ of the $$1000$$ sets of digits that will not be winners on average.

Edit:

As noted in comments below, the simplistic approach detailed above gives an approximation but is not quite correct. In particular, for a given set of digits which occurs $$100$$ out of $$100000$$ rounds, there is the chance that one of the $$999$$ other digit sets will be winners in each of $$3000$$ wins. This happens

$$\frac{\binom{99900}{3000}}{\binom{100000}{3000}}$$

percent of the time when considering the count of such events among the total set of $$3000$$ wins in $$100000$$ rounds. That the numbers work out pretty close to equal is a misleading coincidence.

• I think this is slightly inaccurate, since winning 3000 out of 100000 rounds is not exactly the same as 3% chance of winning. For example, the latter includes the unlikely possibility of losing every round (and winning every round too), while the former does not. I think the correct probability is not $.97^{100}$, but $\binom{99900}{3000} / \binom{100000}{3000}$. But this is approximately $.04748$, which is close to your answer anyway. May 19 at 3:28
• The latter is the answer that someone gave on Reddit: reddit.com/r/askmath/comments/ust0to/… As the answers were so similar, I accepted this answer before your comment VTand. I'm still a little confused as to why my Python script gives ~48.8 pretty consistently, maybe there's a bug in it... May 19 at 3:37
• @VTand thank you for correcting my approach. May 19 at 4:00
• @abiessu Regarding your last sentence of your edit, I don’t think it is a coincidence. Sampling with and without replacement should be pretty much the same if the sample size is really small compared to the population size. May 19 at 5:19
• My simulation suggested a figure slightly lower than your $47.55$, perhaps just below $47.5$ May 19 at 9:15

This is a bizarre problem.

I can give you a somewhat ugly closed form expression for the computation. However, you will clearly need to write a computer program to evaluate the expression. Probably, logarithms will be involved in your computer program. Anyway...

There is a point of ambiguity. The player is (in effect) sampling $$3000$$ numbers from $$\{00000, 00001, 00002, \cdots, 99998, 99999\}.$$ However, it is unclear whether the sampling is done with or without replacement. I will first make the simplifying assumption that the sampling is done with replacement. Then, at the end of my answer, I will accommodate the alternative assumption.

Let $$f(k,n)$$ denote the probability that when $$k$$ numbers are sampled, that exactly $$n$$ of the possible $$1000$$ endings occur, among the $$k$$ entries. Here, the endings are construed to be $$\{000, 001, \cdots, 998, 999\}.~$$ So, for the function $$f(k,n)$$, you have that $$k \in \{1,2,\cdots,3000\}$$ and $$n \in \{1,2,\cdots,1000\}.$$

Then, the desired computation will be

$$\sum_{n=1}^{1000} n \times f(3000,n). \tag1$$

So, the problem has been reduced to providing a formula for $$f(3000,n)$$.

I will use recursion. Clearly, when $$n > k,$$ you have that $$f(k,n) = 0.$$

Also, you have that $$f(1,1) = 1.$$

Then, $$\displaystyle f(2,1) = f(1,1) \times \frac{1}{1000}$$

and $$\displaystyle f(2,2) = f(1,1) \times \frac{1000 - 1}{1000}.$$

Unfortunately, to apply this approach, for each value of $$k \leq 1000$$, you have to compute the $$k$$ variables of

$$f(k,1), f(k,2), f(k,3), \cdots, f(k,k).$$

Thereafter, once $$k$$ equals or exceeds $$1000$$, you have to compute the variables

$$f(k,1), f(k,2), f(k,3), \cdots, f(k,1000).$$

One nice thing about this approach is that when the value of $$k$$ changes from $$K$$ to $$(K+1)$$, and you compute all of the necessary $$f(K+1,n)$$ variables, you can then discard all of the $$f(K,n)$$ variables, as no longer needed.

$$f(K,1) = \binom{1000}{1} \left(\frac{1}{1000}\right)^K. \tag2$$

For $$n \geq 2,$$ to compute $$f(K+1,n)$$ you need to specifically access $$f(K,n-1)$$ and $$f(K,n)$$.

$$f(K+1,n) = \left[f(K,n-1) \times \frac{1000 - (n-1)}{1000}\right] + \left[f(K,n) \times \frac{n}{1000}\right]. \tag3$$

Note that in (3) above, the maximum value of the $$n$$ to be computed will be $$~\displaystyle \min\left(K+1,1000\right).$$

So, using recursion with (2) and (3) above, the computation in (1) above can be programmatically computed.

Now, I explore the somewhat ugly assumption that the sampling is done without replacement.

The first question is, what is $$f(K,1).$$ To consider this, suppose (for example) that $$K_1 = 75$$ and $$K_2 = 140.$$ Further suppose, that you are exploring the $$001$$ ending. There are only $$100$$ such endings, out of the numbers $$00000$$ through $$99999$$. This means that the probability that the first $$75$$ numbers all end in "001" is

$$\displaystyle \frac{\binom{100}{75}}{\binom{100000}{75}}.$$

Therefore,

$$f(75,1) = \binom{1000}{1} \times \frac{\binom{100}{75}}{\binom{100000}{75}}.$$

Assuming that you accept the convention that when $$k > n$$, that $$~\displaystyle \binom{n}{k} = 0,$$ you then have that

$$f(140,1) = \binom{1000}{1} \frac{\binom{100}{140}}{\binom{100000}{140}}.$$

So, you have the general formula that

$$f(K,1) = \binom{1000}{1} \frac{\binom{100}{K}}{\binom{100000}{K}}.$$

The only adjustment remaining is to describe how the $$f(K,n-1)$$ and $$f(K,n)$$ variables are then used to compute $$f(K+1,n)$$. In order to do this, I am going to create a helper function $$g(k,n)$$.

I want $$g(k,n)$$ to represent the number of items remaining from a group of $$(100 \times n)$$ items, after $$k$$ of these items have been removed. So, I will specify:

$$g(k,n)$$ equals:

• $$0$$, if $$100n - k \leq 0.$$
• $$100n - k$$, otherwise.

The event that $$K$$ numbers have had exactly $$n-1$$ endings represents that the $$K$$ numbers have all been drawn from the group of $$(n-1) \times 100$$ numbers, with one of the pertinent endings. This implies that there are $$g(K,n-1)$$ numbers remaining with this pertinent ending. This implies that the probability that the $$(K+1)-th$$ number will have a different ending is

$$\frac{100000 - K - g(K,n-1)}{100000 - K}.$$

Similarly, the event that $$K$$ numbers have had exactly $$n$$ endings represents that the $$K$$ numbers have all been drawn from the group of $$(n) \times 100$$ numbers, with one of the pertinent endings. This implies that there are $$g(K,n)$$ numbers remaining with this pertinent ending. This implies that the probability that the $$(K+1)-th$$ number will have the same ending is

$$\frac{g(K,n)}{100000 - K}.$$

Putting this all together, you have that

$$f(K+1,n) = \left[ ~f(K,n-1) \times \frac{100000 - K - g(K,n-1)}{100000 - K} ~\right]$$

$$+ \left[ ~f(K,n) \times \frac{g(K,n)}{100000 - K}~\right].$$

• This is a truly exceptional answer, much more detailed than I was expecting and probably much better than the question (and its origin) deserved! I'm not sure whether it would be polite to change the accepted the answer to this one. May 19 at 4:39
• For context, on Picture Game we have the actual numbers in question (this player is missing 41 3-digit endings at the moment, after 3300 wins in fact) and someone said that they expected this number to be closer to 100 or so. I thought their overestimate/retrospective guess was possibly related to the Birthday Paradox and I was very curious about the math behind these numbers. Thank you so much for supplying it! May 19 at 4:47
• @R1s1ble my simulation suggested you might expect to see $41$ or less about $17\%$ of the time with $3000$ cases and about $89\%$ of the time with $3300$ cases. So $41$ is not extremely low May 19 at 9:19
• @R1s1ble and the analytical expected number is about $47.5$ with $3000$ cases but the noticeably smaller $34.8$ with $3300$ cases May 19 at 12:08
• It should be clear the sampling is without replacement. One can only solve each problem once. May 19 at 14:04

(I had several false starts on this problem due to wrongly reading the problem statement. Here's hoping I finally have it right.)

Suppose we write each of the integers from $$0$$ to $$999$$ on $$m$$ balls each, so there are $$1000m$$ balls in all. We draw $$n$$ balls from the mix without replacement, with each ball equally likely to be selected. Winning $$3000$$ games out of $$100000$$ corresponds to this model with $$n=3000$$, $$m=100$$. Define $$X_i = \begin{cases} 1 \qquad \text{if no ball labelled i is drawn} \\ 0 \qquad \text{otherwise} \end{cases}$$ for $$0 \le i \le 999$$. Then $$P(X_i = 1) = \frac{\binom{999m}{n}}{\binom{1000m}{n}}$$ The total count of numbers not found is $$\sum_{i=0}^{999} X_i$$, and by linearity of expectation, $$E \left( \sum_{i=0}^{999} X_i \right) = \sum_{i=0}^{999} E(X_i) = 1000 \left( \frac{\binom{999m}{n}}{\binom{1000m}{n}} \right)$$ For $$m=100$$ and $$n=3000$$, the result is $$47.480$$.

• Your application of linearity of expectation means you should not be multiplying by $n$ but by $1000$ (the number of possible final three digits), which is why your answer is exactly three times too high May 19 at 14:44
• @Henry Oops! Thank you, corrected. May 19 at 17:25