∑MathAdvanced

Sigma-Algebras & Measure Spaces

Key Points

•
A $σ - a l g e b r a$ is a collection of subsets that is closed under complements and countable unions, giving us a stable universe of sets where measure makes sense.
•
A measure assigns a nonnegative size to sets in a $σ - a l g e b r a,$ with disjoint sets adding up; probability is a special case where the total measure is 1.
•
In finite settings, checking $σ - a l g e b r a$ closure reduces to complements and finite unions, which you can verify by enumeration.
•
Every partition of a finite set generates a $σ - a l g e b r a$ consisting of all unions of the partition’s atoms, and measures follow by summing atom weights.
•
Lebesgue measure generalizes length/area/volume; Monte Carlo sampling estimates such measures via averages of indicator functions.
•
Key limit laws like continuity from below/above make $σ - a l g e b r a s$ compatible with infinite processes and convergence.
•
Many algorithms informally use measure theory ideas (indicator functions, expected values, product measures) in probability, graphics, and data science.
•
When coding, represent sets compactly (e.g., bitmasks) to check $σ - a l g e b r a$ axioms and compute discrete measures efficiently.

Prerequisites

→Sets and logic — Understanding subsets, unions, intersections, complements, and quantifiers is essential for σ-algebra axioms.
→Sequences and limits — Measure continuity properties and countable operations rely on limits and convergence.
→Basic probability — Probability is a measure on a σ-algebra; events and expectations use indicator functions.
→Real analysis (basics) — Open/closed sets, intervals, and the Borel σ-algebra arise from topology on ℝ.
→Bitmask representations — Efficient finite set operations in C++ are natural with bitwise operators.
→Random number generation — Monte Carlo estimation requires high-quality uniform random samples.
→Time and space complexity — Finite σ-algebra enumeration is exponential in atoms; Monte Carlo is linear in samples.

Detailed Explanation

Tap terms for definitions

01Overview

A σ-algebra (sigma-algebra) is a carefully chosen family of subsets that is closed under operations we want to perform infinitely often: taking complements and countable unions. This structure ensures that limiting processes (like taking the union of infinitely many events) remain within the same family, avoiding paradoxes. A measure is a function assigning a nonnegative size to each set in a σ-algebra, generalizing familiar ideas like length of intervals, area of regions, and probability of events. Together, a measure space (X, 𝔽, μ) provides a rigorous framework for length/area/volume and for probability, where μ(∅)=0 and disjoint unions add their measures. In computer science and applied math, while true measure-theoretic objects can be infinite or uncountable, we often work with finite or algorithmically approximable versions. For example, on a finite set we can build a σ-algebra from a partition and define a discrete measure by summing atom weights. For geometric subsets of the plane, Monte Carlo sampling approximates Lebesgue measure by frequencies of hits within a region. These computational patterns reflect the core measure rules—closure operations and additivity—while giving practical, efficient tools. Understanding σ-algebras and measures clarifies why integration and probability work, explains convergence theorems, and supports algorithms like Monte Carlo integration, randomized analysis, and probabilistic modeling. The formalism balances expressive power (countable operations) with control (measurability), ensuring our size assignments are consistent and stable under limits.

02Intuition & Analogies

Imagine you run a library and want to track groups of books: by genre, by author, by publication year. If you promise that whenever you pick a group, you also keep track of its complement (the books not in that group), and that you can combine any countable list of groups into a new group (e.g., all mystery books or all sci-fi or all biographies, etc.), then your “collection of groups” is closed under the typical ways you might bundle books. That organized family of groups is like a σ-algebra: a safe zone where you can take complements and countably many unions without stepping outside your system. Now think of measure as assigning a weight to each group: perhaps the number of books, total pages, or estimated reading time. A key rule is additivity: if two groups don’t overlap, their combined weight is just the sum. This mirrors how shelf length for two disjoint stacks adds up or how separate probabilities add when events cannot both occur. For geometry, picture a grid overlaying a shape on the plane. The area of the shape can be approximated by counting how many squares it covers; as you refine the grid, your estimate stabilizes. A σ-algebra guarantees that the sophisticated limits you take while refining are legal and land on well-defined sets. In computing, we often simulate this: on finite universes we can list all unions of building blocks (atoms), and for continuous regions we sample random points and estimate area as the fraction of hits. In short: σ-algebras are the rulebook for which groups we’re allowed to measure; measures assign sizes that add up consistently; and together they let us reason safely about infinite constructions using finite approximations in code.

