Top web site - 3.4.1 NUMERICAL DISTRIBUTIONS 115 and after these two
3.4.1 NUMERICAL DISTRIBUTIONS 115 and after these two instructions have been executed the desired integer will appear in register A. If a random integer between 1 and Ic is desired, we add one to this result. (The instruction INCA I would follow (l).) This method gives each integer with nearly equal probability. There is a slight error because the computer word size is finite (see exercise 2); but the error is quite negligible if Ic is small, for example if k/m < l/10000. In a more general situation we might want to give different weights to different integers. Suppose that the value X = x1 is to be obtained with probability pl, and X = xz with probability pa, . . . , X = xk with probability pk. We can generate a uniform number U and let Xl, if 0 5 U < pi; x2, ifn I U < p1 +p2; x= . (2) 1: xk, ifpl +p2 + +pk-1 5 u < 1. (Note that pl + p2 + . . . + pk = 1.) There is a best possible way to do the comparisons of U against various values of PI + ~2 + . . . + P,, as implied in (2); this situation is discussed in Section 2.3.4.5. Special cases can be handled by more efficient methods; for example, to obtain one of the eleven values 2, 3, . . . , 12 with the respective dice probabilities &, 6, . . . , &, . . . , &, 9, we could compute two independent random integers between 1 and 6 and add them together. However, none of the above techniques is really the fastest general method for selecting x1, . . . , xk with the correct probabilities. An ingenious way to do the trick has been discovered by A. J. Walker [Electronics Letters 10,8 (1974), 127-128; ACM Trans. Math. Software 3 (1976) 253-2561. Suppose we form kU and consider the integer part K = LkU] and fraction part V = (kU) mod 1 separately; for example, after the code (1) we will have K in register A and V in register X. Then we can always obtain the desired distribution by doing the operations if V < PK then X +- XK+~ otherwise X t Y,, (3) for some appropriate tables (PO, . . . , P&i) and (Yo, . . . , Yk-1). Exercise 7 shows how such tables can be computed in general. Walker s method is sometimes called the method of aliases. On a binary computer it is usually helpful to assume that k is a power of 2, so that multiplication can be replaced by shifting; this can be done without loss of generality by introducing additional x s that occur with probability zero. For example, let s consider dice again; suppose we want X = j to occur with the following 16 probabilities: j = 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Pj=oo~~&&?i&~~~~~o 0 0