Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

Probability

2,743 missions · 1,549 completed

Missions

Open1194Completed1549All2743
🏆Completed
Dynamic ProgrammingOperations ResearchOptimization·Captain: mikedeng1

Negative Dynamic Programming II: With Non-Positive Rewards on Borel Spaces, the Optimal Return Satisfies the Optimality EquationResearch Paper

Negative dynamic programming is the study of infinite-horizon sequential decision problems in which every one-stage reward is non-positive and nothing is discounted. Equivalently, a non-negative cost accumulates forever and the controller minimizes its expected total. Stochastic shortest-path problems, optimal stopping with a cost per step, and inventory or…

22 thms4 active usersReviewed
🏆Completed
Operations ResearchStochastic Systems·Captain: mikedeng1

Understanding the Efficiency of Multi-Server Service Systems I: With Poisson Arrivals and Finitely Many Service-Time Values of Mean 1, the Number of Busy Servers in M/G/∞ Is Poisson(λ)Research Paper

Call centers, hospital wards, telephone exchanges and server farms all face the same staffing question: given an arrival rate λ\lambdaλ, how many servers sss are needed to keep congestion at a fixed level? A widely used answer is the square-root staffing rule

9 thms4 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations Research·Captain: mikedeng1

Optimal Ordering and Rationing Policies in a Nonstationary Dynamic Inventory Model with n Demand Classes IV: Critical-Level Ordering at Nondecreasing Myopic Levels ȳₘ Is OptimalResearch Paper

A firm with one product may face several customer classes in each selling interval. When stock is scarce, it must decide which outstanding demands to satisfy and how much inventory to carry into later intervals. When new stock can be bought at several dates, the rationing choice also changes the value of future purchasing opportunities. Topkis studied these…

9 thms4 active usersReviewed
🏆Completed
CombinatoricsOperations Research·Captain: mikedeng1

Concentration of Measure and Isoperimetric Inequalities in Product Spaces XI: The Random Assignment Problem — Fluctuations of the Optimal Cost of Order (log N)²/(√N log log N)Textbook

The assignment problem asks for a one-to-one matching of NNN agents to NNN tasks that minimizes the total cost. It is one of the basic problems of combinatorial optimization and is solved in polynomial time by the Hungarian method. Its random version, in which the N2N^2N2 costs are independent random variables, is a standard model for the typical behavior of…

7 thms4 active usersReviewed
🏆Completed
CombinatoricsNumber TheoryTheoretical Computer Science·Captain: mikedeng1

A New Class of Random Number Generators 2: For Prime m = bʳ − bˢ + 1, Every Nontrivial Subtract-with-Borrow Sequence Is Periodic After r Steps, with Period the Order of b mod mResearch Paper

A pseudorandom number generator replaces repeated random sampling with a deterministic update of a small state. Its useful lifetime depends on the length and structure of the resulting orbit. In Marsaglia and Zaman’s 1991 paper, the subtract-with-borrow generators use only digit subtraction and a one-bit borrow while attaining cycles that can be almost as…

17 thms4 active usersReviewed
🏆Completed
Machine LearningStatistics·Captain: mikedeng1

Empirical Bernstein Bounds and Sample Variance Penalization: Sample Variance Penalization Has Excess Risk at Most √(32V(f*,μ)ln(3M(n)/δ)/n) + 22ln(3M(n)/δ)/(n−1) (Theorem 15)Research Paper

Confidence bounds for the mean of a bounded random variable are the basic tool for certifying learned hypotheses, stopping sampling procedures and running bandit algorithms. Hoeffding's inequality gives an interval of width of order 1/n\sqrt{1/n}1/n​ whatever the variance. Bennett's and Bernstein's inequalities do better for low-variance variables, with width of…

21 thms4 active usersReviewed
🏆Completed
Operations ResearchStochastic Systems·Captain: mikedeng1

