Mfrhtyj

The integers $1, 2, 3, 4, 5, 6, 7, 8, 9, 10$ are written on a blackboard. Each day, a teacher chooses one of the integers uniformly at random and decreases it by $1$. Let X be the expected value of the number of days which elapse before there are no longer positive integers on the board. Estimate $X$

The answer is given to be $120.7528$.

I solved it in the below manner and wonder if it is right.

Let $X_i$ be a random variable denoting number of trials required to hit 0. The discrete values it can take are $(1,2,.. i,0)$ where I club all non positive integers on trials to 0.

For $X_1$, the sample space is ${0,1}$. Actually, it should be represented by hypergeometric distrbution with the teacher striking down each integer by 1. As an approximation as the number of trials can be infinite, geometric distribution is used. Thus the probability of success for $X_1$ is $frac{1}{10}.frac{1}{2} = frac{1}{20}$. The probability of failure is $1-p_{success} = frac{19}{20}$.

Similary for $X_2$, the sample space is $(0,1,2)$ and the probability of success for $X_2$ is $frac{1}{10}.frac{2}{3} = frac{2}{30}$. and that of the failure is $= frac{28}{30}$.

And thus for $X_{10}$, the sample space is $(0,1,2,3,..,10)$ and the probability of success for $X_{10}$ is $frac{1}{10}.frac{10}{11} = frac{10}{110}$ and that of the failure is $= frac{100}{110}$.

Let us define the $X$ as the total number of trials required for the teacher to strike down all integers to 0.
Then $X = X_1+X_2+cdots+X_{10}$

$E(X) = E(X_1+X_2+cdots+X_{10}) = E(X_1)+E(X_2)+cdots+E(X_{10})$

$E(X_i) = frac{1-p_i}{p_i}$

I did the calculation and I hit a very close answer of $119.2897$ which is $1$ less the contest answer $120.7528$.

Let me know if the approach is right?. There is no solution provided so I do not know what approach they have taken.

The following solution confirms the answer of $120.7528$, but it may use more machinery than is appropriate for a contest.

An alternative way to view the problem is that we have ten bins and we toss a succession of balls into the bins, one at a time, with each bin chosen independently and with the equal probability. Let $T$ be the number of balls tossed when we first have $n$ balls in bin $n$ for all $n=1,2,3,dots,10$. We want to find the expected value of $T$.

To this end, let $a_n$ be the number of sequences of bin selections satisfying the constraint that bin $n$ contains at least $n$ balls for all $n$. Let $f(x)$ be the exponential generating function (EGF) of $a_n$. The EGF of the sequence of balls falling in a single bin $n$, since the bin must contain at least $n$ balls, is
$$frac{1}{n!} x^n + frac{1}{(n+1)!}x^{n+1} + frac{1}{(n+2)!}x^{n+2} + dots = e^x - sum_{i=0}^n frac{1}{i!} x^i$$
The sequence of all balls is the labelled product of the sequences for each of the bins, so
$$f(x) = prod_{n=0}^9 left( e^x - sum_{i=0}^n frac{1}{i!} x^i right)$$
This EGF counts the acceptable sequences of ball tosses. What we are really interested in is the associated probabilities; but given the EGF of the number of acceptable sequences, the EGF of the associated probabilities, in which each ball is tossed into bin $n$ with probability $1/10$, is simply $f(x/10)$. I.e., if $p_n$ is the probability that a sequence of $n$ tosses satisfies the fill requirement for all the bins, then the EGF of $p_n$ is $f(x/10)$.

If we would like to know the probability that a sequence does not satisfy the fill constraint, that probability is $q_n = 1-p_n$, which has the EGF $g(x) = e^x-f(x/10)$. Another way to look at $q_n$ is that it is the probability that $T >n $, where $T$ is the number of balls tossed when the fill requirement of the bins is first met. So
$$E(T) = sum_{n=0}^{infty} P(T>n) = sum_{n=0}^{infty} q_n$$
We can use the following trick to extract this infinite sum from the EGF of $q_n$. Because
$$int_0^{infty} x^n e^{-x} ;dx = n!$$
we have
$$sum_{n=0}^{infty} q_n = int_0^{infty} g(x) ; e^{-x} ; dx $$

The formula for $g(x)$ is quite complicated, so the prospect of computing this integral by hand is daunting, but a numerical integration using Mathematica is easy, with the result
$$E(T) = 120.75280$$

Not an answer but too long for a comment:

Monte Carlo shows that the answer 120.7528 is correct:

import java.util.HashMap;

import java.util.Map;

import java.util.Random;



public class SolutionCounter {



    public static int numDays(int maxNum) {

        Map<Integer, Integer> values = new HashMap<>();

        for(int i = 1; i <= maxNum; i++) {

            values.put(i, i);

        }

        Random rnd = new Random();

        int count = 0;

        while(values.size() > 0) {

            int pos = rnd.nextInt(10) + 1;

            if(values.containsKey(pos)) {

                int value = values.get(pos) - 1;

                if(value == 0) {

                    values.remove(pos);

                }

                else {

                    values.put(pos, value);                 

                }

            }

            count++;

        }

        return count;

    }



    public static void main(String args) {

        int runs = 0;

        long total = 0;

        while(true) {

            runs++;

            total += numDays(10);

            if(runs % 1000000 == 0) {

                String msg = String.format("Average after %d runs: %.6f", runs, (total / (double) runs));

                System.out.println(msg);

            }

        }

    }

}

Results after millions of runs:

Average after 1000000 runs: 120.732686

Average after 2000000 runs: 120.758270

Average after 3000000 runs: 120.749915

Average after 4000000 runs: 120.757830

Average after 5000000 runs: 120.759283

Average after 6000000 runs: 120.756646

Average after 7000000 runs: 120.755833

Average after 8000000 runs: 120.754364

Average after 9000000 runs: 120.754940

Average after 10000000 runs: 120.752258

Average after 11000000 runs: 120.748632

Average after 12000000 runs: 120.751920

Average after 13000000 runs: 120.753491

Average after 14000000 runs: 120.751542

Average after 15000000 runs: 120.751762

Average after 16000000 runs: 120.751637

Average after 17000000 runs: 120.753422

Average after 18000000 runs: 120.752132

Average after 19000000 runs: 120.753649

Average after 20000000 runs: 120.755102

Average after 21000000 runs: 120.754852

Average after 22000000 runs: 120.755027

Average after 23000000 runs: 120.755376

Average after 24000000 runs: 120.755810

However, I'm still trying to understand what's wrong with your method.