Password and Code Probabilities

Why Codes Need Careful Counting

A short code can have many possible values, and a small change in its rules can change the count substantially. A four-digit code may allow a zero in the first position, for example, even though a four-digit number usually does not. A password may allow a character to appear more than once, while a rule for a one-time code may forbid repeats. Before counting or calculating a probability, specify which sequences are valid.

A code is an ordered sequence: changing the order of its characters generally gives a different code. Thus 208 and 802 are different three-digit codes. This differs from an unordered selection, such as a hand of cards, where changing the order in which the same objects are listed does not create a new outcome.

Definition: A code space is the set of all sequences allowed by the stated code rules. When one code is selected uniformly from that space, every valid code has the same probability. For an event $A$ consisting of some valid codes, $$ P(A)=\frac{\text{number of valid codes in }A}{\text{total number of valid codes}}. $$

The word valid matters in both parts of this ratio. If codes must start with a nonzero digit, codes starting with zero are not included in the total. If repeated characters are forbidden, sequences with repeats are not included either. The favorable count must follow the same rules as the total count.

Counting Codes by Their Positions

A reliable way to count a code is to consider its positions in order. The product rule applies when every partial sequence at a given stage has the same number of permitted choices for the next position. When those counts are constant from stage to stage, multiply them. If a restriction makes the number of continuations depend on earlier choices, separate the possibilities into branches, count each branch, and add the branch counts.

Counting principle: If each partial sequence at a stage has the same number of permitted continuations, multiply the number of choices across stages. If continuation counts differ across partial sequences, do not multiply by one common continuation count; count the branches separately and add their totals.

With repetition allowed and no other restrictions, every position has the same full character set available. With repetition forbidden, later positions have fewer choices, but the number available is still the same for every partial sequence of a given length: after $k$ distinct characters have been used, each such sequence leaves the same number of characters. Restrictions that single out particular characters can break this symmetry. For example, requiring the last digit to be even may leave different numbers of choices for the first digit depending on what the last digit is. In that situation, count by the relevant cases rather than assuming a single product works.

Worked Example: A Four-Digit Code With Repetition Allowed

A hypothetical system selects uniformly from all four-digit strings made from 0 through 9. A zero may appear first, and digits may repeat. What is the probability that the code contains at least one repeated digit?

Total codes. Each of the four positions has 10 choices, independently of the characters already placed. Therefore, $$ 10\cdot 10\cdot 10\cdot 10=10^4=10{,}000 $$ codes are possible.

Count the complement. It is simpler to first count codes with no repeated digit. The first position has 10 choices, the second has 9, the third has 8, and the fourth has 7. These counts are the same for every partial sequence of the relevant length, so the product rule gives $$ 10\cdot 9\cdot 8\cdot 7=5{,}040. $$

The codes with at least one repeated digit are the remaining $10{,}000-5{,}040=4{,}960$ codes. Since each code is equally likely, $$ P(\text{at least one repeated digit})=\frac{4{,}960}{10{,}000}=0.496. $$ Thus the probability is 0.496, or 49.6%. This event includes codes with a pair, with multiple pairs, or with a digit appearing three or four times.

Restrictions and Branch-by-Branch Counting

A restriction may make a code position depend on the characters used elsewhere. This is a signal to inspect the cases, not to multiply choice counts automatically. The following example has a small code space, but illustrates why the cases must be counted carefully.

Worked Example: No Repeats and an Even Final Digit

A hypothetical system selects uniformly from three-digit codes made from 0 through 9, with no repeated digits and a nonzero first digit. What is the probability that the final digit is even?

Total valid codes. There are 9 choices for the first digit (1 through 9), then 9 choices for the second (any digit except the first, including zero), and 8 choices for the third. The choice count at each stage is the same across partial codes of that length, so the total is $$ 9\cdot 9\cdot 8=648. $$

Favorable codes, counted by the last digit. If the last digit is 0, the first digit can be any of 1 through 9, giving 9 choices. The middle digit can then be any of the 8 remaining digits. This case contributes $9\cdot 8=72$ codes.

If the last digit is 2, 4, 6, or 8, there are 4 choices for it. For each such choice, the first digit can be any nonzero digit other than the last digit, giving 8 choices. The middle digit then has 8 choices, since any digit except the first and last is allowed. This case contributes $4\cdot 8\cdot 8=256$ codes. The favorable total is therefore $72+256=328$, and $$ P(\text{final digit is even})=\frac{328}{648}=\frac{41}{81}\approx 0.5062. $$

