Runs, Sequences, and Randomness

What a Run Records

When observations are recorded in order, their pattern can contain information that is lost if we look only at the total number of each outcome. For example, a sequence with many consecutive \(A\)'s and \(B\)'s has a different arrangement from one in which the symbols alternate, even if both sequences have the same symbol totals. A run is the basic unit used to describe this arrangement.

Runs are used in randomness diagnostics for ordered binary data. The first task is a careful count: group each uninterrupted block of identical symbols, and do not split a block just because it is long. A run count describes one feature of the observed order; by itself, it does not establish whether a process is random.

Definition: In an ordered sequence of symbols, a run is a maximal consecutive sequence of identical symbols. “Consecutive” means that the symbols occupy neighboring positions. “Maximal” means that the block cannot be extended to the left or right without including a different symbol or going beyond the sequence. In a binary sequence, the two possible symbols might be \(A\) and \(B\), or \(0\) and \(1\).

For example, the sequence \(A,A,B,B,B,A\) has three runs: \(AA\), \(BBB\), and \(A\). The three adjacent \(B\)'s are one run, not three. The first and last runs have only one symbol, but they still count as runs. A change from one symbol to the other starts a new run.

Throughout this tutorial, the sequence is treated as observed and fixed for the purpose of counting. No probability distribution is assumed for the examples, and no interest rate or mortality assumption is involved. The randomness question concerns whether the ordering of the symbols is consistent with an appropriate model; the formal hypotheses and reference distributions are separate questions.

Counting Runs in an Ordered Binary Sequence

Write a nonempty sequence as \(x_1,x_2,\ldots,x_n\), where each \(x_i\) is one of the two symbols. Scan the sequence from left to right. Start the count at one for the run containing \(x_1\). Each time \(x_i\) differs from \(x_{i-1}\), a new run begins. If the symbols are the same, the current run continues.

R=1+\sum_{i=2}^{n} I(x_i\ne x_{i-1}),

Here \(R\) is the number of runs, and \(I(x_i\ne x_{i-1})\) equals 1 when the neighboring symbols differ and 0 when they agree. Thus the number of runs is one plus the number of changes between consecutive symbols. This formula applies to every nonempty ordered sequence, including sequences that contain only one of the two symbols. An empty sequence has no runs; in the usual counting problems, \(n\ge 1\).

Counting check: The runs must be nonempty consecutive blocks that cover the whole sequence, with no overlap and no gaps. Their lengths therefore add to \(n\). Adjacent runs have different symbols, and identical symbols cannot be split across two runs.

The order is essential. The counts of \(A\)'s and \(B\)'s alone do not determine \(R\): the same numbers of each symbol can be arranged in many ways, producing different numbers of runs. Conversely, a run count does not tell us the exact sequence. It summarizes how often the observed sequence switches symbols, without retaining every detail of the order.

Why the Change-Count Formula Works

The formula follows by asking where each run begins. The first run begins at position 1. After that, every new run begins exactly at a position \(i\) for which \(x_i\ne x_{i-1}\). There are no other ways for a new run to start: if two consecutive symbols agree, they belong to the same maximal block. Counting the first start and all later starts gives the formula.

Count the initial run.
The first symbol belongs to one run, so begin with a count of 1.

Compare neighbors in order.
For each position after the first, compare the symbol with the one immediately before it.

Add one at every change.
A differing pair marks the start of one new maximal block; an equal pair adds no run.

This also explains why counting the number of equal adjacent pairs is not enough by itself. Equal neighbors keep a run going; different neighbors start another one. For a sequence of length \(n\), there are \(n-1\) neighboring pairs to inspect, and each pair either contributes one change or contributes none.

Worked Run Counts

Worked Example: Grouping a Sequence With Repeated Blocks

A hypothetical quality-control log labels each inspected item \(A\) or \(B\), in the order inspected. The recorded sequence is \(A,A,B,B,A,B,B,B,A,A\). Count the runs and check the symbol totals. Treat this as a fixed observed sequence: no probability distribution, interest rate, or mortality assumption is specified or needed.

Step 1: Partition into maximal blocks. Begin at the left and continue each block until the symbol changes. The blocks are \(AA\), \(BB\), \(A\), \(BBB\), and \(AA\). Each block is maximal because its neighboring symbol, where present, is different.

Step 2: Count the blocks. There are five blocks, so \(R=5\).

Step 3: Verify by counting changes. The changes occur from the first \(AA\) block to \(BB\), from \(BB\) to \(A\), from \(A\) to \(BBB\), and from \(BBB\) to the final \(AA\). There are four changes, giving \(R=1+4=5\).

Step 4: Check the symbol totals. The \(A\)'s number \(2+1+2=5\); the \(B\)'s number \(2+3=5\). The total is \(5+5=10\), which matches the sequence length. The count is consistent. Common mistake avoided: counting the three adjacent \(B\)'s as three separate runs instead of one maximal block.

Worked Example: Checking the Count After Reversing a Sequence

