Alphabeta MathRandom graphs and matrix concentration
Develop degree tails, trace and Gaussian estimates, and concentration; connect them to regular spectra, connectivity and synchronization thresholds with each input's model and asymptotic range.
1 · Prerequisites
- The Erdős-Rényi finite random graph G(n,p)
- A finite simple graph is a finite vertex set together with a set of two-element vertex subsets
- Bernoulli random variables and binomial random variables as sums of independent Bernoulli trials
- Pairwise and mutual independence of finite-valued random variables
- A Bernoulli(p) variable has mean p and variance p(1-p); a binomial(n,p) variable has mean np and variance np(1-p)
- Variance, standard deviation, and covariance on a finite probability space
- Variance and covariance identities for random variables
- Independence forces covariance to vanish
- Sequences, convergence, Cauchyness, monotonicity, boundedness and closed intervals in an arbitrary ordered field
- Probability measures and probability spaces
- Finite probability spaces, outcome weights, events, and event probabilities
- Adjacency, incidence, open and closed neighbourhoods, vertex degree, minimum degree and maximum degree
- For |r| < 1 the sequence rᵏ is null, and for |r| > 1 the sequence |r|ᵏ diverges to +∞
- The natural numbers ℕ (von Neumann)
- Real random variables on finite probability spaces and their finite distributions
- Expectation of a real random variable on a finite probability space
- The indicator random variable of an event
- Indicators turn event probabilities, intersections, and finite counts into expectations and products
- Expectation is linear for every finite family of random variables, without any independence hypothesis
- Markov's inequality on a finite probability space
- The Binomial count has its usual probability mass function
- The set [A]ᵏ of k-element subsets and the binomial coefficient C(n, k) := | [n]ᵏ|
- C(n, k) k! (n-k)! = n! for k ≤ n; hence C(n, k) k! = n^k̲, the quotient n!/(k!(n-k)!) is a natural number, and C(n, k) = C(n, n-k)
- Random elements and real random variables
- Measures on sigma-algebras
- The principle of mathematical induction
- For |r| < 1, ∑_k ≥ 0 rᵏ = 1/(1-r), and for |r| ≥ 1 the series diverges
- The factorial n! and the falling factorial n^k̲, defined by recursion in ℕ
- The natural logarithm has derivative 1/x and equals the integral from 1 to x of 1/t
- Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm
- If m ≤ f ≤ M on [a,b] then m(b-a) ≤ L(f,P) ≤ ∫ₐᵇ f ≤ ∫ₐᵇ f ≤ U(f,P) ≤ M(b-a) for every partition P; in particular every constant function is integrable, with ∫ₐᵇ c = c(b-a)
- The fundamental theorem of calculus and integration by parts
- Sum, product, quotient, and chain rules from difference quotients
- The natural logarithm as the inverse of the exponential function
- The real exponential function and the number e by a power series
- The exponential addition formula exp(x+y)=exp(x)exp(y)
- The exponential function is strictly increasing
- 1+x≤exp(x) for every real x, hence (1-p)ᵐ≤exp(-mp)
- Integer part: for every real x there is exactly one integer m with m ≤ x < m + 1
- A norm on a real vector space, the induced metric, and the dictionary with the metric axioms
- The vector space M_m × n(F) := F^ m × n of m by n matrices over a field, with entrywise operations
- Rectangular matrix multiplication and the identity matrix Iₙ, including zero-sized shapes
- The adjacency matrix of a finite simple graph
- Standard normal and normal laws
- Independent random elements
- The Axiom of Choice
- Expectation of a nonnegative or integrable random variable
- Change of variables for expectation
- Integrating against a density agrees with integrating the product
- If u,v are differentiable on [a,b] with u',v' integrable, then ∫ₐᵇ u v' = u(b)v(b)-u(a)v(a) - ∫ₐᵇ u'v
- The exponential function is smooth and (exp)'=exp
- The exponential dominates every fixed nonnegative integer power at +∞
- Monotone convergence for the integral
- A bounded Riemann integrable function on a closed bounded interval is Lebesgue measurable and has the same integral
- Expectations factor over finite products of independent random variables
- Finite rectangular matrices over a commutative ring, their entries, rows and columns
- The chain rule, in one line from Carathéodory: if g is differentiable at c and f is differentiable at g(c), then f ∘ g is differentiable at c with (f ∘ g)'(c) = f'(g(c)) g'(c)
- For a natural n ≥ 1 the function x ↦ xⁿ is differentiable everywhere with derivative ι(n) x^ n-1; for n = 0 it is the constant 1, with derivative 0; for a natural n ≥ 1 the function x ↦ x⁻ⁿ is differentiable at every x ≠ 0 with derivative -ι(n) x⁻ⁿ⁻¹; consequently every polynomial function is differentiable at every real, with the derivative computed term by term
- Sums, scalar multiples, products and quotients: (f+g)'(c) = f'(c) + g'(c), (α f)'(c) = α f'(c), (fg)'(c) = f'(c)g(c) + f(c)g'(c), and (f/g)'(c) = (f'(c)g(c) - f(c)g'(c))/g(c)² when g(c) ≠ 0
- Sums, scalar multiples, products, absolute values, maxima, minima and quotients with nonvanishing denominator of continuous functions are continuous, as are constants, the identity and every polynomial function
- A composite of continuous functions is continuous, with no side hypothesis of the kind the composition of limits needs
- Continuous functions on Euclidean spaces are Borel measurable
- A continuous function on [a,b] is Riemann integrable, by Heine-Cantor and Riemann's criterion
- Monotone change of variable for Riemann-integrable functions
2 · Logical flowchart
Arrows show item dependencies. A grouped prerequisite node points to items that use one or more of its members; their exact links are listed above.
3 · Items
Proposition
Single-vertex degree laws and the shared-edge dependence
Definition
Asymptotic quantifiers and uniform parameter ranges
Proposition
Indicator expectations and exceptional-vertex probabilities
Proposition
Binomial mass ratios and geometric tail domination
Proposition
Elementary binomial probability envelopes
Proposition
Floor and ceiling thresholds in logarithmic degree estimates
Proposition
Norm symmetrization at the actual matrix mean
Proposition