Random structures and processes where conjectured constants and thresholds can be tested numerically and partial results proved step by step.
Let λ_n,2 be the random variable assigning two uniformly random binary strings of length n the length of their longest common subsequence. Then C_31a is the (well-defined) limit C_31a := lim_n → inftyE[λ_n,2]/n.
The constant term of one-shot channel simulation [HJMR07], [BG14], [LEG18], [Li25] is given as (we use the definition in [Li25]) C_32=limsup_t→∞(sup_p_X,Y: I(X;Y)=t inf_p_S|X,Y: I(X;S)=0H(Y|S)-t-log_2t), where H(Ylvert S)=H(Y,S)-H(S) is the conditional entropy (in bits), and I(X;Y)=H(X)+H(Y)-H(X,Y)…
Let G = (g_ij) be an M × N random matrix with independent standard Gaussian entries, and let Z(G) := | σ ∈ -1,1^N : G σ ≥ 0 coordinatewise |. This is the zero-margin binary (or Ising) perceptron. Write M = ⌊ α N ⌋. Define C_80 to be the infimum of all α > 0 such that ℙ(Z(G) > 0) → 0 as N → ∞.
Let X be an integrable real random variable. We say that X is 1-sub-Gaussian in the tail sense if E[X]=0 quadand ℙ(lvert Xrvert>t)≤ 2e^-t^2/2quadfor all t≥ 0.
Let ℤ^2 denote the square lattice graph with vertex set ℤ^2 and edges between nearest neighbors (Euclidean distance 1). A self-avoiding walk (SAW) on a graph G=(V,E) is a walk that visits no vertex more than once.
C_12 = β_2 is the constant such that the length L_n of the shortest tour through n independent uniform random points satisfies L_n/√(n)→ β_2 almost surely.
Let X_1,X_2,… be i.i.d. real random variables with E X_1 = 0, Var(X_1)=1, and finite third absolute moment β_3 := E|X_1|^3 < ∞. Let S_n := X_1+⋯+X_n/sqrt n, F_n(x):=ℙ(S_n≤ x), and let Φ denote the standard normal distribution function.
Let μ be a Borel probability measure on ℝ^n with finite second moments. Its covariance matrix is Cov(μ) :=\ ∫_ℝ^n (x-m)(x-m)^mathsf T dμ(x), m:=∫_ℝ^n x dμ(x). ### Convex bodies If K⊂ℝ^n is a convex body, let λ_K be the uniform probability measure on K and abbreviate Cov(K):=Cov(λ_K).
C_20c is the KLS constant (Kannan–Lovász–Simonovits constant) for log-concave measures. It is defined as C_20c := sup_n≥ 1 ψ_n, where ψ_n is the worst-case inverse Cheeger (isoperimetric) constant among isotropic log-concave probability measures on ℝ^n.
Let X be a random vector in ℝ^n with an isotropic log-concave distribution (i.e. X has a log-concave density, E X=0, and Cov(X)=Id). Since X is isotropic, E|X|^2 = n.
Suppose that X, Y are two finitely-supported independent random variables taking integer values, and such that X + Y is uniformly distributed on its range. Are X and Y themselves uniformly distributed on their ranges?
Everything is published under CC BY 4.0 with authorship recorded. How it works
