Randomized Algorithms

Every procedure up to this point has been deterministic: the same input always gave the same steps and the same answer. The final design approach loosens this guarantee. A random choice is placed inside the procedure, and something is hoped for in exchange — either not getting stuck in bad regions of the search space, or reaching an answer without doing an exhaustive count.

Which guarantee is loosened is decisive, and there are two options. In the first, the answer stays certain and only the step count becomes random; the procedure always gives the correct answer, but how many steps it takes is unknown. In the second, the step count stays bounded and the answer becomes probabilistic; the procedure is fast but sometimes wrong. This lesson counts both with the same measure and models randomness according to this course’s rule: with a deterministic generator.

• DA47. Randomness is modeled with a deterministic generator; the standard library’s random number generator is not used. Every run is reproducible with its seed.
• DA48. Two seeds are used: 20260218 and 20260219. A random procedure’s result is not reported with a single seed.
• DA49. The first measured problem: the majority element in a 15-value array — the value occupying more than half the length. If there is none, the correct answer is “none.”
• DA50. The oracle counts every value one by one; it does no sampling at all.
• DA51. The corpus is two batches: 40 arrays with a majority and 40 without.
• DA52. A step is drawing a sample or comparing a value.
• DA53. The approach’s precondition: the majority element exists. The second batch breaks this precondition.
• DA54. The second measured problem: finding the first solution in a queens placement; column order is randomized.
• DA55. The random step count is reported as minimum, average, and maximum; twenty runs are taken, and a single number is not considered sufficient.
• DA56. Expected performance is the average of the steps, not time.

How Randomness Is Modeled

In this course, randomness is not a library call but a seeded generator. The reason is measurement: a random procedure’s diverging-input count can only be reported if the run is reproducible.

# Randomness is modeled with a deterministic generator; the standard library's generator is not used.
LENGTH = 15


class Counter:
    def __init__(self):
        self.steps = 0

    def add(self, n=1):
        self.steps += n


def generator(seed):
    d = seed

    def next_value(n):
        nonlocal d
        d = (d * 1103515245 + 12345) % 2147483648
        return d % n
    return next_value


def majority_corpus(seed, count=40, has_majority=True):
    """has_majority=True -> one value takes up more than half the length."""
    r = generator(seed)
    items = []
    for i in range(count):
        dominant = r(6)
        share = 8 + r(3) if has_majority else 5 + r(3)      # 8..10 or 5..7
        array = [dominant] * share + [6 + r(6) for _ in range(LENGTH - share)]
        for j in range(len(array) - 1, 0, -1):          # deterministic shuffle
            k = r(j + 1)
            array[j], array[k] = array[k], array[j]
        items.append({"no": i + 1, "array": array})
    return items


def oracle_majority(array, s):
    """Counts every value one by one. This is the oracle."""
    for i in range(len(array)):
        count = 0
        for j in range(len(array)):
            s.add()
            if array[j] == array[i]:
                count += 1
        if count * 2 > len(array):
            return array[i]
    return None


WITH_MAJORITY = majority_corpus(20260218)
WITHOUT_MAJORITY = majority_corpus(20260218, has_majority=False)
s1, s2 = Counter(), Counter()
v = sum(1 for item in WITH_MAJORITY if oracle_majority(item["array"], s1) is not None)
y = sum(1 for item in WITHOUT_MAJORITY if oracle_majority(item["array"], s2) is not None)
print("corpus with majority: 40 arrays x", LENGTH, "values | have a majority:", v)
print("corpus without majority:", 40, "arrays | have a majority:", y)
print("oracle steps:", s1.steps, "(with majority) |", s2.steps, "(without majority)")

corpus with majority: 40 arrays x 15 values | have a majority: 40
corpus without majority: 40 arrays | have a majority: 0
oracle steps: 780 (with majority) | 9000 (without majority)

