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
Operations ResearchStatisticsStochastic Systems·Captain: Shuze Chen

The Markov Chain Central Limit TheoremResearch Paper

Markov chain Monte Carlo turns hard integration problems into long simulations: to estimate an expectation EπfE_\pi fEπ​f one runs a Markov chain with stationary distribution π\piπ and reports the sample average fˉn\bar f_nfˉ​n​. The ergodic theorem guarantees fˉn→Eπf\bar f_n \to E_\pi ffˉ​n​→Eπ​f, but honest error bars require more: a central limit theorem

154 thms18 active usersReviewed
🏆Completed
AnalysisStochastic Systems·Captain: WillR

Foundations of Lévy Processes: Construction, Fluctuation Theory and Stochastic ControlTextbook

A real-valued Lévy process describes random evolution with stationary and independent increments. Brownian motion, compound-Poisson risk models and infinite-activity jump processes belong to this class. Their analytical theory is a foundation for insurance risk, mathematical finance and stochastic control. Lévy–Khintchine representation and the construction…

2,360 thms12 active usersReviewed
🏆Completed
Machine Learning·Captain: mikedeng1

Privacy for Free in Efficient Agnostic Halfspace LearningResearch Paper

A classifier trained on individual records can reveal information about those records through its output. Differential privacy bounds how much the output distribution changes when one labeled example is replaced. For halfspace learning, the statistical question is whether this protection requires substantially more examples than learning without privacy.…

33 thms9 active usersReviewed
🏆Completed
Machine LearningOperations ResearchOptimization·Captain: mikedeng1

A Nonparametric Asymptotic Analysis of Inventory Planning with Censored Demand 1: AIM's Average Expected Cost Is Within O(1/√T) of the Newsvendor Cost, Perishable and Non-PerishableResearch Paper

A retailer who restocks a product every period must choose an order-up-to level without knowing the demand distribution, and in most retail settings it observes only sales, the minimum of demand and stock. Demand above the stock is lost and never recorded. This is censored demand: the data needed to estimate the distribution are truncated exactly at the…

17 thms8 active usersReviewed
🏆Completed
Functional AnalysisGraph TheoryRandom Matrix Theory·Captain: dbenbenn

A new approach to strong convergence (Chen–Garza-Vargas–Tropp–van Handel 2026)Research Paper

This mission formalizes C.-F. Chen, J. Garza-Vargas, J. A. Tropp and R. van Handel, A new approach to strong convergence, Ann. of Math. (2) 203 (2026) 555–602, doi:10.4007/annals.2026.203.2.4 (arXiv:2405.16026v3, whose page numbers are used).

103 thms7 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchStochastic Systems·Captain: Shuze Chen

Stochastic Networks XVI: The Stability Region of Alpha-Fair Flow AllocationsTextbook

Bandwidth allocation determines how quickly a network transfers each file, but files also arrive and depart while the network operates. An allocation can be feasible at every instant and still allow the number of unfinished files to grow without an equilibrium. The relevant question is therefore about the interaction of the allocation rule with the changing…

15 thms7 active usersReviewed
🏆Completed
Machine LearningStatisticsTheoretical Computer Science·Captain: mikedeng1

Foundations of Machine Learning VII: On-Line Learning and On-Line-to-Batch ConversionTextbook

Every guarantee in the preceding chapters assumes a fixed distribution and i.i.d. sampling. On-line learning drops both assumptions: an algorithm processes one example at a time, in an adversarial (worst-case) sequence, and is judged by regret against the best fixed comparator in hindsight rather than by generalization error. This chapter develops the…

28 thms7 active users
🏆Completed
Machine LearningRandom Matrix TheoryStatistics·Captain: mikedeng1

High-Dimensional Probability IX: The Matrix Deviation InequalityTextbook

Random matrices with independent rows are the workhorse of high-dimensional statistics and compressed sensing: sample covariance matrices, sub-sampled measurement operators, and randomized sketches are all of this form. A basic question about such a matrix AAA is how close ∥Ax∥2\|Ax\|_2∥Ax∥2​ stays to its typical size E∥Ax∥2≈m∥x∥2\mathbb E\|Ax\|_2\approx\sqrt m\|x\|_2E∥Ax∥2​≈m​∥x∥2​ — not just…

13 thms7 active users
🏆Completed
Mathematical PhysicsQuantum Information·Captain: mikedeng1

Fast mixing of the SYK model at high temperaturesResearch Paper

A Gibbs state describes thermal equilibrium, but specifying its matrix does not provide an efficient procedure for preparing it. For quantum algorithms, the useful guarantee is convergence from every initial state in a distance that controls arbitrary measurements. Agreement of a few local observables is insufficient for this purpose. The Sachdev–Ye–Kitaev…

