How statement and proof provenance work
The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.
- Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
- AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
- AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.
These labels describe origin, not correctness: citations and verification chips remain separate evidence.
Dominating thinning has the prescribed reaction law
Statement
Assume Countable Choice and Dependent Choice. Let be finite or countable, with finitely many time-dependent propensities on as in Finite-channel reaction propensity systems and their generator. Suppose a certified constant envelope holds for all and . Then the dominating-thinning algorithm in Dominating thinning for bounded time-varying propensities, with an unlimited candidate budget, has the following exact conditional law from time and state :
Write for the sigma-algebra generated by the candidate times and marks in . Then, for , , and ,
and for every Borel and channel ,
After a reaction, the same rule restarts at its new time and state. Candidate events on have a Poisson count of mean ; accepted reactions are a subset, so there are finitely many accepted reactions almost surely and . The conclusion is conditional on the stated envelope; no law is asserted when it fails.
When , the same two conditional-law conclusions hold if, at each fixed , channel is accepted on a Borel mark set , provided these sets are pairwise disjoint, have Lebesgue measure , and for each fixed state the region is measurable for . The standard cumulative intervals in the algorithm are one such choice: their endpoints are finite sums of the Borel time sections , so their time-mark regions are product-measurable. If , the step 5.1 constant-path case applies. This equivalent mark-set form is used by the minimum-intensity coupling construction.
Facts & Assumptions
Given: Countable Choice, Dependent Choice, a reaction propensity system, an independent stream of unit exponential variables and unit-interval uniform variables, and a certified envelope .
The reaction network specifies admissible increments, finite channel rates, and the time-dependent rate sum . (Finite-channel reaction propensity systems and their generator)
The global envelope is an admissibility precondition for the algorithm. Its pointwise runtime guard reports invalid-envelope only if it encounters a candidate time and state where ; it does not verify a global certificate exhaustively. (Dominating thinning for bounded time-varying propensities)
Under Countable Choice and Dependent Choice the countable random-input stream can be realized with the prescribed finite-coordinate product laws. (Assuming countable and dependent choice, countable products of arbitrary probability spaces)
The homogeneous Poisson process on with rate has finite total count and ordered event-time density on . (Finite-window homogeneous Poisson construction and ordered event-time density)
A finite-intensity Poisson point process has the mixed-binomial construction: conditional on a Poisson total count, its points have the normalized intensity law. By the defining independent-count property, its restrictions to disjoint Borel time intervals are independent. (Finite-intensity Poisson-process existence and mixed-binomial law, Poisson and Cox point processes)
Nonnegative product-measurable functions may be integrated by sections (Tonelli), so the mark-region measure is the time integral of its mark lengths. The product-measurability hypothesis in the generalized mark-set clause supplies this condition for each fixed state. (For sigma-finite factors, the product measure exists, has the rectangle formula, is sigma-finite, and is unique, Tonelli's theorem for nonnegative measurable functions on a sigma-finite product)
Countable Choice is used in the exponential and unit-interval probability laws. (The Axiom of Countable Choice ())
Dependent Choice is used in constructing the countable product probability space for the infinite stream of random inputs. (The axiom of dependent choice: a relation in which every element is related to something admits an -indexed chain)
Proof
First assume . If the candidate interarrival increments are , then for exactly candidates at ordered times , the product of the exponential gap densities and the final no-candidate survival factor is where . This is the ordered-event density in [F4]. The independent uniform marks give the conditional product-uniform mark law, so [F5] identifies the finite marked candidate pattern with a Poisson point process of intensity on . By the defining independent-count property in [F5], restrictions to disjoint time intervals are independent; after translating time, the restriction to any interval of length has ordered-time density . In particular .
Fix deterministic , condition on with , and let . By step 1.1 and [F5], future candidates in are independent of and their ordered-time density is . For put . Conditional on ordered candidate times, the probability all marks are rejected is the product of their rejection fractions. Using that density and Tonelli [F6], the conditional probability of no accepted candidate is The middle identity holds because the symmetric product integrand has equal integrals on the orderings of the cube; ties form a Lebesgue-null set.
Fix a channel and a Borel set . By step 1.1 and [F5], future candidate points on are independent of and have ordered-time density . For the first accepted candidate to occur at time with mark in , all earlier candidates must be rejected, its mark must lie in a set of measure , and later candidates are unrestricted. For earlier rejected candidates, integration over their ordered times contributes ; for later unrestricted candidates, integration contributes . Summing the nonnegative series and using [F6], the first-event measure on is This proves the channel-specific first-event law for arbitrary Borel rates and for disjoint mark sets of the specified measures whose time-mark regions are product-measurable; their locations within do not enter the calculation. The endpoint mark conventions differ only on a null set.
At an accepted candidate time the new state depends only on the past and that candidate's time and mark. If its candidate index is , the event is determined by the first gap and mark coordinates; partitioning over finite shows that the coordinates after retain their prescribed product law. Thus the same two calculations restart at the new state and time. Since pathwise, [F7] and step 1.1 give and almost surely. Repeating the event-kernel construction proves the full path law through .
If , the envelope forces every propensity to vanish everywhere, so the constant path is exact. If the global envelope hypothesis is false, this theorem asserts no path law; the algorithm returns invalid-envelope only if its pointwise guard encounters a violating candidate as specified in [F2]. Steps 1.1, 2.1, 3.1 and 4.1 establish the candidate law, both conditional event laws, the restart rule and the finite-count bound under the global envelope.
Depends on
- The Axiom of Countable Choice ($\mathrm{AC}_\omega$)
- The axiom of dependent choice: a relation in which every element is related to something admits an $\mathbb{N}$-indexed chain
- Lebesgue measurable sets, the family $\mathcal{L}(\mathbb{R}^n)$, and the restricted set function $\lambda_n$
- Poisson and Cox point processes
- Finite-channel reaction propensity systems and their generator
- The scalar Poisson count law
- Dominating thinning for bounded time-varying propensities
- Competing exponential clocks give the reaction event law
- Finite-window homogeneous Poisson construction and ordered event-time density
- Normalization, moments, and generating function of the Poisson count law
- Assuming countable and dependent choice, countable products of arbitrary probability spaces
- Exponential and Weibull survival specifications define probability laws
- Finite-intensity Poisson-process existence and mixed-binomial law
- A box in $\mathbb{R}^n$ with parameters $a_i\le b_i$ is Lebesgue measurable of measure $\prod_{i<n}(b_i-a_i)$, whichever of its faces are included
- For sigma-finite factors, the product measure exists, has the rectangle formula, is sigma-finite, and is unique
- Tonelli's theorem for nonnegative measurable functions on a sigma-finite product
Used by
- Clipping an understated thinning envelope changes the waiting-time law Counterexample
- Minimum-intensity coupling of two birth-death chains Example
- Compensators, brackets, and jump-integral isometry for reaction counts Theorem
- Finite-state Gillespie and next-reaction methods have the specified CTMC law Theorem
- The minimum-intensity reaction coupling preserves both marginals Theorem
Dependency tree · two levels
98 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.
Sources
- David F. Anderson, Introduction to Stochastic Processes with Applications to Biology, Chapters 6–7 (standard reference, not scraped)
- David F. Anderson and Thomas G. Kurtz, Continuous Time Markov Chain Models for Chemical Reaction Networks (standard reference, not scraped)