03Formal Definition

Let X be a set. A

σ - a l g e b r a

𝔽 on X is a nonempty collection of subsets of X such that: (1) X ∈ 𝔽, (2) if A ∈ 𝔽 then its complement

A^{c} = X

\ A ∈ 𝔽, and (3) if {

A_{i}

}_{

i=1}^{\infty}

⊆ 𝔽 then the countable union

⋃_{i = 1}^{\infty}

A_{i}

∈ 𝔽. By De Morgan’s laws, 𝔽 is also closed under countable intersections. A measure μ on (X, 𝔽) is a function

μ :

𝔽 → [0,

\infty

] such that

μ (\emptyset) = 0

and (countable additivity) for any sequence of pairwise disjoint sets {

A_{i}

} in 𝔽, we have μ

\big

(

⋃_{i = 1}^{\infty}

A_i\big

) =

\sum_{i = 1}^{\infty}

μ (A_{i}) .

The triple (X, 𝔽,

μ)

is a measure space. If

μ (X) = 1,

it is a probability space. Important consequences include monotonicity (A ⊆ B ⇒

μ (A)

≤

μ (B)),

finite additivity for disjoint unions, and continuity from below/above for increasing/decreasing sequences of sets (with a finiteness condition for the latter). The Borel

σ - a l g e b r a

R^{n}

, generated by open sets, under Lebesgue measure

λ,

formalizes our intuition of length/area/volume while remaining closed under standard limit operations. In finite settings,

σ - a l g e b r a s

generated by partitions consist of all unions of atoms, and measures are determined by atom weights.

04When to Use

Probability modeling: Events form a σ-algebra; probabilities are measures. Random variables are measurable functions, and expectations are integrals with respect to the probability measure.
Numerical integration and graphics: Monte Carlo integration estimates \int f , dμ by sampling. Estimating areas (Lebesgue measure) via random uniform points underlies rendering and coverage calculations.
Data aggregation: On finite datasets, partitions (e.g., user segments) generate σ-algebras; assigning weights (e.g., total spend) defines discrete measures where union and complement operations remain consistent.
Theoretical guarantees: When dealing with limits—like infinite unions, limits of events in probability (Borel–Cantelli), or convergence theorems (Monotone/Dominated Convergence)—σ-algebras ensure results remain measurable and measures behave continuously.
Product spaces: Modeling joint phenomena (time × outcomes, position × velocity) uses product measures. Rectangles A×B get measure μ(A)ν(B); Fubini/Tonelli justify swapping integrals/sums.
Algorithm design and analysis: Indicator functions and expectations translate algorithm performance into measurable quantities; tail bounds and laws of large numbers use measure-theoretic probability under the hood. Use finite σ-algebras and discrete measures when the universe is small and exact enumeration is feasible. Use Monte Carlo approximation when sets are defined by predicates in continuous spaces and exact geometry is hard or expensive.

⚠️Common Mistakes

Confusing algebras with σ-algebras: Closure under finite unions is not enough for limits; some probability theorems fail without countable closure. In finite universes, this coincides, but not on infinite sets.
Forgetting disjointness in additivity: μ(A ∪ B) = μ(A) + μ(B) only holds when A and B are disjoint. Otherwise use inclusion–exclusion: μ(A ∪ B) = μ(A) + μ(B) − μ(A ∩ B).
Ignoring measurability: Defining μ on all subsets of \mathbb{R} is impossible if you want countable additivity and translation invariance (Vitali sets). Borel/Lebesgue σ-algebras exist to avoid such pathologies.
Mixing outer measure and measure: Outer measure μ* is defined on all subsets and is subadditive; a measurable set E must satisfy Carathéodory’s criterion μ*(A) = μ*(A ∩ E) + μ*(A \ E) for all A. Failing this leads to paradoxes.
Misinterpreting measure-zero: A set of measure zero is not necessarily empty or impossible; it can be infinite or dense. Events of probability zero can still happen—they are just negligible in measure.
Numerical pitfalls: Monte Carlo estimates have variance; too few samples or poor RNGs lead to biased estimates. Always compute confidence intervals and seed RNGs carefully.
Overlooking product measures: Assuming μ(A × B) = μ(A)μ(B) without checking independence/product structure can be wrong; this equality is a definition in product spaces, not a universal fact.

Key Formulas

σ-algebra axioms

