Why the Mapping Matters
A computer can generate a random integer, but a chance question may ask for a die face, a card rank, or another outcome that is not itself an integer in the computer’s output range. To simulate the chance question, we need a rule that translates each generated integer into an outcome. That rule matters: if some outcomes have more integer codes leading to them than others, those outcomes will occur more often in the simulation.
Assume the generator produces each integer in its stated range with equal probability. A mapping gives equally likely outcomes only when it assigns the same number of possible source integers to every outcome, or when it uses a suitable rejection rule to make those counts equal. Counting the codes is a direct way to check the mapping before using it.
Direct Mapping When the Codes Divide Evenly
Suppose the source codes are \(0,1,\ldots,M-1\), and the desired outcomes are labeled \(1,2,\ldots,m\). When \(M\) is a multiple of \(m\), one simple rule is to use the remainder after division by \(m\):
Here, \(\text{code}\bmod m\) is the remainder, one of \(0,1,\ldots,m-1\). If \(M\) is divisible by \(m\), every possible remainder occurs exactly \(M/m\) times in the source range. Therefore, each outcome receives exactly \(M/m\) codes.
Worked Example: Mapping Integers to a Fair Die
Suppose a generator selects a uniformly distributed integer from 0 through 11. Map this integer to one of the six faces of a fair die.
There are \(M=12\) equally likely codes and \(m=6\) faces. Since \(12\) is divisible by \(6\), use the remainder rule:
Codes 0 and 6 have remainder 0 and map to face 1. Codes 1 and 7 map to face 2; codes 2 and 8 map to face 3; codes 3 and 9 map to face 4; codes 4 and 10 map to face 5; and codes 5 and 11 map to face 6. Each face has two codes, so its probability is
The six outcomes are equally likely because the source codes are equally likely and each face has exactly two codes leading to it.
Grouping Codes for Outcomes With Several Representations
The remainder rule is convenient, but it is not the only balanced mapping. When there are more source codes than outcomes, codes can be arranged in consecutive groups of equal size. This is useful when the source integers already represent combinations, such as a card’s suit and rank.
Worked Example: Mapping Card Codes to Ranks
Imagine that a generator chooses one uniformly distributed integer from 0 through 51, representing one of 52 cards. Arrange the codes in 13 consecutive groups of four, one group for each rank. Map code \(k\) to rank \(\lfloor k/4\rfloor+1\), where \(\lfloor k/4\rfloor\) means the greatest integer no larger than \(k/4\).
For example, codes 0, 1, 2, and 3 map to rank 1; codes 4, 5, 6, and 7 map to rank 2; and codes 48, 49, 50, and 51 map to rank 13. In general, rank \(r\) receives codes \(4(r-1)\) through \(4r-1\), which is four codes.
The probability of any particular rank is therefore
This mapping simulates the rank of a uniformly selected card: each rank is represented by the four suits. It does not require the codes to be assigned in any particular order; the important check is that there are four codes for each rank.
When the Source Range Does Not Divide Evenly
If \(M\) is not divisible by \(m\), a direct mapping generally gives some outcomes more codes than others. One standard remedy is rejection sampling: retain a range containing a positive multiple of \(m\) codes, map those retained codes evenly, and generate another integer whenever the code falls outside that range.
The condition \(M\ge m\) is essential. It ensures that \(L\) is positive, so the retained range contains at least one full code for every outcome. If \(M<m\), a single source draw has fewer possible codes than desired outcomes, and no mapping can give every outcome a positive, equal number of codes. The source must be expanded or changed before this method can represent all outcomes equally.
Worked Example: Six Outcomes From Ten Possible Codes
Suppose a generator selects a uniformly distributed integer from 0 through 9, and the goal is to produce one of six equally likely outcomes. Here \(M=10\), \(m=6\), and \(M\ge m\), so rejection sampling is possible. The largest multiple of 6 not exceeding 10 is \(L=6\). Retain codes 0 through 5 and reject codes 6 through 9. Map each retained code \(k\) to outcome \(k+1\).
On any draw, each retained code has probability \(1/10\), and the probability that a draw is retained is \(6/10\). Conditional on being retained, each outcome has probability
If a code is rejected, the procedure uses a fresh, independent draw from the same uniform source. Thus the probability that the first accepted code is the code for outcome \(r\) is the sum of the probabilities that it appears on each possible draw:
The first term represents acceptance on the first draw; each later term includes rejection on all earlier draws. All six outcomes therefore have probability \(1/6\) when the procedure stops. A single draw is accepted with probability \(6/10=0.6\); the other \(0.4\) of the time, the procedure draws again.
Why Equal Code Counts Give Equal Probabilities
The general justification is a count of the source codes leading to an outcome. For a uniform source, each one of the \(M\) codes has probability \(1/M\). If the set of codes mapped to outcome \(r\) contains \(c_r\) codes, then the probability of that outcome is the sum of the probabilities of its codes:
Consequently, all outcomes have equal probabilities exactly when their code counts \(c_r\) are equal. For a direct mapping, the counts must add to \(M\), so equal counts require \(M=mc\) for some positive integer \(c\). This explains why divisibility is necessary without rejection.
For rejection sampling, the retained source has \(L\) codes, where \(L\) is a positive multiple of \(m\). Under the remainder mapping, each outcome receives exactly \(L/m\) retained codes. Given that a draw is retained, the probability of an outcome is therefore
Repeated independent draws until the first retained code preserve this balanced distribution: every accepted draw has the same conditional probabilities, regardless of how many rejected draws came before it. This reasoning depends on two conditions: the source codes are equally likely, and each new draw has the same distribution independently of earlier draws.
Common Mistakes and Practical Checks
A tempting shortcut is to take a remainder even when the source range is not divisible by the number of outcomes. For example, applying \(k\bmod 6+1\) to codes 0 through 9 does not produce six equally likely outcomes. Outcomes 1 through 4 each receive two codes, while outcomes 5 and 6 each receive one. Their probabilities are \(2/10=0.2\) and \(1/10=0.1\), respectively. The arithmetic is simple, but the mapping is biased.
- Do not assume a remainder rule is automatically balanced. Check whether the number of source codes is divisible by the number of outcomes.
- Do not count labels instead of codes. List how many source integers lead to each outcome; equal numbers of outcome labels do not guarantee equal probabilities.
- Do not discard leftover codes and then treat the original range as the denominator. Once codes are rejected, the relevant probabilities are conditional on acceptance, or equivalently account for repeated independent draws.
- Check that there are enough source codes. Rejection sampling requires \(M\ge m\); if \(M<m\), the retained multiple \(L\) would be zero and no outcome could be represented by a retained code.
Before using a mapping, identify the source range and count its possible values. Then count how many codes lead to each outcome. If the counts are unequal, the mapping does not give equally likely outcomes; use a balanced mapping where possible, or a valid rejection rule when the source range is large enough.
Check Your Understanding
Answer each question by counting the codes and, where appropriate, stating the probability of an outcome.
- A uniform integer is chosen from 0 through 23. Can the remainder rule map it directly to eight equally likely outcomes? How many codes map to each outcome?
- A uniform integer from 0 through 19 is mapped directly to six outcomes using a remainder rule. Explain why the outcomes cannot all be equally likely.
- For a source of 0 through 19 and six desired outcomes, find \(L\), identify the retained and rejected codes, and state the acceptance probability.
- A uniform integer is chosen from 0 through 3. Can rejection sampling from this single draw produce five equally likely outcomes? Explain using the condition on \(M\) and \(m\).
- Suppose each outcome has three source codes, but the source integers are not equally likely. Is equal code count alone enough to guarantee equal outcome probabilities? Explain.