Notes on the Ball and Urn Experiment

Java Applet Simulation of the ball and urn experiment

Reference

An amazing number of probability problems can be formulated in terms of ball and urn models. The authoritative reference for this theory is the book Urn Models and Their Application by Johnson and Kotz.

Simulating a Sample With Replacement

It's very easy to simulate a random sample of size n chosen with replacement from our population. First, recal that the ceiling of a real number t, ceil(t) is the smallest integer that is at least as large as t.

$Mathematical Exercise$ 1. Suppose that W is uniformly distributed on (0, 1) (a random number is a simulation of such a variable). Show that X = ceil(NW) is uniformly distributed on {1, 2, ..., N}.

$Mathematical Exercise$ 2. Suppose that W₁, W₂, ..., W_n are uniformly distributed on (0, 1). Let X_i = ceil(NW_i) for each i. Show that

(X₁, X₂, ..., X_n)

has the same distribution as a random sample of size n chosen with replacement from {1, 2, ..., N}.

Simulating a Sample Without Replacement

It's a bit harder to simulate a random sample of size n when the sampling is without replacment. The natural approach is to successively pick elements at random from the population, removing each chosen element from the population before the next draw.

$Mathematical Exercise$ 3. Show that the following algorithm generates a random permutation of size k from the population D:

For i = 1 to N, let b(i) = i.

For i = 1 to n,

Let j = N – i + 1

Let W = random number

Let J = ceil[(jW]

Let X(i) = b(J)

Let k = b(j)

Leb b(j) = b(J)

Let b(J) = k

Return (X(1), X(2), ..., X(n)).