The split is necessary because a final zero leaves 9 choices for the first digit, while a nonzero even final digit leaves only 8. Using one first-position count for all even endings would miscount the codes.

This example also shows why a valid denominator depends on the code's rules. There are $648$ codes in the selection space, not $1{,}000$: codes beginning with zero or containing repeated digits are not eligible for selection. The probability uses the favorable count divided by this valid total.

Counting an Exact Repetition Pattern

Sometimes the question is not whether there is any repeated digit, but whether a particular pattern occurs. A useful strategy is to decide which digit repeats, choose the other digits, and arrange the resulting characters in the positions. When counting arrangements, account for identical repeated copies: swapping two copies of the same digit does not create a different code.

Worked Example: Exactly One Pair in a Four-Digit Code

A hypothetical four-digit code is selected uniformly from all strings of digits 0 through 9, with repetition allowed. Find the probability that exactly one digit appears twice and the other two digits each appear once.

There are $10^4=10{,}000$ total codes. To count favorable codes, first choose the digit that appears twice: 10 choices. Next choose the two other distinct digits from the remaining 9 digits: $$ \binom{9}{2}=36. $$

For each selection of digits, the four characters have one pair of identical copies and two distinct single digits. The number of distinct orders is $$ \frac{4!}{2!}=12, $$ because swapping the two identical copies does not change the code. Thus the favorable count is $10\cdot 36\cdot 12=4{,}320$, and the probability is $$ P(\text{exactly one pair})=\frac{4{,}320}{10{,}000}=0.432. $$

This pattern excludes a triple, two pairs, and four identical digits. Those arrangements do not have exactly one digit appearing twice with two other digits each appearing once.

Why the Count Ratio Gives the Probability

The ratio of counts follows directly from uniform selection. Suppose a valid code is chosen from a finite set of $N$ codes, each with probability $1/N$, and an event $A$ contains $m$ of those codes. The event occurs if the selected code is any one of those $m$ outcomes. Since these outcomes are disjoint and each has probability $1/N$, their probabilities add:

P(A)=\underbrace{\frac{1}{N}+\frac{1}{N}+\cdots+\frac{1}{N}}_{m\text{ outcomes}}=\frac{m}{N}.

The justification depends on equal likelihood. If a generator favors some codes over others, counting favorable and total codes alone does not determine the probability; the individual selection probabilities would also be needed. Likewise, if the question says codes are sampled only from a restricted set, that restricted set is the sample space for the calculation.

Common Mistakes and a Reliable Method

Treating a code like a number. A code may begin with zero. Exclude leading zeroes only if the stated rules exclude them.
Ignoring order. In a code, 208 and 802 are different outcomes. Use ordered sequences, not an unordered selection count, unless the problem explicitly says order does not matter.
Multiplying incompatible choice counts. A product such as “number of first choices times number of later choices” is valid only when the continuation count is the same for every relevant first choice. Otherwise split into cases and add.
Counting the complement incorrectly. “At least one repeated digit” includes every pattern with a repeat. Counting codes with no repeats and subtracting from the total avoids trying to separate all the repeat patterns.
Using the wrong denominator. The denominator is the number of codes eligible to be selected under the given rules, not necessarily all strings of that length.
Assuming a count ratio is a probability without uniform selection. The ratio applies when each valid code is equally likely. A nonuniform generator requires its selection probabilities.

Define the valid codes.
Specify the character set, code length, whether repetition is allowed, and any position restrictions.

Count the total space.
Use a product only when the relevant choice counts are uniform across partial sequences; otherwise count separate branches and add.

Count the event.
Choose direct counting or a complement, and ensure the favorable count follows the same validity rules as the total.

Calculate and interpret.
For uniform selection, divide the favorable count by the total valid count and state the event in the code's context.

Key takeaway: Code probabilities begin with a precise sample space. Count ordered valid sequences, check whether continuation counts are uniform before multiplying, use branch sums when they vary, and take a favorable-to-total ratio only for uniformly selected codes.

Check Your Understanding

For each question, state the counting logic as well as the result where a calculation is requested.

How many three-digit strings can be formed from 0 through 9 if repetition is allowed and a zero may appear first?
A four-character code uses digits 0 through 9 without repetition. How many valid codes begin with a nonzero digit?
Why is it not generally correct to multiply the number of first choices by one continuation count when different first choices permit different numbers of continuations?
In a uniformly selected five-digit string from 0 through 9, why can the probability of at least one repeated digit be counted using the complement?
A code is selected from a set of valid codes, but some valid codes are more likely than others. Is the favorable count divided by the total count necessarily its probability? Explain.