Random Number Generator

Let $N$ be the number of times the number generator operates until the running total is $1$ or more. Thus $N$ is the smallest integer $n$ such that $X_1 + X_2 + \cdots + X_n \ge 1$ where each $X_j$ is uniformly distributed over $(0,1)$ , independently of all the others.

If we let $F_n(t) \; = \; \mathbf{P}[X_1 + X_2 + \cdots + X_n \le t]$ , then $F_1(t) = t$ for $0 \le t \le 1$ and $F_{n+1}(t) \; = \; \int_0^t F_n(t-u)\,du \hspace{2cm} n \ge 1\,,\,t > 0$ and it is a simple induction to show that $F_n(t) \; = \; \frac{t^n}{n!} \hspace{2cm} n \ge 1 \;,\; 0 < t < 1$ Thus we deduce that $\mathbb{P}[N \ge k] \; = \; \mathbb{P}[X_1 + X_2 + \cdots + X_{k-1} < 1] \; = \; F_{k-1}(1) = \frac{1}{(k-1)!}$ for all $k \ge 1$ , and hence $\mathbb{E}[N] \; = \; \sum_{k \ge 1} \mathbb{P}[N \ge k] \; = \; \sum_{k=1}^\infty \frac{1}{(k-1)!} \; = \; \boxed{e}$

For each $y$ in $[0,1]$ , let $E(y)$ be the expected number of times the machine should generate a number before the total sum is $y$ .

If any number in $[y,1]$ is generated, we are done. Otherwise $x$ in $[0,y]$ is generated with equal probability distribution, and it follows that

$\displaystyle E(y) = (1-y) + \int_{x=0}^{y} {(1+E(y-x)) dx}$

Integrating the $1$ and making the substitution $y-x = u$ , we get

$\displaystyle E(y) = 1 + \int_{u=0}^{y} {E(u)du}$ .

Take $\displaystyle 1+ \int_{u=0}^{y} {E(u)du} = f(y)$ , so that $E(y) = f'(y)$ .

Thus $f'(y) = f(y)$ , which gives $f(y) = Ce^{y}$ . But $f(0) = \displaystyle 1+ \int_{u=0}^{0} {E(u)du} = 1$ , clearly. So $C=1$ . Therefore

$E(y) = f'(y) = e^y$ , and $E(1) = e = \boxed{2.718}$

We may rephrase the problem: Suppose that the $n$ th number generated is $a_n$ . What is the expected number of times the machine will generate numbers such that $a_n > a_{n - 1}$ for $n > 1$ ?

This problem is slightly easier to deal with. Note that $E(X) = 1Pr(1) + 2Pr(2) + 3Pr(3) + ...$ where $X$ is the event and $Pr(k)$ denotes the probability of $k$ number being drawn.

Suppose that the machine has already generated $k - 1$ numbers and we are to generate a new one. We will find the probability of success. Since there exactly $k!$ orderings of $a_1, a_2, ... a_k$ , and only one satisfies the condition that $a_n < a_{n + 1}$ for all $1 \leq n \leq k - 1$ . Hence $Pr(k) = \frac{1}{k!}$ , or equivalently, $kPr(k) = \frac{1}{(k - 1)!}$ . From here, it is easy to see that the desired value is the famous constant $e$ .

Pre-solution nitpick: "randomly drawn" does not necessarily mean "randomly drawn from a uniform distribution" though our thinking seems to default to said distribution when no distribution is specified. I'm assuming a uniform distribution on $[0,1]$ for this problem.

Let $N$ be the number of random numbers drawn before we see a sum of at least 1. Then the event $[N > n]$ is equivalent to choosing n random numbers $x_1, x_2, ... x_n$ such that their sum is less than 1. This region of $n$ -space defines the $n$ -dimensional simplex, whose volume is known to be $\frac{1}{n!}$ . Let us call this number $V_n$ .

Then the event $[N = n]$ happens when the sum of the first $(n-1)$ numbers is less than 1, but the sum of the first $n$ numbers is not less than 1. This happens with probability $p_n = V_{n-1} - V_{n}$ = $\frac{1}{(n-1)!} - \frac{1}{n!}$ $= \frac{(n-1)}{n!}.$ To find the expected value of $N$ , (after noticing that p_1 = 0) we sum over all $n \geq 2$ the quantity $n*p_n$ .

I.e., $E[N] = \sum_{n=2}^{\infty} \frac{n*(n-1)}{n!} = \sum_{n=2}^{\infty} \frac{1}{(n-2)!} = \ldots$

(after re-indexing)

$E[N] = \sum_{k=0}^{\infty} \frac{1}{k!} = e$

I used code to simulate the situation several times.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

public class RandomNumber {
    public static void main(String[] args) {
        //number of times to test
        int trials = 50000000;
        //total times that we have used the RNG4000
        long totalCount = 0;
        //go through each trial
        for (int i = 0; i < trials; i++) {
            //variable representing the sum of generated random numbers
            double curNum = 0;
            //generate a random number until curNum is greater than 1
            while (curNum < 1) {
                //Add the random number between 0 and 1 to curNum
                curNum += Math.random();
                //increment totalCount
                totalCount++;
            }
        }
        //the mean is total/num trials
        double result = (double)totalCount / trials;
        //print out the result
        System.out.println(result);
    }
}