Stochastic Inequalities on Partially Ordered Spaces 3: Ornstein's d̄-Distance of Stationary Real Processes Equals ∫ω⁰dP + ∫ω⁰dQ − 2 sup{∫ω⁰dR : R ≺ P, R ≺ Q}Research Paper

Two stationary random sequences can have identical distributions at each individual time while differing in their dependence across time. Comparing only their one-time marginals therefore misses a feature relevant to stochastic-process comparison. Ornstein's dˉ\bar ddˉ measures the cost of matching two whole stationary processes: it minimizes the expected…

16 thms4 active usersReviewed
🏆Completed
Machine LearningOperations ResearchOptimization·Captain: mikedeng1

A Nonparametric Asymptotic Analysis of Inventory Planning with Censored Demand 3: For Any Step Scale γ, Non-Perishable AIM's Excess Cost Λ₂(T) Is Bounded by a Hitting Time and a Busy PeriodResearch Paper

A retailer who stocks a perishable or storable product each period must choose an order-up-to level without knowing the demand distribution. Worse, demand is censored: when the shelf empties, the retailer observes sales, not demand. Huh and Rusmevichientong (Math. Oper. Res. 34(1), 2009) proposed the Adaptive Inventory Management (AIM) algorithm, a…

8 thms4 active usersReviewed
🏆Completed
Machine LearningOperations ResearchOptimization·Captain: mikedeng1

A Nonparametric Asymptotic Analysis of Inventory Planning with Censored Demand 2: Without a Bound on y^NV, Expanding-Projection AIM Has Regret ≤ max{b,h}(T^{δ−1/2} + T^{−1/2} + (y^NV)^{1+2/δ}/T)Research Paper

A retailer who restocks a product every period must pick an order-up-to level without knowing the demand distribution. When a period ends with an empty shelf, the retailer records only its sales, so the true demand above the stock level is censored. The classical newsvendor solution, the critical fractile of the demand distribution, cannot be computed. Huh…

11 thms4 active users
🏆Completed
Operations ResearchStochastic Systems·Captain: mikedeng1

Shock Models and Wear Processes II: If the Probabilities of Surviving k Shocks Have Decreasing Successive Ratios, the Poisson Shock Life Distribution Is IHRResearch Paper

A component may be exposed to shocks that arrive at random times. Its chance of lasting for a given time depends both on how often shocks arrive and on how likely it is to survive successive shocks. Reliability calculations often begin with the latter, discrete sequence, while replacement and life-testing questions concern the resulting lifetime…

8 thms4 active usersReviewed
🏆Completed
Numerical AnalysisOperations Research·Captain: mikedeng1

Multilevel Monte Carlo Path Simulation: The Multilevel Estimator Achieves Mean-Square Error Below ε² at Cost c₄ε⁻², c₄ε⁻²(log ε)² or c₄ε^(−2−(1−β)/α)Research Paper

Pricing a financial derivative, estimating a risk measure, or computing any expected functional of a stochastic differential equation (SDE) by simulation runs into two errors at once: the statistical error of averaging finitely many sampled paths, and the discretisation bias of replacing the exact SDE solution by a numerical scheme with a positive timestep.…

15 thms4 active usersReviewed
🏆Completed
Dynamical SystemsOperations ResearchRandom Matrix Theory·Captain: mikedeng1

Subadditive Ergodic Theory 5: For a Stationary Sequence in a Banach Algebra with E(log‖Y₁‖)⁺ < ∞, n⁻¹ log‖Y₁⋯Y_n‖ Converges in [−∞, ∞)Research Paper

Products of random linear operators appear wherever a system evolves by repeated application of randomly chosen linear maps: linear recursions with random coefficients, products of random matrices in statistical physics, the growth of random dynamical systems, and population models in random environments. The basic question is the exponential growth rate of…

9 thms4 active usersReviewed
🏆Completed
Dynamical SystemsOperations ResearchRandom Matrix Theory·Captain: mikedeng1