Both batches are built as intended: one has a majority in 40 of 40 arrays, the other in none. The difference in the oracle’s step count is also meaningful — 780 versus 9000. When a majority exists, the oracle usually finds it at the first value it tries and stops; when there is none, it has to count all 15 values through to the end, that is, exactly 225 steps per array. A procedure’s most expensive case is the one where the answer is “none.”

The Probabilistic Answer and the Role of Verification

A random procedure for the majority element is built in one sentence: pick a random position, take the value there as a candidate. If a majority exists, the candidate is correct with probability more than half. The two variants below share this idea and diverge at a single point — one verifies the candidate, the other does not.

# Continuing from the previous block: Counter, generator, majority_corpus, oracle_majority, WITH_MAJORITY come from there.
def sampled_majority(array, trials, r, s, verify=True):
    """Picks 'trials' random positions. If verify=True, tests the candidate by counting."""
    if verify:
        for _ in range(trials):
            candidate = array[r(len(array))]
            s.add()
            count = 0
            for x in array:
                s.add()
                if x == candidate:
                    count += 1
            if count * 2 > len(array):
                return candidate
        return None
    sample = []                                   # no verification: the sample's mode
    for _ in range(trials):
        s.add()
        sample.append(array[r(len(array))])
    best, best_count = None, -1
    for a in sample:
        c = sample.count(a)
        if c > best_count:
            best, best_count = a, c
    return best


def measure(items, trials, seed, verify):
    r = generator(seed)
    diverging, ac, oc = 0, Counter(), Counter()
    for item in items:
        a = sampled_majority(item["array"], trials, r, ac, verify)
        if a != oracle_majority(item["array"], oc):
            diverging += 1
    return {"diverging": diverging, "approach_steps": ac.steps, "oracle_steps": oc.steps}


print("trials  seed       verified diverging/steps   unverified diverging/steps")
for trials in (1, 3, 5):
    for seed in (20260218, 20260219):
        a = measure(WITH_MAJORITY, trials, seed, True)
        b = measure(WITH_MAJORITY, trials, seed, False)
        print(f"{trials:6d}  {seed}  {a['diverging']:12d} / {a['approach_steps']:5d}"
              f" {b['diverging']:16d} / {b['approach_steps']:4d}")

trials  seed       verified diverging/steps   unverified diverging/steps
     1  20260218            10 /   640               10 /   40
     1  20260219            17 /   640               17 /   40
     3  20260218             0 /   944                6 /  120
     3  20260219             1 /   928               13 /  120
     5  20260218             0 /   944                6 /  200
     5  20260219             0 /  1056                7 /  200

Three numbers side by side. The oracle spends 780 steps. Verified sampling spends 944 to 1056 steps at five trials and diverges on 0 inputs in both seeds. Unverified sampling spends 200 steps — almost four times fewer than the oracle — and diverges on 6 and 7 inputs across the two seeds.

The effect of trial count differs across the two columns. In the verified column, the diverging count drops from 10 and 17 to 0 and 1 at three trials, and to 0 and 0 at five trials: every new trial cuts the probability of all previous trials failing by more than half. In the unverified column, the diverging count drops from 10 and 17 to 6 and 7 and stays there; it improves as the sample grows but never reaches zero.

The real difference is not the size of the numbers but the direction of the error. The verified version cannot return a wrong value; because it never accepts a candidate without counting it, it either gives the correct value or says “none.” The 10 divergences seen at one trial do not mean it gave a wrong value on ten inputs — they mean it failed to find one on ten inputs. The unverified version really does return a wrong value. The verification step turns a two-sided error into a one-sided one, and that is what 944 steps buy over 200.

When the Precondition Breaks

The importance of this distinction becomes visible when the majority element does not exist.

# Continuing from the previous blocks: measure, WITH_MAJORITY and WITHOUT_MAJORITY come from there.
print("precondition  seed       verified diverging  unverified diverging")
for label, items in (("holds   ", WITH_MAJORITY), ("broken  ", WITHOUT_MAJORITY)):
    for seed in (20260218, 20260219):
        a = measure(items, 5, seed, True)
        b = measure(items, 5, seed, False)
        print(f"{label}  {seed}  {a['diverging']:16d}  {b['diverging']:20d}")

