Randomization and Simulation
Randomization
A computer really isn't a random device, of course; if it
were, programming would be as difficult as controlling human behavior.
Fortunately, since the advent of the computer, mathematicians have
developed algorithms capable of simulating randomness.
Pseudo-randomization is a standard implementation in all computer
languages.
The built-in function RND returns a single precision
number, "randomly" chosen between 0 and 1 (in the language of
probability, the number is uniformly distributed on the interval 0 - 1).
The range specification is not as restrictive as a first glance would
suggest, since the number may be transformed so that it fits within any
specified interval. Simply add the
lower bound of the interval to the product of the range and the returned RND
number. For example, a random
number, A, between 1 and 100 may be obtained via A = 1
+ (100 - 1) * RND. If instead a random integer,
I, between 5 and 10 is desired, the equation would be I
= 5 + INT ((10 - 5 + 1) * RND). The
+1 added to the range multiplier is needed because the INT function truncates.
Random integers can be useful in subtle ways.
For example, to randomly select a capital letter from the alphabet,
choose a random integer between 65 and 90; i.e., RANDOMLETTER
= ASC(65 + INT((90 - 65 + 1) * RND)). To randomly select one object from among a group, assign an
integer to each group member and use 1 and the number of members to define the
range.
The pseudo-randomizer cooks up its random numbers using a
seed value. When RND is invoked, a
default seed is employed to start the process of generating random numbers, so
the same sequence of numbers will be reported every time the program is run
unless the program calls for reseeding. This
may be useful during program development, especially if the programmer is
crafting a transformation. In fact,
by using an argument of zero with the RND function, - that is, with a statement
such as A = RND(0) - the same random number will
be returned every time. Of course,
when the program is run normally, varied random numbers are needed. These are obtained by preceding the RND call with the
built-in reseeding function RANDOMIZE TIMER
before the first call to RND. TIMER
is another built-in function; it returns the number of seconds elapsed since
midnight. This unfathomable number serves as a variable seed.
Simulation
In a typical simulation, the program cycles through many
trials and meanwhile keeps track of various interesting outcomes.
Simulation can be used to let the user explore a complex setting in which
analytic expressions for the probabilities of particular outcomes are hard to
derive. The frequency statistics
kept by the program furnish estimates of these probabilities.
For example, an expert could calculate the exact probability of drawing a
poker hand with two kings; but even
one who slept through statistics class (for shame!) could get a very good
approximation to the theoretically derived value by examining the frequency in
1000 trials. Simulation is
especially useful when no one knows how to find a theoretical solution.
We can use the computer to simulate a typical random
process such as is called for when playing Monopoly.
A short program utilizes the world's most expensive pair of dice.
The simulation is designed to find the
frequency of doubles within a run of 20 tosses. You may want to run
the program several times to check the randomness (or you may get into game mode
- it's OK, take a break). .
PRIVATE NDOUBLES AS INTEGER
PRIVATE NTRIALS AS INTEGER
PRIVATE NROLL AS INTEGER
PRIVATE NDIE1 AS INTEGER
PRIVATE NDIE2 AS INTEGER
NDOUBLES = 0
NTRIALS = 20
RANDOMIZE TIMER
FOR
nroll = 1 TO NTRIALS
ndie1
= 1 + INT((6 - 1 + 1) * RND)
ndie2
= 1 + INT((6 - 1 + 1) * RND)
IF
ndie1 = ndie2 Then
NDOUBLES = NDOUBLES + 1
END
IF
NEXT
nroll
LABEL1.CAPTION = "There were
" & STR$(NDOUBLES)& " doubles in " STR$(NTRIALS)+& "
trials"
Random Permutation (with an example of card shuffling)
I love to play the card game bridge, but I find shuffling
and dealing tedious. Distributing a
deck of cards illustrates an important variation on the randomization theme, the
random permutation. Permutation
entails allocating a number of objects into a number of bins.
The distinction between ordinary randomization and random permutation is
well illustrated by an error a medical colleague made while conducting a
research project. As patients presented themselves for treatment, they were to
be randomly assigned to one of two groups (who received slightly different
instructions but got the same medical care).
My friend handled the random assignment by tossing a coin as each patient
appeared. Unfortunately, the coin
proved fallible, because after sixty patients had been inducted, there were 40
in group one and 20 in group two. When
I was consulted, I suggested the bad luck was somewhat extreme, but a lesser
disparity was almost certain to occur. A fair coin necessarily gives 50-50 proportions only in the
"long run". A more
effective random assignment scheme would call for shuffling the numbers 1
through N, where N is the number of patients to be run. The parity (odd vs.
even) of the first number drawn would determine group placement for the first
patient, that of the second number drawn would determine placement for the
second, and so on. If the number of
available patients was uncertain, the assignment could be done for smaller
blocks of patients. For example,
the first ten patients could be assigned according to a random permutation, then
the next ten, etc. Random
permutation can be accomplished by shuffling numbers in a hat, but since no one
wears hats anymore we ought to do it with VB.
For those of you who have managed to spend your time more
constructively than by playing cards, let me sketch the requirements of the card
dealer program. The deck consists
of fifty-two cards, arranged in four suits (clubs, hearts, diamonds, spades).
Each suit has thirteen cards; ace is the highest, then king, queen, jack,
ten, nine, and so on down to the lowly deuce, or two.
The program should place in a random way thirteen cards into the hand of
each of the four players, who are conventionally designated as North, East,
South, and West. The display will
show the cards, arranged by rank within suits, for each player.
Shuffling, or more formally, permuting, is accomplished by
interchanging the positions within the deck of randomly chosen pairs of cards.
If we interchange many times (I arbitrarily chose 1000 - the choice
affects the speed of the program), the order of the cards will be completely
revamped. The SHUFFLER SUBROUTINE can be used for any permutation task.
In the bridge version, the deck begins with the cards in
the order 1-52, but after the shuffling, the order is unknown.
The top thirteen cards go to the first player, North; the next thirteen
go to West, etc. Next the cards within each hand are separated into suits,
then ranked within each suit. Since
the requirements of bridge may be obscure, I have commented this program more
extensively than is my usual practice. I leave it to you to determine how
to display the results.
OPTION BASE 1
DIM DECK(52) AS INTEGER
DIM HAND(4, 13) AS INTEGER
DIM PLAYER(4) AS STRING
DIM SUIT(4) AS STRING
DIM NSUIT(4, 4) AS INTEGER
DIM HOLDING(4, 4, 13) AS INTEGER
PLAYER(1) = "North"
PLAYER(2) = "West"
PLAYER(3) = "East"
PLAYER(4) = "South"
SUIT(1) = CHR$(6)
SUIT(2) = CHR$(3)
SUIT(3) = CHR$(4)
SUIT(4) = CHR$(5)
RANDOMIZE TIMER
CALL SHUFFLER(DECK(), 52)
REM
ALLOCATE CARDS INTO THE FOUR HANDS
FOR L = 1 TO 4
FOR J = 1 TO 13
HAND(L, J) = DECK(J + (L - 1) * 13)
NEXT J
NEXT L
REM
THE DISTRIBUTION IS FINISHED, NOW SORT THE HANDS
REM
NSUIT IS THE NUMBER OF CARDS IN EACH SUIT
FOR L = 1 TO 4
FOR J = 1 TO 13
SELECT CASE HAND(L, J)
CASE 1 TO 13
REM SPADE
I = 1
CASE 13 TO 26
REM HEART
I = 2
CASE 27 TO 39
REM DIAMOND
I = 3
CASE 40 TO 52
REM CLUB
I = 4
END SELECT
NSUIT(L, I) = NSUIT(L, I) + 1
HOLDING(L, I, NSUIT(L, I)) = HAND(L, J)
NEXT J
NEXT L
REM PUT CARDS IN EACH HAND IN ORDER
WITHIN SUITS
FOR L = 1 TO 4
FOR
I = 1 TO 4
UNORDERED = TRUE
DO WHILE UNORDERED = TRUE
UNORDERED = FALSE
FOR J = 1 TO NSUIT(L, I) - 1
IF HOLDING(L, I, J) > HOLDING(L, I, J
+ 1) THEN
SWAP HOLDING(L, I, J), HOLDING(L, I, J +
1)
UNORDERED = TRUE
END IF
NEXT J
LOOP
NEXT
I
NEXT L
FUNCTION CARD (NRANK) AS STRING
REM NAME THE CARDS FOR BRIDGE
NAMECARD = NRANK MOD 13
IF NAMECARD = 0 THEN NAMECARD = 13
SELECT CASE NAMECARD
CASE
1
CARD = " A"
CASE
2
CARD = " K"
CASE
3
CARD = " Q"
CASE
4
CARD = " J"
CASE
5 TO 13
CARD = STR$(15 - NAMECARD)
END SELECT
END FUNCTION
SUB SHUFFLER (OBJECTS(), N)
FOR J = 1 TO N
OBJECTS(J) = J
NEXT J
FOR I = 1 TO 1000
NFIRST = INT(N * RND + 1)
NSECOND = INT(N * RND + 1)
SWAP OBJECTS(NFIRST), OBJECTS(NSECOND)
NEXT I
END SUB
SUBROUTINE SWAP (A, B)
DIM TEMP AS INTEGER
TEMP = A
A = B
B = TEMP
END SUB
|