Lax195003.WordRamRandomness
Randomized computation on the word RAM
concepts/Lax195003/WordRamRandomness.lean · lax-195003
No public endorsements yet.
Loading review…
Sign in with ORCIDConcept map
Definition
A randomized word-RAM computation is a deterministic word-RAM program whose ordinary input is followed by a finite tape of independent uniform random bits. Given a rational threshold q, it succeeds with probability at least q within time T if every random tape makes the program halt within T steps, and at least a q fraction of the equally likely bit strings make it halt with an accepted output.
Lean source view on GitHub
| 1 | import Lax67.Ram |
| 2 | import Mathlib.Data.Rat.Cast.Order |
| 3 | import Mathlib.Data.Set.Card |
| 4 | |
| 5 | /-! |
| 6 | --- |
| 7 | title: Randomized computation on the word RAM |
| 8 | type: definition |
| 9 | --- |
| 10 | A randomized word-RAM computation is a deterministic word-RAM program whose |
| 11 | ordinary input is followed by a finite tape of independent uniform random |
| 12 | bits. Given a rational threshold *q*, it succeeds with probability at least |
| 13 | *q* within time *T* if every random tape makes the program halt within *T* |
| 14 | steps, and at least a *q* fraction of the equally likely bit strings make it |
| 15 | halt with an accepted output. |
| 16 | |
| 17 | # Formalization notes |
| 18 | |
| 19 | The machine itself is exactly the word RAM of Lax67; randomness is input, not |
| 20 | a new primitive instruction. A random tape of length `r` is a function |
| 21 | `Fin r → Bool`, encoded in index order by the words zero and one. There are |
| 22 | exactly `2 ^ r` such tapes. For a rational success threshold `q`, the |
| 23 | inequality `q · 2^r ≤ |good tapes|` states the probability bound without |
| 24 | introducing a measure-theoretic representation of a finite experiment. The |
| 25 | Welzl-order theorem instantiates `q` with `2/3`. |
| 26 | |
| 27 | The definition separates total running time from success: every tape must |
| 28 | halt within the bound, while a bad tape may return any output. The accepting |
| 29 | condition is a relation on output words because a search algorithm may return |
| 30 | any one of many correct witnesses. Supplying more bits than a program reads |
| 31 | does not alter the success fraction—each used prefix has equally many |
| 32 | extensions—so a theorem may use its time bound itself as a uniform tape |
| 33 | length without exposing an implementation-specific random-bit count. |
| 34 | -/ |
| 35 | |
| 36 | namespace Lax195003.WordRamRandomness |
| 37 | |
| 38 | open Lax67.Ram |
| 39 | |
| 40 | /-- A bit tape as a word list, in index order, with `false` encoded by zero |
| 41 | and `true` by one. -/ |
| 42 | def bitTape {r : ℕ} (ρ : Fin r → Bool) : List ℕ := |
| 43 | List.ofFn (fun i : Fin r => if ρ i then 1 else 0) |
| 44 | |
| 45 | /-- The program halts within `T` steps on every `r`-bit tape, and on at least |
| 46 | a `successProbability` fraction of those tapes its output satisfies `Accept`. -/ |
| 47 | noncomputable def SucceedsWithProbabilityAtLeastInTime |
| 48 | (successProbability : ℚ) (w : ℕ) (p : Program) |
| 49 | (input : List ℕ) (r T : ℕ) |
| 50 | (Accept : List ℕ → Prop) : Prop := |
| 51 | (∀ ρ : Fin r → Bool, ∃ y : List ℕ, ∃ t ≤ T, |
| 52 | RunsTo w p (input ++ bitTape ρ) y t) ∧ |
| 53 | successProbability * (2 ^ r : ℚ) ≤ |
| 54 | ({ρ : Fin r → Bool | ∃ y : List ℕ, ∃ t ≤ T, |
| 55 | RunsTo w p (input ++ bitTape ρ) y t ∧ Accept y}.ncard : ℚ) |
| 56 | |
| 57 | end Lax195003.WordRamRandomness |
| 58 |
Formalization notes
The machine itself is exactly the word RAM of Lax67; randomness is input, not a new primitive instruction. A random tape of length is a function , encoded in index order by the words zero and one. There are exactly such tapes. For a rational success threshold , the inequality states the probability bound without introducing a measure-theoretic representation of a finite experiment. The Welzl-order theorem instantiates with .
The definition separates total running time from success: every tape must halt within the bound, while a bad tape may return any output. The accepting condition is a relation on output words because a search algorithm may return any one of many correct witnesses. Supplying more bits than a program reads does not alter the success fraction—each used prefix has equally many extensions—so a theorem may use its time bound itself as a uniform tape length without exposing an implementation-specific random-bit count.
Builds on
From Mathlib
Community review
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above; your ORCID profile must share a public name.
0 comments