precondition  seed       verified diverging  unverified diverging
holds     20260218                 0                     6
holds     20260219                 0                     7
broken    20260218                 0                    40
broken    20260219                 0                    40

On the 40 arrays without a majority, unverified sampling diverges from the oracle on all 40 of the 40 inputs; verified sampling diverges on none. The result is the same across both seeds, so it does not depend on the corpus.

The reason is clear and fits the course’s general shape. The unverified procedure has buried the “a majority exists” assumption inside its code: it returns the sample’s most frequent value and never asks whether that value is actually a majority. When the precondition breaks, it does not slow down — it still finishes in 200 steps — but every time, it reports an answer that does not exist. Verification takes the precondition out of the code and turns it into a condition tested at run time; its cost is one exhaustive count per array, its gain is not staying silent when the precondition breaks.

Certain Answer, Random Steps

The second use of randomness never touches the answer. The previous lesson’s pruned queens search always tried columns left to right; once the order is randomized, the solution found is still valid, and the only thing that changes is how many nodes it takes to reach it.

# Continuing from the previous block: Counter and generator come from there.
def queens_first_solution(n, r=None):
    """Stops at the first solution. If column order is random, steps change, the answer does not."""
    s = Counter()
    found = None

    def visit(row, placement):
        nonlocal found
        s.add()
        if row == n:
            found = tuple(placement)
            return
        columns = list(range(n))
        if r:
            for j in range(n - 1, 0, -1):
                k = r(j + 1)
                columns[j], columns[k] = columns[k], columns[j]
        for column in columns:
            if any(column == y or abs(column - y) == row - i
                   for i, y in enumerate(placement)):
                continue
            placement.append(column)
            visit(row + 1, placement)
            placement.pop()
            if found is not None:
                return
    visit(0, [])
    return {"nodes": s.steps, "valid": found is not None}


print(" n  deterministic  seed       min  average  max  valid solution")
for n in (8, 12, 16):
    deterministic = queens_first_solution(n)
    for seed in (20260218, 20260219):
        r = generator(seed)
        runs = [queens_first_solution(n, r) for _ in range(20)]
        nodes = [run["nodes"] for run in runs]
        print(f"{n:2d} {deterministic['nodes']:13d}  {seed}  {min(nodes):6d} {sum(nodes) / 20:9.1f}"
              f" {max(nodes):7d}  {sum(run['valid'] for run in runs):9d} / 20")

 n  deterministic  seed       min  average  max  valid solution
 8           114  20260218       9      35.7      89         20 / 20
 8           114  20260219      16      35.0     101         20 / 20
12           262  20260218      15      98.7     491         20 / 20
12           262  20260219      17      90.1     356         20 / 20
16         10053  20260218      19     359.6    3379         20 / 20
16         10053  20260219      19     355.8    1237         20 / 20

The last column is 20 / 20 in every row: all forty runs find a valid placement. The answer is not random; only the steps are. On the sixteen-queens board, the deterministic order visits 10,053 nodes, the random order an average of 359.6 and 355.8 nodes — roughly 28 times fewer. The averages for the two seeds are very close to each other, meaning expected performance does not depend on the corpus.

The extreme values complete this table and show why a single average is not enough. The minimum is 19 nodes, the maximum 3379; the gap between them is 178 times, and the two seeds’ maximums are also far apart, 3379 versus 1237. A random procedure’s performance cannot be reported with a single number; the average is not a guarantee, it is an expectation. The deterministic order’s 10,053 nodes is not an accident: a fixed order walks the same solution-free region to the same depth on every run, and a bad order’s cost never shrinks on any run. What randomization buys is never trying the same bad order twice.

Cutting the Long Tail

The 3379-node outlier is the random procedure’s real problem: most runs are short, a few are very long. This tail can be cut with a budget — if search exceeds a set node count, it is abandoned and restarted from scratch with a new random order.