\emptyset \in F, X \in F; A \in F \Rightarrow A^{c} \in F; (A_{i})_{i = 1}^{\infty} \subseteq F \Rightarrow i = 1 ⋃ \infty A_{i} \in F

Explanation: These are the closure rules for $σ - a l g e b r a s :$ contain the whole space, be closed under complement, and be closed under countable unions. They guarantee stability under infinite operations.

Measure definition

μ : F \to [0, \infty], μ (\emptyset) = 0, A_{i} \cap A_{j} = \emptyset (i \neq = j) \Rightarrow μ (i = 1 ⋃ \infty A_{i}) = i = 1 \sum \infty μ (A_{i})

Explanation: A measure assigns a nonnegative size to measurable sets, with disjoint unions adding up. The empty set must have measure zero.

Monotonicity

A \subseteq B \Rightarrow μ (A) \leq μ (B)

Explanation: If one set is contained in another, its measure cannot be larger. This follows from additivity and nonnegativity.

Inclusion–Exclusion (two sets)

μ (A \cup B) = μ (A) + μ (B) - μ (A \cap B)

Explanation: When sets overlap, add their measures and subtract the overlap to avoid double counting. For disjoint sets, the intersection term is zero.

Continuity from below

A_{n} ↑ A \Rightarrow μ (A) = n \to \infty lim μ (A_{n})

Explanation: For an increasing sequence of sets converging to A, measures converge upward to $μ (A) .$ This formalizes stable growth under limits.

Continuity from above

A_{n} ↓ A, μ (A_{1}) < \infty \Rightarrow μ (A) = n \to \infty lim μ (A_{n})

Explanation: For a decreasing sequence with finite initial measure, measures converge downward to $μ (A) .$ This handles shrinking sequences.

Borel σ-algebra

B (R^{n}) = σ (open sets)

Explanation: The smallest $σ - a l g e b r a$ containing all open sets in ℝ^n. It includes intervals, rays, and more complex sets made by countable operations.

Lebesgue length of interval

λ ([a, b]) = b - a

Explanation: Lebesgue measure on ℝ matches our intuition: the measure of an interval equals its length. This anchors the theory to geometry.

Indicator integrates to measure

\int 1_{E} d μ = μ (E)

Explanation: The integral of an indicator function counts the measure of its set. This is the bridge from set size to integration and expectations.

Lebesgue outer measure on ℝ

μ^{*} (A) = in f {i = 1 \sum \infty ℓ (I_{i}) : A \subseteq i = 1 ⋃ \infty I_{i}}

Explanation: Outer measure is the greatest lower bound of total lengths of countable interval covers of A. It leads to the Lebesgue measure via Carathéodory.

Carathéodory criterion

E is measurable ⟺ \forall A, μ^{*} (A) = μ^{*} (A \cap E) + μ^{*} (A ∖ E)

Explanation: A set is measurable if it splits every other set additively with respect to outer measure. This selects the well-behaved sets.

Size of σ-algebra from a partition

∣ σ (P) ∣ = 2^{k}

Explanation: If a partition has k atoms, the generated $σ - a l g e b r a$ consists of all 2^k unions of atoms. Each subset of atoms defines a measurable set.

Product measure on rectangles

(μ \otimes ν) (A \times B) = μ (A) ν (B)

Explanation: In product spaces, rectangles get product measure. This extends uniquely to the full $σ - a l g e b r a,$ enabling multi-dimensional integration.

Monte Carlo estimator

\overset{μ}{^}_{N} (E) = \frac{1}{N} i = 1 \sum N 1_{E} (X_{i})

Explanation: Sampling $X_{i}$ from a reference measure (e.g., uniform) makes the average of indicators an unbiased estimator of $μ (E) .$ Variance decreases as 1/N.

Complexity Analysis

On a finite universe of size n, representing sets as bitmasks allows O(1) membership, complement, and union via bitwise operations. Verifying that a family F is a

σ - a l g e b r a

on a finite space reduces to checking closure under complements and finite unions (countable unions collapse to finite unions in finite spaces). If

∣ F ∣

=m, verifying complements is O(m) and verifying closure under binary unions is O(

m^{2}

) lookups; with a hash set for membership, each lookup is O(1) average, so total O(

m^{2}

). Space is O(m) for storing the family. Generating a

σ - a l g e b r a

from a partition with k atoms requires enumerating all 2^k unions; this is optimal since the

σ - a l g e b r a

has size 2^k. Time is O(2^k) to enumerate (each union is built in O(k) or O(1) with bitmasks), and space is O(2^k) to store all sets. For discrete measures on a finite