33 thms6 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations Research·Captain: mikedeng1

Best-of-Many-Worlds MMS Allocation for Chores with Sublinear DisposalsResearch Paper

Dividing undesirable tasks gives a cost to every recipient. A person asked to divide all tasks into equal shares may still be unable to find a share she considers acceptable once other people's preferences must also be respected. This tension matters in fair division: a benchmark based only on each person's own costs need not be simultaneously achievable by…

28 thms6 active usersReviewed
🏆Completed
CombinatoricsOperations Research·Captain: Shuze Chen

Online Matching with Stochastic Rewards: Optimal Competitive Ratio via Path-Based Formulation: Optimal competitiveness of generalized perturbed greedyResearch Paper

An allocation decision does not always produce a reward. An advertisement may receive no click, or a recommended product may not be purchased. In online matching with stochastic rewards, a failed offer uses the customer's opportunity but leaves the resource available for a later customer. This distinction changes both the algorithm and the benchmark against…

24 thms6 active usersReviewed
🏆Completed
Operations ResearchOptimal TransportOptimization·Captain: Shuze Chen

Technical Note—Data-Driven Chance Constrained Programs over Wasserstein Balls: Exact deterministic reformulation of chance constraintsResearch Paper

A decision can be inexpensive on average yet fail too often to be acceptable. A chance constraint addresses this by bounding the probability of an unsafe outcome. When the distribution of uncertainty is itself unknown, enforcing the constraint only under observed frequencies can overlook outcomes absent from the data. A distributionally robust chance…

16 thms6 active usersReviewed
🏆Completed
EconomicsOperations Research·Captain: mikedeng1

Capability Building in Sluggish Organizations: Under Myopic Adjustment the Lowest Long-Run Capability Is at Most 2μ − 1, Attained by a Perturbed Rest/High-Intensity CycleResearch Paper

Organizations, athletes and students build capability gradually: a team can raise or lower its skill level only a little from one period to the next, while the demands placed on it can change abruptly. A trainer (a coach, a manager, a curriculum designer) who controls the sequence of demands, subject to a budget on their average intensity, wants to know…

13 thms6 active usersReviewed
🏆Completed
Bandit AlgorithmsMachine LearningOperations Research·Captain: mikedeng1

Dynamic Pricing with Unknown Non-Parametric Demand and Limited Price Changes: The SLPE Policy Has Regret O(√T log T log log T) on Its Concentration Event and Makes O(log log T) Price ChangesResearch Paper

A retailer selling one product over TTT periods must choose a price each period without knowing how demand responds to price. Charging different prices reveals the demand curve but costs revenue, and in practice every price change has its own cost: relabelling, customer goodwill, contractual limits on repricing. Dynamic pricing with learning asks for policies…

10 thms6 active usersReviewed
🏆Completed
Operations ResearchOptimizationStochastic Systems·Captain: Shuze Chen

Stochastic Networks XI: Gaussian Limits for Large Loss NetworksTextbook

A loss network accepts a request only when all resources needed by that request are available. An accepted telephone call, for example, occupies circuits on several links at once. A blocked request leaves immediately. Resource sharing makes route occupancies dependent, even when the arrival streams are independent. For a large network, its exact equilibrium…

15 thms6 active usersReviewed
🏆Completed
Quantum InformationTheoretical Computer Science·Captain: mikedeng1

Simulating quantum computers with probabilistic methods: a circuit on a computationally tractable state is classically simulable by sampling when U†OU is sparseResearch Paper

A quantum circuit may create a state whose full list of amplitudes is far too large for a classical computer to store. That fact alone does not show that every observable feature of its output is hard to estimate. In Simulating quantum computers with probabilistic methods, Van den Nest asks when classical sampling can reproduce the accuracy of a quantum…

12 thms6 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: Shuze Chen

Interior Point Algorithms VIII: The Semidefinite Relaxation Bounds Quadratic Programs within π/2Textbook

Many problems in combinatorial optimization, control and signal processing reduce to minimizing a nonconvex quadratic form over a box. Max-cut and other boolean quadratic programs are special cases. Computing the global minimum of such a program is NP-hard in general, so the practical question is how well a tractable convex problem can bound it. The semidefi…

16 thms6 active usersReviewed
🏆Completed
Experimental DesignOperations ResearchStatistics·Captain: mikedeng1

Pigeonhole Design: Balancing Sequential Experiments from an Online Matching Perspective 2: Every Pigeonhole Design on [0,1] Has Worst-Case Expected Discrepancy Ω(T^(1/4))Research Paper

