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?

Question

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?

Answer 1

(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.

Answer 2

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].$$

Answer 3

(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$.