σ - a l g e b r a,

evaluating

μ (A)

is O(number of atoms in A). With bitmasks and precomputed atom weights, this is O(k) per query (or O(popcount) if using bit tricks). Verifying finite additivity on all disjoint pairs is O(

m^{2}

) in the worst case. Monte Carlo estimation of Lebesgue measure

\frac{a re a}{v o l u m e}

for a predicate over a bounded region uses N independent samples. Each sample costs O(1) predicate time, yielding O(N) total time and O(1) extra space (besides RNG state). The estimator’s mean-squared error is O

\frac{1}{N}

, and confidence intervals shrink as O(1/√N). Compared to exact geometric algorithms, Monte Carlo scales well to high dimensions where deterministic gridding is exponential in dimension, but convergence becomes slow for very small target measures or highly oscillatory predicates. In summary: exact finite

σ - a l g e b r a s

scale exponentially with the number of atoms, while Monte Carlo scales linearly with samples and is dimension-agnostic; choose accordingly based on problem size and structure.

Code Examples

Check σ-algebra axioms on a finite universe using bitmasks

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Helper: print a subset represented as a bitmask over {0,...,n-1}
5 string setToString(uint64_t mask, int n) {
6     vector<int> elems;
7     for (int i = 0; i < n; ++i) if (mask & (1ULL << i)) elems.push_back(i);
8     string s = "{";
9     for (size_t i = 0; i < elems.size(); ++i) {
10         s += to_string(elems[i]);
11         if (i + 1 < elems.size()) s += ", ";
12     }
13     s += "}";
14     return s;
15 }
16 
17 bool contains(const unordered_set<uint64_t>& fam, uint64_t s) {
18     return fam.find(s) != fam.end();
19 }
20 
21 // Check if a family F is a sigma-algebra on universe of size n.
22 // In a finite universe, closure under complements and finite unions suffices.
23 bool isSigmaAlgebra(int n, const vector<uint64_t>& Fvec) {
24     uint64_t U = (n == 64) ? ~0ULL : ((1ULL << n) - 1ULL);
25     unordered_set<uint64_t> F(Fvec.begin(), Fvec.end());
26 
27     // 1) Must contain empty set and universe
28     if (!contains(F, 0ULL) || !contains(F, U)) return false;
29 
30     // 2) Closed under complement
31     for (auto s : F) {
32         uint64_t comp = (~s) & U; // complement relative to universe
33         if (!contains(F, comp)) return false;
34     }
35 
36     // 3) Closed under finite unions (check pairwise unions)
37     for (auto a : F) {
38         for (auto b : F) {
39             uint64_t u = a | b;
40             if (!contains(F, u)) return false;
41         }
42     }
43 
44     // If all checks pass, in a finite universe this implies closure under countable unions
45     return true;
46 }
47 
48 int main() {
49     ios::sync_with_stdio(false);
50     cin.tie(nullptr);
51 
52     // Universe X = {0,1,2,3}
53     int n = 4;
54     uint64_t U = (1ULL << n) - 1ULL;
55 
56     // Build a valid sigma-algebra from a partition: A0={0,1}, A1={2}, A2={3}
57     uint64_t A0 = (1ULL<<0) | (1ULL<<1);
58     uint64_t A1 = (1ULL<<2);
59     uint64_t A2 = (1ULL<<3);
60     vector<uint64_t> atoms = {A0, A1, A2};
61 
62     // Generate all unions of atoms (size 2^3 = 8)
63     vector<uint64_t> valid;
64     for (int mask = 0; mask < (1<< (int)atoms.size()); ++mask) {
65         uint64_t s = 0ULL;
66         for (int i = 0; i < (int)atoms.size(); ++i) if (mask & (1<<i)) s |= atoms[i];
67         valid.push_back(s);
68     }
69 
70     // An invalid family (missing complement and not closed under unions)
71     vector<uint64_t> invalid = {0ULL, A0, A1}; // lacks A2 and many closures
72 
73     cout << "Valid family is sigma-algebra? " << (isSigmaAlgebra(n, valid) ? "yes" : "no") << "\n";
74     cout << "Invalid family is sigma-algebra? " << (isSigmaAlgebra(n, invalid) ? "yes" : "no") << "\n\n";
75 
76     cout << "Elements of the valid sigma-algebra on X={0,1,2,3}:\n";
77     for (auto s : valid) cout << setToString(s, n) << "\n";
78 
79     return 0;
80 }
81