Online platforms run experiments on subjects that arrive one at a time: a user opens an app, a customer reaches a checkout page, a patient enters a trial. Each subject must be assigned to control or treatment at once, before the next one arrives, and the quality of the final estimate depends on how well the two groups resemble each other in their observed…

14 thms6 active users
🏆Completed
Bandit AlgorithmsMachine LearningOperations Research+1·Captain: mikedeng1

Learning and Optimization with Seasonal Patterns 2: Regret Lower Bound for Periodic Multi-Armed Bandits with Known PeriodsResearch Paper

Demand, prices and click-through rates often follow seasonal cycles: weekly, monthly, yearly. A decision maker who repeatedly chooses among options whose expected payoffs repeat in time faces a non-stationary multi-armed bandit. Chen, Wang and Wang (arXiv:2005.08088v4, Operations Research, 2025) study the model in which each arm's mean reward is periodic…

15 thms6 active usersReviewed
🏆Completed
Information TheoryOptimizationStatistics·Captain: mikedeng1

Distributionally Robust Optimization: A Review: Variation²/4 ≤ Hellinger ≤ Kullback–Leibler ≤ J-Divergence, so the J, KL and Hellinger Balls of Radius ε Lie in the Variation Ball of Radius 2√εResearch Paper

Distributionally robust optimization evaluates a decision against a set of plausible probability laws rather than against a single estimated law. A common way to specify that set is to choose a nominal law P0P_0P0​ and allow every law PPP whose discrepancy from P0P_0P0​ is below a radius ε\varepsilonε. Different discrepancies produce different ambiguity sets, so…

10 thms6 active usersReviewed
🏆Completed
Complexity TheoryLinear algebraTheoretical Computer Science·Captain: mikedeng1

Candidate Indistinguishability Obfuscation and Functional Encryption for All Circuits: Garblings of Equivalent Partial Assignments Are O(nT²/p)-Close in the Generic Colored Matrix ModelResearch Paper

An indistinguishability obfuscator (iO) is a compiler that scrambles a program so that any two programs computing the same function become computationally indistinguishable after compilation. Garg, Gentry, Halevi, Raykova, Sahai and Waters gave the first candidate construction for all circuits (SIAM J. Comput. 45(3), 2016; conference version FOCS 2013). The…

12 thms6 active usersReviewed
🏆Completed
Bandit AlgorithmsMachine LearningReinforcement Learning·Captain: mikedeng1

Provably Efficient Reinforcement Learning with Linear Function Approximation 2: LSVI-UCB Has Regret O(√(d³H³Tι²) + ζdHT√ι) on ζ-Approximately Linear MDPsResearch Paper

Reinforcement learning with large or continuous state spaces relies on function approximation: value functions are represented as functions of a ddd-dimensional feature map instead of tables indexed by states. Before 2019, regret guarantees for exploration with function approximation either needed strong assumptions (deterministic dynamics, a generative…

17 thms6 active usersReviewed
🏆Completed
Machine LearningOperations ResearchOptimization·Captain: mikedeng1

Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic Programming 3: The Two-Phase RSG Method Finds an (ε, Λ)-Solution within S(Λ)[N(ε) + T(ε, Λ)] Oracle CallsResearch Paper

Stochastic optimization methods often see only noisy gradients. For a nonconvex objective, a useful guarantee is that an output point has a small gradient: this is a first-order stationarity certificate, even when there is no claim that the point is globally optimal. A guarantee on the expected squared gradient leaves open how often one particular run…

14 thms6 active users
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Consumer Returns Policies and Supply Chain Performance 1: With Valuations Learned after Purchase, the Seller's Optimal Policy Is p* = E max(V, s), F̄(q*) = (c − s)/(p* − s), r* = sResearch Paper

Retailers accept large volumes of returned merchandise, and a common default is the full refund: a buyer who is unhappy with a product brings it back and gets the whole price back. Many consumers only learn how much they value a product after they have it at home — clothes that do not fit, a gadget that does not suit the buyer's needs. A returns policy…

15 thms6 active users
🏆Completed
Algorithmic Game TheoryOperations Research·Captain: mikedeng1

Worst-Case Equilibria II: On Two Links with Speeds s₁ ≤ s₂ ≤ φs₁ Some Nash Equilibrium Has Expected Makespan 1 + s₂/(s₁ + s₂) Times the Optimum, Reaching φ at s₂ = φs₁Research Paper

When many independent users share a network, each routes its own traffic to minimize its own delay, and nobody optimizes the system as a whole. Koutsoupias and Papadimitriou asked how much this lack of coordination can cost: how far the social cost of a Nash equilibrium can be from the social optimum, in the worst case. Their paper Worst-case equilibria (STA…

11 thms6 active usersReviewed
PreviousPage 1 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