Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

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

Probability

2,744 missions · 1,568 completed

Missions

Open1176Completed1568All2744
🏆Completed
Algorithmic Game TheoryOperations ResearchTheoretical Computer Science·Captain: mikedeng1

Secretary Problems: Weights and Discounts 1: An (8+3e)-Competitive Algorithm for the Weighted Secretary ProblemResearch Paper

The classical secretary problem asks how to select one valuable candidate when candidates arrive in random order and a decision must be made when each candidate appears. Many allocation settings have several goods of unequal quality instead of a single position. An employer may have roles of different desirability, or a seller may have placements with…

7 thms2 active usersReviewed
🏆Completed
Statistics·Captain: mikedeng1

Weighted Sums of Certain Dependent Random Variables 3: Reversed Weighted Sums of Bounded Martingale Differences Obey a Strong LawResearch Paper

A martingale difference sequence is the standard model of a "fair" sequence of observations whose terms may depend on the past: each new term has conditional mean zero given everything observed before it. Laws of large numbers for such sequences underlie the analysis of stochastic approximation, sequential estimation and online learning, where the noise…

8 thms2 active usersReviewed
🏆Completed
Operations Research·Captain: mikedeng1

Conditional Logit Analysis of Qualitative Choice Behavior 1: Independence of Irrelevant Alternatives with a Universal Benchmark Yields Logit Selection ProbabilitiesResearch Paper

The conditional logit model is the workhorse of discrete choice analysis: it is used to forecast travel mode shares, to estimate demand for differentiated products, and, in operations research, as the multinomial logit (MNL) choice model behind assortment optimization and revenue management. Its selection probabilities have the form …

7 thms2 active usersReviewed
🏆Completed
Statistics·Captain: mikedeng1

Weighted Sums of Certain Dependent Random Variables 1: Weighted Sums of Bounded Multiplicative Systems Grow at Most Like √(2Bₙ² log n)Research Paper

Weighted sums of dependent random variables occur when the weights change with the observation horizon. Even if each random variable is bounded and centered, allowing the weights in row nnn to be chosen anew makes an almost-sure statement about all large nnn different from a bound on a single finite sum. Kazuo Azuma's 1967 paper treats this situation under a…

7 thms2 active usersReviewed
🏆Completed
Machine LearningReinforcement Learning·Captain: mikedeng1

Minimax Regret Bounds for Reinforcement Learning II: High-Probability Regret Bound for UCBVI with a Bernstein–Freedman BonusResearch Paper

An agent can learn to act in an unknown environment by repeatedly running a finite episode, observing the states reached after its actions, and updating its model of the environment. The agent must trade off rewards in the current episode against information that may improve later decisions. A regret bound measures the cumulative value lost relative to an…

13 thms2 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization+1·Captain: mikedeng1

Smoothed Analysis of Algorithms: Why the Simplex Algorithm Usually Takes Polynomial Time 2: The Two-Phase Shadow-Vertex Simplex Method Has Polynomial Smoothed ComplexityResearch Paper

The simplex method solves linear programs by moving between vertices of a feasible polyhedron. Its worst-case number of moves can grow exponentially, yet it often performs well on ordinary inputs. Worst-case examples alone therefore give an incomplete account of the method’s behavior. Spielman and Teng introduced smoothed analysis to measure expected…

22 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimizationStatistics·Captain: mikedeng1

Asymptotic Behavior of Statistical Estimators and of Optimal Solutions of Stochastic Optimization Problems: Optimal Solutions Under Estimated Distributions Are Strongly ConsistentResearch Paper

Many estimation procedures in statistics, and most stochastic optimization models in operations research, have the same shape: a decision or parameter x∈Rnx\in\mathbb R^nx∈Rn is chosen to minimize an expected loss Ef(x)=∫f(x,ξ) P(dξ)Ef(x)=\int f(x,\xi)\,P(d\xi)Ef(x)=∫f(x,ξ)P(dξ) under a distribution PPP that is not known. In practice PPP is replaced by an estimate PνP^\nuPν built from the information…

13 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryMechanism DesignOperations Research·Captain: mikedeng1

Multi-parameter Mechanism Design and Sequential Posted Pricing 4: A 6.75-Approximate Truthful Posted-Price Menu for Unit-Demand Buyers of Multiple ItemsResearch Paper

A hotel sells rooms of several types, in limited numbers, to guests who each want one room. The revenue-optimal way to sell is known only in special cases: for buyers with several private values, optimal mechanisms can be randomized, involve lotteries, and lack a closed form (Manelli–Vincent 2007; Chawla, Hartline, Kleinberg 2007). In practice sellers post…

15 thms2 active usersReviewed
🏆Completed
Machine LearningOptimizationStatistics·Captain: mikedeng1

Variance-based Regularization with Convex Objectives I: The χ²-Robust Risk Equals Empirical Risk plus a Standard-Deviation PenaltyResearch Paper

