5
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Very nice. (+1) $\endgroup$ – Markus Scheuer Jan 11 at 8:14
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.