On a finite universe, we represent subsets as 64-bit masks. We verify the σ-algebra axioms by checking that the family contains ∅ and X, is closed under complements, and closed under pairwise unions (sufficient for countable unions in finite spaces). We construct a valid σ-algebra generated by a partition and compare it to an invalid family.

Time: O(m^2) to check closure under unions for a family of size m; O(m) for complements.Space: O(m) to store the family plus O(1) working space.

Generate σ-algebra from a partition and compute a discrete measure

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 struct DiscreteMeasure {
5     int n; // universe size (0..n-1)
6     vector<uint64_t> atoms; // disjoint nonempty subsets covering the universe
7     vector<double> atomWeight; // nonnegative weights per atom
8     uint64_t U; // universe bitmask
9     vector<uint64_t> sigma; // all unions of atoms (the sigma-algebra)
10 
11     DiscreteMeasure(int n_, const vector<uint64_t>& atoms_, const vector<double>& w)
12         : n(n_), atoms(atoms_), atomWeight(w) {
13         U = (n == 64) ? ~0ULL : ((1ULL << n) - 1ULL);
14         // Sanity: atoms disjoint and cover U
15         uint64_t cover = 0ULL;
16         for (auto a : atoms) cover |= a;
17         if (cover != U) throw runtime_error("Atoms must cover the universe");
18         for (size_t i = 0; i < atoms.size(); ++i)
19             for (size_t j = i+1; j < atoms.size(); ++j)
20                 if (atoms[i] & atoms[j]) throw runtime_error("Atoms must be disjoint");
21         if (atoms.size() != atomWeight.size()) throw runtime_error("Weights mismatch");
22         for (double x : atomWeight) if (x < 0) throw runtime_error("Negative weight");
23         // Generate all unions (2^k)
24         int k = (int)atoms.size();
25         sigma.reserve(1<<k);
26         for (int mask = 0; mask < (1<<k); ++mask) {
27             uint64_t s = 0ULL;
28             for (int i = 0; i < k; ++i) if (mask & (1<<i)) s |= atoms[i];
29             sigma.push_back(s);
30         }
31     }
32 
33     // Measure of a measurable set s: sum of atom weights included in s
34     double mu(uint64_t s) const {
35         double total = 0.0;
36         for (size_t i = 0; i < atoms.size(); ++i)
37             if (s & atoms[i]) total += atomWeight[i];
38         return total;
39     }
40 
41     // Test finite additivity for all disjoint pairs in sigma (diagnostic)
42     bool testAdditivity(double eps=1e-12) const {
43         unordered_set<uint64_t> fam(sigma.begin(), sigma.end());
44         for (auto A : sigma) {
45             for (auto B : sigma) {
46                 if (A & B) continue; // only disjoint pairs
47                 uint64_t UAB = A | B;
48                 if (!fam.count(UAB)) return false;
49                 double lhs = mu(UAB);
50                 double rhs = mu(A) + mu(B);
51                 if (fabs(lhs - rhs) > eps) return false;
52             }
53         }
54         return true;
55     }
56 };
57 
58 string setToString(uint64_t mask, int n) {
59     vector<int> elems;
60     for (int i = 0; i < n; ++i) if (mask & (1ULL << i)) elems.push_back(i);
61     string s = "{";
62     for (size_t i = 0; i < elems.size(); ++i) {
63         s += to_string(elems[i]);
64         if (i + 1 < elems.size()) s += ", ";
65     }
66     s += "}";
67     return s;
68 }
69 
70 int main(){
71     ios::sync_with_stdio(false);
72     cin.tie(nullptr);
73 
74     // Universe X = {0,1,2,3,4,5}
75     int n = 6;
76     uint64_t U = (1ULL<<n)-1ULL;
77 
78     // Partition atoms: A0={0,1}, A1={2,3}, A2={4}, A3={5}
79     vector<uint64_t> atoms = {
80         (1ULL<<0)|(1ULL<<1),
81         (1ULL<<2)|(1ULL<<3),
82         (1ULL<<4),
83         (1ULL<<5)
84     };
85 
86     // Assign nonnegative weights to atoms (sum need not be 1 unless you want a probability measure)
87     vector<double> w = {0.3, 0.2, 0.1, 0.4};
88 
89     DiscreteMeasure dm(n, atoms, w);
90 
91     cout.setf(std::ios::fixed); cout<<setprecision(6);
92 
93     cout << "Sigma-algebra size: " << dm.sigma.size() << " (should be 2^4=16)\n";
94 
95     // Pick two disjoint measurable sets and verify additivity
96     uint64_t A = atoms[0];                 // {0,1}
97     uint64_t B = atoms[2] | atoms[3];      // {4,5}
98     cout << "A=" << setToString(A,n) << ", mu(A)=" << dm.mu(A) << "\n";
99     cout << "B=" << setToString(B,n) << ", mu(B)=" << dm.mu(B) << "\n";
100     cout << "A \\cup B=" << setToString(A|B,n) << ", mu(A \\cup B)=" << dm.mu(A|B) << "\n";
101 
102     // Global additivity test on all disjoint pairs
103     cout << "Finite additivity holds on all disjoint pairs? " << (dm.testAdditivity() ? "yes" : "no") << "\n";
104 
105     // If you want a probability measure, normalize the weights so mu(U)=1
106     double total = dm.mu(U);
107     cout << "Total mass mu(U)=" << total << "\n";
108 
109     return 0;
110 }
111