# Continuing from the previous block: Counter, generator and queens_first_solution come from there.
def budgeted_search(n, r, budget):
    """Gives up if the budget is exceeded. Giving up is not a wrong answer - there is no answer."""
    s = Counter()
    found = None

    def visit(row, placement):
        nonlocal found
        s.add()
        if s.steps > budget or found is not None:
            return
        if row == n:
            found = tuple(placement)
            return
        columns = list(range(n))
        for j in range(n - 1, 0, -1):
            k = r(j + 1)
            columns[j], columns[k] = columns[k], columns[j]
        for column in columns:
            if any(column == y or abs(column - y) == row - i
                   for i, y in enumerate(placement)):
                continue
            placement.append(column)
            visit(row + 1, placement)
            placement.pop()
            if found is not None or s.steps > budget:
                return
    visit(0, [])
    return s.steps, found


print("budget  seed       restarts  total nodes  max     valid")
for budget in (100, 400, 100000):
    for seed in (20260218, 20260219):
        r = generator(seed)
        total, attempts, worst, valid = 0, 0, 0, 0
        for _ in range(20):
            run_nodes = 0
            while True:
                steps, result = budgeted_search(16, r, budget)
                run_nodes += steps
                attempts += 1
                if result is not None:
                    valid += 1
                    break
            total += run_nodes
            worst = max(worst, run_nodes)
        print(f"{budget:6d}  {seed}  {attempts:16d} {total / 20:13.1f} {worst:7d}"
              f" {valid:8d} / 20")

budget  seed       restarts  total nodes  max     valid
   100  20260218                54         225.8     940       20 / 20
   100  20260219                57         240.8    1229       20 / 20
   400  20260218                27         228.8    1731       20 / 20
   400  20260219                29         276.1     835       20 / 20
100000  20260218                20         359.6    3379       20 / 20
100000  20260219                20         355.8    1237       20 / 20

With a budget of a hundred nodes, 54 and 57 attempts are made for twenty solutions, meaning between 2.70 and 2.85 restarts per solution. In exchange, the total node average drops from 359.6 to 225.8, and the worst run from 3379 to 940. The last rows repeat the unbudgeted run and confirm the difference.

The answer still does not break: the last column is 20 / 20 in all six rows. Giving up is not the same as giving a wrong answer — when the budget is exceeded, the procedure says nothing, and because it says nothing, it does not diverge from the oracle. The distinction from the course’s first lesson takes its final form here: a procedure that reports what it does not know can be measured; a procedure that fabricates what it does not know cannot.

Summary

• Randomization can loosen two separate guarantees: the answer can stay certain while the step count becomes random, or the step count can stay bounded while the answer becomes probabilistic. The two are measured separately.
• On the majority element, the oracle spends 780 steps; verified sampling spends 944 to 1056 steps at five trials with 0 diverging inputs, unverified sampling 200 steps with 6 to 7 diverging inputs.
• The verification step makes error one-sided: the verified version cannot return a wrong value, it can only say “none”; the unverified version really does return a wrong value.
• When the precondition breaks, unverified sampling diverges on 40 of 40 inputs, verified sampling on none; the result is the same across both seeds.
• On a sixteen-queens board, the deterministic order visits 10,053 nodes, the random order an average of 359.6 and 355.8 nodes, and all forty runs find a valid solution; the extremes range from 19 to 3379, so the average is an expectation, not a guarantee.
• With a hundred-node budget, restarting brings the average down to 225.8, the worst run from 3379 to 940, and the answer still stays 20 / 20 valid.

Next Step

This topic ran six design approaches through the same measure, and the same thing came out every time: an approach’s value is visible not in the steps it saves but in the wrong answers it gives once its precondition breaks. The next topic carries this measure to problem patterns. There, the patterns are narrower and more recognizable — scanning from both ends in a sorted array, incremental computation on a contiguous subarray, connected-component search on a grid — and each one’s precondition can be written in a single sentence. The first lesson opens with the two-pointer pattern, which requires sorted input, and its question is the same as here: on how many inputs does a wrong answer appear once the ordering breaks.