A hypothetical monitoring record is \(0,1,1,0,1,0,0,0,1,1,0\). Find its run count and symbol totals, then check the count for the reversed record. This is deterministic sequence counting; no probability distribution, interest rate, or mortality assumption is used.

Step 1: Find the original runs. Group consecutive equal symbols to obtain \(0\), \(11\), \(0\), \(1\), \(000\), \(11\), \(0\). There are seven runs.

Step 2: Verify by changes. The adjacent pairs change at positions \(1\) to \(2\), \(3\) to \(4\), \(4\) to \(5\), \(5\) to \(6\), \(8\) to \(9\), and \(10\) to \(11\). These are six changes, so \(R=1+6=7\).

Step 3: Check the totals. There are six zeros, at positions 1, 4, 6, 7, 8, and 11, and five ones, at positions 2, 3, 5, 9, and 10. The totals add to \(6+5=11\), the length of the sequence.

Step 4: Reverse and regroup. The reversed sequence is \(0,1,1,0,0,0,1,0,1,1,0\). Its maximal blocks are \(0\), \(11\), \(000\), \(1\), \(0\), \(11\), \(0\), giving seven runs. Reversing the order preserves the number of runs: every boundary between unlike neighboring symbols remains a boundary when viewed from the other direction. Common mistake avoided: reversing the sequence and then splitting adjacent equal symbols into separate runs.

Worked Example: Using Changes to Count Runs Efficiently

A hypothetical sensor records whether a reading is below a threshold (\(L\)) or at or above it (\(H\)). In time order, the labels are \(H,H,L,H,L,L,H,H,L,L,L,H,L,L\). Count the runs and verify both the number of changes and the symbol totals. No probability distribution, interest rate, or mortality assumption is required for this fixed sequence.

Step 1: List the maximal blocks. Reading from left to right gives \(HH\), \(L\), \(H\), \(LL\), \(HH\), \(LLL\), \(H\), \(LL\). There are eight blocks.

Step 2: Check with the neighboring-change method. There are seven boundaries between these eight blocks. Each boundary changes from \(H\) to \(L\) or from \(L\) to \(H\), so there are seven changes and \(R=1+7=8\).

Step 3: Check the number of observations. The \(H\) blocks contain \(2+1+2+1=6\) symbols. The \(L\) blocks contain \(1+2+3+2=8\) symbols. Thus the total is \(6+8=14\), matching the 14 entries in the record.

Conclusion. The sequence has eight runs, six \(H\)'s, and eight \(L\)'s. Common mistake avoided: counting only the blocks with at least two symbols; a single \(H\) or \(L\) is still a run.

Common Counting Errors and Their Consequences

Run counting is elementary, but small grouping errors change the summary and can affect subsequent interpretation. Use the definition of maximality rather than relying on how a sequence looks at a glance.

Splitting a repeated block. In \(A,B,B,B,A\), the middle \(BBB\) is one run, not three. Equal adjacent symbols remain in the same run.
Omitting a singleton. In \(A,A,B,A\), the middle \(B\) is a run even though it has length one.
Counting symbols instead of changes. The number of occurrences of either symbol is not the number of runs. First identify blocks or count changes between neighbors.
Discarding the order. Sorting the observations, or retaining only the two symbol totals, destroys the original arrangement needed to count runs.
Using the wrong sequence. The order must be defined by the data collection process, such as time or inspection order. Rearranging observations changes the run count in general.

A very useful final check is to count in two ways: list the maximal blocks, then count adjacent changes and add one. If the answers disagree, at least one boundary has been missed or an equal-symbol block has been split. Also check that the run lengths sum to the sequence length and that the two symbol totals do the same.

Key takeaway: For a nonempty binary sequence, a run is one maximal consecutive block of identical symbols. The run count is one plus the number of changes between neighboring positions. This count describes ordering, not just the number of occurrences of each symbol, and is a summary rather than a complete conclusion about randomness.

Check Your Understanding

For each sequence, identify maximal blocks or count changes, then check that the symbol totals add to the sequence length.

A hypothetical inspection sequence is \(H,H,L,H,L,L,H\). How many runs are there, and how many of each symbol? (Answer: 5 runs; 4 \(H\)'s and 3 \(L\)'s, totaling 7.)
Count the runs and symbol totals in \(0,0,0,1,1,0,1,1,1,1\). (Answer: 4 runs; 4 zeros and 6 ones, totaling 10.)
For \(A,B,A,A,B,B,A,B\), find the number of runs, the number of adjacent changes, and the symbol totals. (Answer: 6 runs; 5 changes; 4 \(A\)'s and 4 \(B\)'s, totaling 8.)
A sequence is \(A,B,B,A,A,B\). Count its runs, then reverse it and count again. (Answer: 4 runs in each; the reverse is \(B,A,A,B,B,A\), with blocks \(B\), \(AA\), \(BB\), \(A\).)
Count the runs and check the totals for \(1,0,1,0,0,1,0,1,1,0,0,0,1\). (Answer: 9 runs; 6 ones and 7 zeros, totaling 13.)

What You'll Learn