4
$\begingroup$

One hundred Random Digits

    00-04 05-09 10-14 15-19
===========================
00  54463 22662 65905 70639
01  15389 85205 18850 39226
02  85941 40756 82414 02015
03  61149 69440 11286 88218
04  05219 81619 10651 67079

I just started reading up on random number tables, but Im not really sure how to read the above table/interpret the data. How would I go about to draw a random sample of size $n =10$ without replacement from a numbered population of size $N=100$? And also a random sample of size $n=15$ without replacement from a numbered population of size $N=123$?

$\endgroup$
  • 3
    $\begingroup$ Is this a homework exercise or are you actually trying to generate random numbers in this way? If it is homework, please add the homework tag; if it's not homework my advice would be to put away the table and use a computer $\endgroup$ – Macro Jun 26 '12 at 12:18
5
$\begingroup$

A random number table is designed to create uniformly distributed values; this use is straightforward. The somewhat tricky part to do correctly and efficiently is to sample without replacement. I will describe this because it is a useful algorithm for any statistician to know: random permutations are very important (for resampling and bootstrapping, for instance) and, because they may be generated a huge number of times, efficiently generating them can be essential.

Selecting elements of a population

Usually, one designates a starting entry in the table and a rule for selecting sequences of digits. For instance, for sampling from $100$ objects, first number them from $0$ through $99$ in any order you like. Without referring to the table, you might stipulate that you will start in row 3, column 1 and pick every other digit, grouping them in pairs. This determines the sequence

89, 10, 58, 44, ...

Via your numbering system you will interpret this sequence as elements of the population.

When $N$ is not a power of $10$ you can proceed in several ways. Perhaps the most efficient is to partition the random digits into longish groups, interpret them as values in the interval $[0,1)$ by placing an implicit decimal point in front of them, multiplying those by $N$, and rounding down. For example, with $N=123$ items numbered from $0$ through $122$ and again starting in row 3 column 1, this time grouping the digits in sixes, you would produce

123 * .859414 = 105, 123 * .075682 = 9, 123 * .414020 = 50, 123 * .156114 = 19, ...

This can be performed in the field without any tools at all (apart from pencil and paper if you need those for the multiplications).

Sampling without replacement

The most straightforward way to accomplish this is simply to remove duplicates as they are encountered in the sequence of indexes generated above. Two tricks are frequently employed when doing this manually (in the field) or by computer with very large populations.

The first one is that when sampling more than half the population, instead identify the elements that are not needed (without replacement), then just keep the rest for the sample.

There is an elegant algorithm to avoid searching for duplicates. It generates a random permutation (an ordered subset of the population of specified size); the ordering is useful in its own right. You begin by writing the identifiers of the population in any sequence you like. As an example, if we were to sample from a population of $N=10$ of individuals named {a,b,c,d,e,f,g,h,i,j}, we would begin with, say, this array preceded by a set of the elements put into the sample so far (none of them):

    {}, a b c d e f g h i j

Generate a sequence of random numbers as before. For this example let's use the previous sequence .859414, .075682, .414020, ... . Because the array currently has $10$ elements in it, we use the first random number from the table to compute the random index 10 * 0.859414 = i. Interpret this as an index*into the array, remembering the array indexes must start at $0$. Swap the marked element of the array with the element at this index, keep the new element at the first index for your sample, and then drop the first element from the array altogether, leaving this:

    (i), b c d e f g h a j

Repeat, bearing in mind the array now has only $N-1$ = $9$ elements. So we use the second random value from the table to compute 9 * 0.075682 = 0. That happens to designate the first element of the remainder of the array, which is swapped with itself and also put into the growing sample:

    (i, b), c d e f g h a j

Another repetition produces the index 8 * .414020 = 3, identifying the value f in the array, which is swapped with the initial c:

    (i, b, f), d e c g h a j

You can see that the only actual changes made to the array are the swaps: the random permutation--here (i, b, f)--automatically appears in the first $k$ entries of the array after $k$ swaps are performed in this manner. In this fashion you can generate a random $k$-permutation by means of just $k$ (uniformly distributed) random numbers and $k$ swaps: a highly efficient procedure. Moreover, in cases where the sample size is not fixed in advance, this procedure can be iterated with the remaining non-sampled elements.

BTW, to prove that all permutations are equally likely to occur in this algorithm, note that all elements of the population have equal chances of being the first chosen. The proof is finished by induction (because this is a recursive algorithm).

$\endgroup$
3
$\begingroup$

Michael Chernick's method will be exact for $N=100$, but will have slight imbalances and unequal probabilities of selection for $N=123$ due to small discretization error.

For $N=100$, I would go with just two digits in the table, so my sample of size $n=10$ would be comprised of units 54, 46, 32, 26, 62, 65, 90, 57, 6 and 39 (the 00 combination maps to 100).

For $N=123$, you'd have to observe that $123\times8 = 984$, so it would be handy to use the triples of numbers $\mod 123$, and discard some $16/1000=1.6$% of the combinations. So the sample of size 10 would consist of units $ 544 (\mod 123) = 52$, $632 (\mod 123) = 17$, $266 (\mod 123) = 20$, etc. 000, 123, 246 combinations map to the unit numbered 123.

If you encounter duplicates, while you want to sample without replacement, you can either omit the duplicates, or shift by one digit, or omit the whole sample.

Random digit tables, as well as $t$-tables and $F$-tables in the back of your statistics textbooks, are basically the Ptolemaic system in statistics. Yes, they do work with some accuracy. But since their invent, things have changed computationally, and better accuracy methods are available these days.

$\endgroup$
  • $\begingroup$ Random number tables still have several advantages over pseudorandom number generators. One is that they provide the clearest possible documentation of how a random number sequence will be (or was) produced. Another is that they need no technology to use, which to some people in the field can be very useful (they still work when your batteries run out; they are lightweight; they can work in rain, snow, sand, and under water, etc.). And they are completely accurate. If anything, the onus is on the pseudo-RNGs to demonstrate their "accuracy." $\endgroup$ – whuber Jun 26 '12 at 14:48
  • 1
    $\begingroup$ @whuber, that's a philosophical debate, I guess. I am a believer in the right tool for the problem, and for most applications, I would see the PRNG to do appropriate job. The tables are only as accurate as the method that produced them. And you can produce computer-readable truly random numbers from random.org or special physical devices, although they won't be reproducible. And of course you can laminate your random number table and take it under water (although I sorta doubt people really do that, frankly; I'd be curious to see myself mistaken though :) ). $\endgroup$ – StasK Jun 26 '12 at 15:35
  • 1
    $\begingroup$ You're right, Stas. But every few years I do find occasion to use a random number table (and each time I think it's the last time I will ever do so...). $\endgroup$ – whuber Jun 26 '12 at 18:03
0
$\begingroup$

In general you start with N objects out of which you want to choose k at random. Select a uniform random number. Interpret a number U such as 54463 as 0.54463. Since you have index numbers 1, 2, 3,.., N to choose from pick index 1 0 < U <=1/N , 2 if 1/N < U <=2/N,..., N if (N-1)/N < U <=1. Now after doing that you have N-1 index numbers left to pick k-1 out from. Reorder the indices from 1 to N-1 and pick index 1 if 0 < U <= 1/(N-1), 2 if 1/(N-1) < U <=2/(N-1),..., N-1 if (N-2)/(N-1) < U <=1. Continue in this way until all k indices have been selected.

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