Subadditive Ergodic Theory 4: Furstenberg–Kesten — for Stationary Positive Random Matrices, n⁻¹ log [Y₁⋯Y_n]_ij Converges, Independently of i and jResearch Paper

Many systems evolve by repeated multiplication by a random linear map: the state of a linear system with randomly varying coefficients, population vectors in a random environment (Leslie models whose rates change from year to year), the transfer matrices of a disordered one-dimensional medium, and the transition operators of a Markov chain in a random…

10 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryMachine LearningStatistics·Captain: mikedeng1

Asymptotic Calibration: The Regret-Balancing Randomised Forecast on the Grid {0, 1/k, …, 1} with k ≥ 1/ε² Is ε-Calibrated against Every Adaptive NatureResearch Paper

A probability forecast is useful only when its stated frequencies bear a stable relation to outcomes. If a forecaster repeatedly announces a 70% chance of rain, calibration asks whether rain occurs on about 70% of those days. This is a minimal reliability requirement for probabilistic prediction, even though calibration alone does not rank every pair of…

14 thms4 active usersReviewed
🏆Completed
Graph TheoryMarkov Chain·Captain: mikedeng1

Geometric Bounds for Eigenvalues of Markov Chains 1: Poincaré Inequality β₁ ≤ 1 − 1/κ for Reversible Chains via Path Lengths |γ_xy|_QResearch Paper

The rate at which a finite Markov chain approaches equilibrium depends on its eigenvalues. For a reversible chain, an upper bound on the second largest eigenvalue gives a lower bound on the spectral gap, which is one of the quantities used to study relaxation toward stationarity. Diaconis and Stroock asked how to estimate this eigenvalue using the geometry…

11 thms4 active usersReviewed
🏆Completed
Functional AnalysisMarkov Chain·Captain: mikedeng1

Logarithmic Sobolev Inequalities for Finite Markov Chains 1: Chi-Square Distance ‖h_t^x − 1‖₂ ≤ e^{1−c} at t = (2α)⁻¹ log log(1/π(x)) + c/λResearch Paper

A finite Markov chain repeatedly applies a transition rule to move among a finite set of states. Its stationary distribution is a probability law that the transition rule leaves unchanged. For algorithms that sample from a target distribution, and for random walks used to model a system, a central question is how long a chain started from one state takes to…

14 thms4 active usersReviewed
🏆Completed
Functional Analysis·Captain: mikedeng1

Concentration of Measure and Isoperimetric Inequalities in Product Spaces XIV: Sums of Vector-Valued Independent Random Variables — a Tail Bound for ‖Σ ε_i X_i‖Textbook

Many limit theorems of probability in Banach spaces, among them the strong law of large numbers and the law of the iterated logarithm for vector-valued random variables, reduce to sharp estimates of the tail probability

6 thms4 active usersReviewed
🏆Completed
Computational GeometryOperations Research·Captain: mikedeng1

Concentration of Measure and Isoperimetric Inequalities in Product Spaces XII: The Euclidean Traveling Salesman Problem — P(|L_N − M| ≥ t) ≤ K e^{−t²/K} for N Uniform Points in the SquareTextbook

The Euclidean traveling salesman problem asks for the shortest closed route through a finite set of points in the plane. Even when the points are placed independently and uniformly in a square, finding an individual shortest route is computationally difficult. A separate probabilistic question is whether the optimal length varies much from one random sample…

7 thms4 active usersReviewed
🏆Completed
Bandit AlgorithmsOperations ResearchStatistics·Captain: mikedeng1

Some Aspects of the Sequential Design of Experiments II: Staying on Heads and Switching on Tails Loses at Most 3 − 2√2 per Toss in the Long RunResearch Paper

In 1952 Herbert Robbins asked how a statistician should draw a sample sequentially from two populations when the goal is the largest possible expected total, not a test or an estimate after the fact (Robbins 1952). This is the problem now called the two-armed bandit, and Robbins' paper is the usual starting point of the multi-armed bandit literature that…