Many statistical procedures minimize an average observed loss. This treats two candidates with the same average as equally attractive even when one has much more variable losses across the sample. Adding a multiple of the empirical standard deviation can distinguish them, but the resulting objective need not be convex even when each individual loss is…

8 thms2 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchOptimization·Captain: mikedeng1

Optimal Policies for a Multi-Echelon Inventory Problem: The Two-Echelon Optimal Cost Splits into the Isolated Installation-1 Cost Plus a Function of Echelon StockResearch Paper

Most physical supply chains hold stock at several levels: a factory warehouse feeds a regional depot, which feeds a retail outlet. Each level orders from the one above it, and a shortage upstream delays replenishment downstream. Optimizing such a multi-echelon system by dynamic programming looks hopeless, because the state is a vector of stock levels and…

8 thms2 active usersReviewed
🏆Completed
Machine LearningStatistics·Captain: mikedeng1

Certified Adversarial Robustness via Randomized Smoothing 1: The Gaussian-Smoothed Classifier Is Constant on the ℓ2 Ball of Radius (σ/2)(Φ⁻¹(p_A) − Φ⁻¹(p_B))Research Paper

Classifiers trained on images, speech and text can be made to change their prediction by perturbations of the input that are tiny in norm (Szegedy et al., 2014). Empirical defences against such adversarial examples have repeatedly been broken by stronger attacks (Athalye, Carlini, Wagner, 2018), which motivates certified defences: classifiers that come with…

15 thms2 active usersReviewed
🏆Completed
Machine LearningStatistics·Captain: mikedeng1

Stability and Generalization 1: Polynomial Generalization Bounds from Hypothesis Stability for the Empirical and Leave-One-Out ErrorsResearch Paper

A learning algorithm is judged by its generalization error, its expected loss on a fresh example, which cannot be computed because the data distribution is unknown. Practitioners estimate it either by the empirical error on the training set or by the leave-one-out error, which retrains the algorithm once per example. Classical learning theory justifies…

13 thms2 active usersReviewed
Control TheoryOperations ResearchStochastic Systems·Captain: mikedeng1

Dynamic Scheduling of a System with Two Parallel Servers in Heavy Traffic with Resource Pooling: The Threshold Policy Is Asymptotically OptimalResearch Paper

Many service systems route several classes of work to servers with overlapping skills: call centers with cross-trained agents, manufacturing cells with flexible machines, computing clusters with heterogeneous processors. Choosing which server works on which class at each moment is a dynamic scheduling problem. Exact optimal policies are out of reach except…

14 thms2 active usersReviewed
🏆Completed
Dynamical SystemsOperations ResearchStochastic Systems·Captain: mikedeng1

Dynamics of Stochastic Approximation Algorithms 7: Weak Limit Points of the Occupation Measures of a Weak Asymptotic Pseudotrajectory Are InvariantResearch Paper

Stochastic approximation algorithms are recursions xn+1−xn=γn+1(F(xn)+Un+1)x_{n+1}-x_n=\gamma_{n+1}(F(x_n)+U_{n+1})xn+1​−xn​=γn+1​(F(xn​)+Un+1​) driven by small steps γn\gamma_nγn​ and noise Un+1U_{n+1}Un+1​; they include the Robbins–Monro scheme, stochastic gradient methods and learning dynamics in games. The ODE method studies their long-run behaviour by comparing a time-interpolation of the iterates with the…

10 thms2 active usersReviewed
🏆Completed
Machine LearningStatistics·Captain: mikedeng1

The Sample Complexity of Pattern Classification with Neural Networks: The Size of the Weights is More Important than the Size of the Network I: Fat-Shattering Margin Bound with d = fat_H(γ/16)Research Paper

Classical generalization bounds for classifiers, built on the VC dimension, grow with the number of adjustable parameters. For neural networks this is at odds with practice: networks with many more weights than training examples often generalize well. Bartlett's 1998 paper (IEEE Trans. Inform. Theory 44(2), 525–536) explains part of this by measuring a…

12 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Air Travel Demand and Airline Seat Inventory Management III: Gaussian EMSR Protection Levels and Their SensitivityTextbook

An airline sells the seats of one flight leg in several fare classes at different prices. Low-fare passengers usually book first, so the airline must decide how many seats to keep back, or protect, for later high-fare passengers. Peter Belobaba's 1987 MIT dissertation introduced the expected marginal seat revenue (EMSR) rule for this decision, and EMSR-type…

9 thms2 active usersReviewed
🏆Completed
Machine LearningReinforcement Learning·Captain: mikedeng1

Minimax Regret Bounds for Reinforcement Learning I: High-Probability Regret Bound for UCBVI with a Chernoff–Hoeffding BonusResearch Paper

An agent learning to control an unknown environment must balance rewards it can collect now against information that improves later decisions. In a finite Markov decision process (MDP), every action changes the distribution of the next state, so a mistaken transition estimate can affect decisions many steps later. Regret measures this loss against a policy…

9 thms2 active usersReviewed
🏆Completed
Operations ResearchTheoretical Computer Science·Captain: mikedeng1

