CMP.11:5 - Archetypal Grounding

CMP.11:5.1 - Determine whether any bit is one

An unknown n-bit input is accessed one bit at a time. Return whether it contains a one. For a deterministic always-correct algorithm, answer zero to every query. Before all n distinct positions have been read, both the all-zero input and an input with a one at an unread position remain possible. Their correct answers differ. Therefore some input requires n queries. A complete scan attains that bound.

Allow a randomized algorithm that uses at most q queries on every run and errs with probability at most δ<1/2 on every input. Couple its runs on the all-zero input and on the input with just position j set to one, using the same random choices. Unless the zero-input run queries j, both runs have the same transcript and output. Let p_j be the probability it queries j on the zero input. Consequently,

P(output 1 on singleton j) ≤ P(output 1 on zeros)+p_j ≤ δ+p_j.

Correctness on the singleton requires the left side to be at least 1-δ, so p_j≥1-2δ. Summing over j gives

q ≥ sum_j p_j ≥ n*(1-2δ).

For δ=1/3, this gives q≥n/3. It is a lower bound under the stated maximum-query convention, not a claim that every randomized algorithm uses exactly that many queries.

Now change the promise: either all bits are zero or at least half are one. Query k independently chosen uniform positions, returning one if any query finds it. On a nonzero promised input, the probability of missing every one is at most 2^-k; zero inputs always receive the correct answer. For 0<δ<1/2, choosing k=ceil(log2(1/δ)) therefore achieves the error requirement independently of n, subject to generating and accessing those positions. For n>2, the singleton inputs used in the earlier bound are excluded. This explains why the new algorithm escapes that growth in cost.

CMP.11:5.2 - Bound comparison sorting and identify its escape

Sort n distinct opaque keys, with their order available only through pairwise comparisons. A comparison has two possible outcomes. The n! possible input orders require different output permutations, so a correct decision tree needs at least n! leaves. A binary tree of height q has at most 2^q leaves. Thus the worst case needs at least ceil(log2(n!)) comparisons, which grows as Ω(n log n).

This bound is about comparison sorting. If each key is an integer in 0..K-1 and direct array indexing is an allowed elementary operation, count occurrences in K counters and emit keys in index order. That construction uses O(n+K) counter/access operations and corresponding output work. It escapes the comparison bound by observing the encoding through indexing. Large K, long integers or a requirement to preserve distinct record identity can change its storage and reconstruction costs.

A practical consequence is to compare representations and access before spending effort trying to make an ordinary comparison procedure sort arbitrary distinct keys in fewer than order n log n comparisons. If comparisons themselves are expensive, a matching comparison count still leaves their internal cost to reduce.

CMP.11:5.3 - Expose information hidden in a message

One agent has an n-bit string x and sends one fixed-length binary message to another agent holding y. The receiver must decide whether x=y with no error. If two different strings x and x’ produce the same message, take the common receiver input y=x. The receiver sees identical information in both cases but must answer differently. All 2^n strings therefore need distinct messages, requiring at least n bits. Sending x achieves it.

If public independent random masks and an error probability are admitted, the task changes. For each mask r, send the parity of the positions where both x and r are one; the receiver compares with its parity from y. Equal strings always match. For unequal strings, choose one differing position: toggling its independent mask bit pairs masks with opposite comparison outcomes, so the parities match with probability 1/2. After k independent masks, falsely accepting equality has probability 2^-k and the message has k bits. The shared random masks and local parity-computation cost are explicit resources, not information transmitted by the message.