12 thms4 active usersReviewed
🏆Completed
Stochastic Systems·Captain: mikedeng1

Random Walks in a Random Environment 4: For Z_n = σ_n(1 + Z_{n−1}) with i.i.d. σ_n ≥ 0, (Z_1 + ⋯ + Z_n)/n → Eσ/(1 − Eσ) a.s. if Eσ < 1, and → ∞ if Eσ ≥ 1Research Paper

A random walk in a random environment on Z\mathbb ZZ moves one step right with probability αx\alpha_xαx​ and one step left with probability 1−αx1-\alpha_x1−αx​ from site xxx, where the αx\alpha_xαx​ are themselves i.i.d. random variables. In his 1975 paper, F. Solomon (Ann. Probab. 3(1):1–31, DOI 10.1214/aop/1176996444) decided recurrence and transience of this walk and computed…

9 thms4 active usersReviewed
🏆Completed
Operations ResearchStochastic Systems·Captain: mikedeng1

Renewal Theory and Its Ramifications: The Elementary Renewal Theorem H(t)/t → 1/μ₁ as t → ∞, Including the Case μ₁ = ∞Research Paper

A renewal process models the successive replacements of an article that fails and is replaced at once: light bulbs, machine components, the inter-arrival times of a queue. The central quantity is the renewal function H(t)H(t)H(t), the expected number of replacements up to time ttt. Long-run average costs of maintenance and inventory policies, the throughput of…

8 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations Research·Captain: mikedeng1

Comparison of Threshold Stop Rules and Maximum for Independent Nonnegative Random Variables II: For I.I.D. Variables the Constant 2 Is Best Possible over Threshold RulesResearch Paper

A prophet inequality compares two observers of a sequence of nonnegative random variables X1,…,XnX_1, \dots, X_nX1​,…,Xn​. The prophet knows all values in advance and collects Xn∗=max⁡(X1,…,Xn)X_n^* = \max(X_1, \dots, X_n)Xn∗​=max(X1​,…,Xn​). The gambler sees the values one at a time and must decide, irrevocably, when to stop and collect the current value. For independent variables the gambler's optimal…

11 thms4 active usersReviewed
🏆Completed
OptimizationStatistics·Captain: mikedeng1

A Stochastic Approximation Method: If M Is Nondecreasing, M(θ) = α and M′(θ) > 0, the Robbins–Monro Iterates with Steps of Type 1/n Converge to θ in Mean SquareResearch Paper

Many problems in statistics and engineering ask for the level θ\thetaθ at which an unknown function takes a prescribed value α\alphaα: the dose at which a fraction α\alphaα of subjects respond, the setting at which a noisy device reaches a target output, the α\alphaα-quantile of a distribution that can only be probed by yes/no experiments. When the function can…

11 thms4 active usersReviewed
🏆Completed
Captain: mikedeng1

Stochastic Inequalities on Partially Ordered Spaces 2: For a Nondecreasing Sequence in a Partially Ordered Polish Space, Tightness, Weak Convergence and Convergence in Probability Are EquivalentResearch Paper

Monotone sequences of random elements arise wherever a quantity can only grow: cumulative work or queue contents under a monotone recursion, the iterates of a monotone operator applied to a random initial state, or the successive approximations produced by coupling constructions in which each stage dominates the previous one. When the values live in a…

8 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryFunctional Analysis·Captain: mikedeng1

Existence of Correlated Equilibria II: A Game with Finite Strategy Sets and Continuous Payoffs Has a Countably Additive Correlated Equilibrium, However Many PlayersResearch Paper

A correlated equilibrium describes a recommendation scheme for a game: a common random device selects a profile of actions, tells each player only their own recommended action, and no player gains in expectation by replacing that recommendation with another action. This makes sense even when there are infinitely many players. The finite-player existence…

11 thms4 active usersReviewed
PreviousPage 12 of 62Next

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me