Secretary Problems: Weights and Discounts 4: A Threshold Rule Earns Z/4 for Any Z ≤ E[OPT] in the Discounted Secretary ProblemResearch Paper

In the classical secretary problem a decision maker sees nnn candidates in a uniformly random order and must accept or reject each one on arrival, irrevocably, aiming to accept a valuable one. Its online, random-order structure models hiring, selling an item to sequentially arriving buyers, and posting prices in online markets. Babaioff, Dinitz, Gupta,…

6 thms2 active usersReviewed
🏆Completed
Operations ResearchTheoretical Computer Science·Captain: mikedeng1

Secretary Problems: Weights and Discounts 2: An Ω(log n / log log n) Lower Bound on the Competitive Ratio of the Discounted Secretary ProblemResearch Paper

In the classical secretary problem a decision maker sees nnn candidates in uniformly random order, learns each candidate's value on arrival, and must accept or reject it on the spot; the goal is to pick a valuable one. A simple sample-then-select rule picks the best candidate with probability at least 1/e1/e1/e, so the problem is constant-competitive. The secretary…

7 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations Research·Captain: mikedeng1

Correlated Equilibrium as an Expression of Bayesian Rationality II: Two-Person Correlated Equilibrium Distributions Are the Solutions of Linear InequalitiesResearch Paper

A correlated equilibrium is the equilibrium notion that arises when the players of a game take their actions on the advice of a common randomizing device, each player seeing only his own recommendation. It was introduced by Aumann in 1974 (Aumann 1974). Aumann's 1987 paper (Aumann 1987) gives the simple, finite form of the definition used today (Definition…

6 thms2 active usersReviewed
🏆Completed
Mathematical Physics·Captain: mikedeng1

The Intermediate Disorder Regime for Directed Polymers in Dimension 1+1: The Rescaled Partition Function Converges in Law to a Wiener ChaosResearch Paper

A directed polymer in a random environment is a simple random walk whose paths are reweighted by a random field of energies. It is a basic model of disordered statistical mechanics, and in dimension 1+11+11+1 it belongs to the Kardar–Parisi–Zhang (KPZ) universality class: at fixed temperature the free energy fluctuates on the scale n1/3n^{1/3}n1/3 and is expected to…

13 thms2 active usersReviewed
Mathematical PhysicsOptimizationPartial Differential Equations·Captain: mikedeng1

Optimization of Mean-field Spin Glasses I: Every Minimizer of the Extended Parisi Functional Has Full SupportResearch Paper

The Ising mixed ppp-spin model assigns to each configuration σ∈{−1,+1}N\sigma \in \{-1,+1\}^Nσ∈{−1,+1}N the energy of a random polynomial whose covariance is E{HN(σ)HN(σ′)}=Nξ(⟨σ,σ′⟩/N)\mathbb E\{H_N(\sigma)H_N(\sigma')\} = N\xi(\langle\sigma,\sigma'\rangle/N)E{HN​(σ)HN​(σ′)}=Nξ(⟨σ,σ′⟩/N). Its ground-state energy max⁡σHN(σ)/N\max_\sigma H_N(\sigma)/Nmaxσ​HN​(σ)/N converges to the value of a variational problem, the zero-temperature Parisi formula (Auffinger–C…

22 thms2 active usersReviewed
🏆Completed
Markov ChainNumerical AnalysisOperations Research+1·Captain: mikedeng1

Fundamentals of Queueing Theory X: Uniformization of Continuous-Time Markov ChainsTextbook

Most Markovian queueing models have no closed-form transient solution. The M/M/1 queue already needs modified Bessel functions (Chapter 2 of the book), and a finite-capacity or multi-class model with state-dependent rates has no closed form at all. What an analyst can always write down is the system of forward equations p′(t)=p(t)Qp'(t)=p(t)Qp′(t)=p(t)Q for the state…

8 thms2 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: mikedeng1

A Randomized Linear Programming Method for Computing Network Bid Prices II: Directional Derivatives of Expected Perfect-Information Revenue Are Expected LP ValuesResearch Paper

Airlines, hotels and railways sell a fixed stock of capacity on several resources at once: a passenger flying from Boston to Los Angeles through Chicago uses a seat on two flight legs. Network revenue management decides which requests to accept, and the standard control is a bid price per leg: accept an itinerary if its fare exceeds the sum of the bid…

8 thms2 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: mikedeng1

A Randomized Linear Programming Method for Computing Network Bid Prices I: Averaged LP Dual Prices Are an Unbiased Estimate of the Gradient of Expected Perfect-Information RevenueResearch Paper

Airlines, hotels and railways sell fixed capacity on networks of resources. In network revenue management a request for an itinerary that uses several flight legs is accepted or rejected in real time, and the dominant industrial control is the bid-price control: every leg carries a price, and a request is accepted only if its fare is at least the sum of the…

8 thms2 active usersReviewed
PreviousPage 91 of 110Next

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