A partition’s atoms generate a σ-algebra of all unions. Assigning nonnegative weights to atoms defines a measure on the σ-algebra, computed by summing the weights of included atoms. We verify finite additivity for disjoint unions and show how to normalize to a probability measure.

Time: O(2^k) to generate the σ-algebra for k atoms; O(k) per measure query; O(|σ|^2) for exhaustive additivity tests on disjoint pairs.Space: O(2^k) to store all measurable sets; O(k) for atom weights.

Monte Carlo approximation of Lebesgue measure (area) of a planar set

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Estimate area of E = {(x,y) in [0,1]^2 : x^2 + y^2 <= 1} (a quarter of the unit disk)
5 // True area = pi/4 ≈ 0.785398...
6 int main(){
7     ios::sync_with_stdio(false);
8     cin.tie(nullptr);
9 
10     const uint64_t N = 5'000'000; // number of samples (adjust as needed)
11 
12     std::mt19937_64 rng(123456789); // fixed seed for reproducibility
13     std::uniform_real_distribution<double> U(0.0, 1.0);
14 
15     uint64_t hits = 0;
16     for (uint64_t i = 0; i < N; ++i) {
17         double x = U(rng);
18         double y = U(rng);
19         if (x*x + y*y <= 1.0) ++hits; // indicator 1_E(x,y)
20     }
21 
22     double est = static_cast<double>(hits) / static_cast<double>(N); // average of indicators
23 
24     // Approximate 95% confidence interval using normal approximation: p ± 1.96*sqrt(p(1-p)/N)
25     double p = est;
26     double se = sqrt(max(1e-18, p*(1.0-p) / static_cast<double>(N)));
27     double lo = p - 1.96 * se;
28     double hi = p + 1.96 * se;
29 
30     cout.setf(std::ios::fixed); cout<<setprecision(6);
31     cout << "Estimated area mu(E) ≈ " << est << "\n";
32     cout << "95% CI: [" << lo << ", " << hi << "]\n";
33     cout << "True area pi/4 ≈ " << M_PI/4.0 << "\n";
34 
35     return 0;
36 }
37

Sampling uniformly from [0,1]^2, the area of a set equals the probability that a random point lands in it. The Monte Carlo estimator is the sample average of the set’s indicator function. The variance shrinks as 1/N; we report a normal-approximation confidence interval.

