--- title: 'Randomized Algorithms' source: 'https://academia.sh/en/courses/advanced-algorithms/randomized-algorithms' course: 'Advanced Algorithms and Problem Solving' language: en updated: '2026-08-17T18:07:27+00:00' license: 'CC BY-SA 4.0' --- # Randomized Algorithms Randomness can be used in two separate places, and the two are measured separately: unverified sampling returns a wrong value on all 40 of the 40 arrays with no majority, while verified sampling never errs on the same arrays, and on a sixteen-queens board, random column order brings a 10,053-node deterministic search down to an average of 360 nodes. 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. ```python # 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. ```python # 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**. ```python # 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. ```python # 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. ```python # 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.