Time: O(N) for N samples.Space: O(1) extra space beyond RNG state.

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Helper: print a subset represented as a bitmask over {0,...,n-1}
5	string setToString(uint64_t mask, int n) {
6	vector<int> elems;
7	for (int i = 0; i < n; ++i) if (mask & (1ULL << i)) elems.push_back(i);
8	string s = "{";
9	for (size_t i = 0; i < elems.size(); ++i) {
10	s += to_string(elems[i]);
11	if (i + 1 < elems.size()) s += ", ";
12	}
13	s += "}";
14	return s;
15	}
16
17	bool contains(const unordered_set<uint64_t>& fam, uint64_t s) {
18	return fam.find(s) != fam.end();
19	}
20
21	// Check if a family F is a sigma-algebra on universe of size n.
22	// In a finite universe, closure under complements and finite unions suffices.
23	bool isSigmaAlgebra(int n, const vector<uint64_t>& Fvec) {
24	uint64_t U = (n == 64) ? ~0ULL : ((1ULL << n) - 1ULL);
25	unordered_set<uint64_t> F(Fvec.begin(), Fvec.end());
26
27	// 1) Must contain empty set and universe
28	if (!contains(F, 0ULL) \|\| !contains(F, U)) return false;
29
30	// 2) Closed under complement
31	for (auto s : F) {
32	uint64_t comp = (~s) & U; // complement relative to universe
33	if (!contains(F, comp)) return false;
34	}
35
36	// 3) Closed under finite unions (check pairwise unions)
37	for (auto a : F) {
38	for (auto b : F) {
39	uint64_t u = a \| b;
40	if (!contains(F, u)) return false;
41	}
42	}
43
44	// If all checks pass, in a finite universe this implies closure under countable unions
45	return true;
46	}
47
48	int main() {
49	ios::sync_with_stdio(false);
50	cin.tie(nullptr);
51
52	// Universe X = {0,1,2,3}
53	int n = 4;
54	uint64_t U = (1ULL << n) - 1ULL;
55
56	// Build a valid sigma-algebra from a partition: A0={0,1}, A1={2}, A2={3}
57	uint64_t A0 = (1ULL<<0) \| (1ULL<<1);
58	uint64_t A1 = (1ULL<<2);
59	uint64_t A2 = (1ULL<<3);
60	vector<uint64_t> atoms = {A0, A1, A2};
61
62	// Generate all unions of atoms (size 2^3 = 8)
63	vector<uint64_t> valid;
64	for (int mask = 0; mask < (1<< (int)atoms.size()); ++mask) {
65	uint64_t s = 0ULL;
66	for (int i = 0; i < (int)atoms.size(); ++i) if (mask & (1<<i)) s \|= atoms[i];
67	valid.push_back(s);
68	}
69
70	// An invalid family (missing complement and not closed under unions)
71	vector<uint64_t> invalid = {0ULL, A0, A1}; // lacks A2 and many closures
72
73	cout << "Valid family is sigma-algebra? " << (isSigmaAlgebra(n, valid) ? "yes" : "no") << "\n";
74	cout << "Invalid family is sigma-algebra? " << (isSigmaAlgebra(n, invalid) ? "yes" : "no") << "\n\n";
75
76	cout << "Elements of the valid sigma-algebra on X={0,1,2,3}:\n";
77	for (auto s : valid) cout << setToString(s, n) << "\n";
78
79	return 0;
80	}
81

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	struct DiscreteMeasure {
5	int n; // universe size (0..n-1)
6	vector<uint64_t> atoms; // disjoint nonempty subsets covering the universe
7	vector<double> atomWeight; // nonnegative weights per atom
8	uint64_t U; // universe bitmask
9	vector<uint64_t> sigma; // all unions of atoms (the sigma-algebra)
10
11	DiscreteMeasure(int n_, const vector<uint64_t>& atoms_, const vector<double>& w)
12	: n(n_), atoms(atoms_), atomWeight(w) {
13	U = (n == 64) ? ~0ULL : ((1ULL << n) - 1ULL);
14	// Sanity: atoms disjoint and cover U
15	uint64_t cover = 0ULL;
16	for (auto a : atoms) cover \|= a;
17	if (cover != U) throw runtime_error("Atoms must cover the universe");
18	for (size_t i = 0; i < atoms.size(); ++i)
19	for (size_t j = i+1; j < atoms.size(); ++j)
20	if (atoms[i] & atoms[j]) throw runtime_error("Atoms must be disjoint");
21	if (atoms.size() != atomWeight.size()) throw runtime_error("Weights mismatch");
22	for (double x : atomWeight) if (x < 0) throw runtime_error("Negative weight");
23	// Generate all unions (2^k)
24	int k = (int)atoms.size();
25	sigma.reserve(1<<k);
26	for (int mask = 0; mask < (1<<k); ++mask) {
27	uint64_t s = 0ULL;
28	for (int i = 0; i < k; ++i) if (mask & (1<<i)) s \|= atoms[i];
29	sigma.push_back(s);
30	}
31	}
32
33	// Measure of a measurable set s: sum of atom weights included in s
34	double mu(uint64_t s) const {
35	double total = 0.0;
36	for (size_t i = 0; i < atoms.size(); ++i)
37	if (s & atoms[i]) total += atomWeight[i];
38	return total;
39	}
40
41	// Test finite additivity for all disjoint pairs in sigma (diagnostic)
42	bool testAdditivity(double eps=1e-12) const {
43	unordered_set<uint64_t> fam(sigma.begin(), sigma.end());
44	for (auto A : sigma) {
45	for (auto B : sigma) {
46	if (A & B) continue; // only disjoint pairs
47	uint64_t UAB = A \| B;
48	if (!fam.count(UAB)) return false;
49	double lhs = mu(UAB);
50	double rhs = mu(A) + mu(B);
51	if (fabs(lhs - rhs) > eps) return false;
52	}
53	}
54	return true;
55	}
56	};
57
58	string setToString(uint64_t mask, int n) {
59	vector<int> elems;
60	for (int i = 0; i < n; ++i) if (mask & (1ULL << i)) elems.push_back(i);
61	string s = "{";
62	for (size_t i = 0; i < elems.size(); ++i) {
63	s += to_string(elems[i]);
64	if (i + 1 < elems.size()) s += ", ";
65	}
66	s += "}";
67	return s;
68	}
69
70	int main(){
71	ios::sync_with_stdio(false);
72	cin.tie(nullptr);
73
74	// Universe X = {0,1,2,3,4,5}
75	int n = 6;
76	uint64_t U = (1ULL<<n)-1ULL;
77
78	// Partition atoms: A0={0,1}, A1={2,3}, A2={4}, A3={5}
79	vector<uint64_t> atoms = {
80	(1ULL<<0)\|(1ULL<<1),
81	(1ULL<<2)\|(1ULL<<3),
82	(1ULL<<4),
83	(1ULL<<5)
84	};
85
86	// Assign nonnegative weights to atoms (sum need not be 1 unless you want a probability measure)
87	vector<double> w = {0.3, 0.2, 0.1, 0.4};
88
89	DiscreteMeasure dm(n, atoms, w);
90
91	cout.setf(std::ios::fixed); cout<<setprecision(6);
92
93	cout << "Sigma-algebra size: " << dm.sigma.size() << " (should be 2^4=16)\n";
94
95	// Pick two disjoint measurable sets and verify additivity
96	uint64_t A = atoms[0]; // {0,1}
97	uint64_t B = atoms[2] \| atoms[3]; // {4,5}
98	cout << "A=" << setToString(A,n) << ", mu(A)=" << dm.mu(A) << "\n";
99	cout << "B=" << setToString(B,n) << ", mu(B)=" << dm.mu(B) << "\n";
100	cout << "A \\cup B=" << setToString(A\|B,n) << ", mu(A \\cup B)=" << dm.mu(A\|B) << "\n";
101
102	// Global additivity test on all disjoint pairs
103	cout << "Finite additivity holds on all disjoint pairs? " << (dm.testAdditivity() ? "yes" : "no") << "\n";
104
105	// If you want a probability measure, normalize the weights so mu(U)=1
106	double total = dm.mu(U);
107	cout << "Total mass mu(U)=" << total << "\n";
108
109	return 0;
110	}
111

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Estimate area of E = {(x,y) in [0,1]^2 : x^2 + y^2 <= 1} (a quarter of the unit disk)
5	// True area = pi/4 ≈ 0.785398...
6	int main(){
7	ios::sync_with_stdio(false);
8	cin.tie(nullptr);
9
10	const uint64_t N = 5'000'000; // number of samples (adjust as needed)
11
12	std::mt19937_64 rng(123456789); // fixed seed for reproducibility
13	std::uniform_real_distribution<double> U(0.0, 1.0);
14
15	uint64_t hits = 0;
16	for (uint64_t i = 0; i < N; ++i) {
17	double x = U(rng);
18	double y = U(rng);
19	if (xx + yy <= 1.0) ++hits; // indicator 1_E(x,y)
20	}
21
22	double est = static_cast<double>(hits) / static_cast<double>(N); // average of indicators
23
24	// Approximate 95% confidence interval using normal approximation: p ± 1.96*sqrt(p(1-p)/N)
25	double p = est;
26	double se = sqrt(max(1e-18, p*(1.0-p) / static_cast<double>(N)));
27	double lo = p - 1.96 * se;
28	double hi = p + 1.96 * se;
29
30	cout.setf(std::ios::fixed); cout<<setprecision(6);
31	cout << "Estimated area mu(E) ≈ " << est << "\n";
32	cout << "95% CI: [" << lo << ", " << hi << "]\n";
33	cout << "True area pi/4 ≈ " << M_PI/4.0 << "\n";
34
35	return 0;
36	}
37