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 ProgrammingLinear OptimizationOperations Research·Captain: mikedeng1

Analysis of Stochastic Dual Dynamic Programming Method: SDDP with Independently Subsampled Scenarios Finds an Optimal Policy of the SAA Problem in Finitely Many Iterations Almost SurelyResearch Paper

Multistage stochastic linear programs model sequential decisions under uncertainty: capacity and reservoir planning, hydro-thermal scheduling, inventory and asset–liability management. When the data process is stagewise independent, the problem decomposes by dynamic programming into one linear program per stage, coupled through expected cost-to-go functions.…

14 thms5 active usersReviewed
🏆Completed
Machine LearningTheoretical Computer Science·Captain: mikedeng1

What Can We Learn Privately? II: Parity Functions Are Privately PAC Learnable from O(d log(1/β)/(εα)) ExamplesResearch Paper

Differential privacy (Dwork, McSherry, Nissim and Smith, 2006) requires a randomized algorithm's output distribution to change little when one individual's record is changed. PAC learning asks an algorithm to output, from i.i.d. labeled examples, a hypothesis whose error is small with high probability. Kasiviswanathan, Lee, Nissim, Raskhodnikova and Smith (a…

14 thms5 active usersReviewed
🏆Completed
Discrete GeometryTheoretical Computer Science·Captain: wurtle

The Gaussian propeller bound in every dimensionResearch Paper

Split Euclidean space into finitely many measurable cells and record, for each cell, its Gaussian first moment, the integral of xxx against the standard Gaussian measure over that cell. How large can the sum of the squared lengths of these vectors be? The propeller conjecture predicts that, with at least three cells in dimension at least two, the answer is …

57 thms5 active usersReviewed
🏆Completed
Machine LearningTheoretical Computer Science·Captain: mikedeng1

What Can We Learn Privately? I: The Exponential Mechanism Privately Agnostically Learns Any Finite Concept Class from O((ln|C| + ln(1/β))·max{1/(εα), 1/α²}) ExamplesResearch Paper

Many learning tasks run on data about people: medical records, purchase histories, survey answers. A learner whose output reveals too much about any one training example is unusable on such data, however accurate it is. Differential privacy (Dwork, McSherry, Nissim and Smith, 2006) makes "reveals too much" precise: changing one individual's record may…

10 thms5 active usersReviewed
🏆Completed
Operations ResearchStochastic Systems·Captain: mikedeng1

Designing a Call Center with Impatient Customers I: The Steady-State Fraction of Abandoning Callers Tends to max(0, 1 − 1/ρ) as the Number of Agents GrowsResearch Paper

Telephone call centers are among the largest employers of service labour, and their staffing decisions are made with queueing models. The classical model is the Erlang-C queue M/M/NM/M/NM/M/N: Poisson arrivals, NNN agents, exponential service, infinitely patient callers. Real callers hang up. Garnett, Mandelbaum and Reiman (M&SOM 2002) argued that a model ignoring…

14 thms5 active usersReviewed
🏆Completed
Functional AnalysisMarkov Chain·Captain: mikedeng1

Logarithmic Sobolev Inequalities for Finite Markov Chains 5: The Log-Sobolev Constant of K(x, y) = π(y) Is (1 − 2π_)/log(1/π_ − 1)Research Paper

The log-Sobolev constant α\alphaα of a finite Markov chain controls how fast the chain forgets its starting point in relative entropy and in ℓ2\ell^2ℓ2, and it gives sharper mixing-time bounds than the spectral gap λ\lambdaλ when the stationary distribution has very small atoms. Diaconis and Saloff-Coste (Ann. Appl. Probab. 6 (1996)) made this constant a standard…

16 thms5 active usersReviewed
🏆Completed
Functional AnalysisMarkov Chain·Captain: mikedeng1

Logarithmic Sobolev Inequalities for Finite Markov Chains 4: The Metropolis Chain for the Binomial Distribution Is Within e^{1−c} of Stationarity after (n/2)(log n + 2c) StepsResearch Paper

The Metropolis algorithm turns a simple random walk into a Markov chain with a prescribed stationary distribution, by accepting or rejecting the walk's proposals. It is the basic tool of Markov chain Monte Carlo, and the practical question it raises is quantitative: how many steps are needed before the chain's distribution is close to the target? For most…

23 thms5 active usersReviewed
AnalysisOperations ResearchStochastic Systems·Captain: mikedeng1

Implicit Renewal Theory and Tails of Solutions of Random Equations 3: Rate of Approach — t^κP(R > t) Equals C₊ Minus a Contour Integral Plus O(t^{−β/2})Research Paper

Random equations of the form R=LΨ(R)R \overset{\mathcal L}{=} \Psi(R)R=LΨ(R), with Ψ\PsiΨ a random function independent of RRR, describe the stationary laws of many stochastic recursions: perpetuities in insurance and finance, the stationary law of ARCH-type volatility models, random difference equations R=Q+MRR = Q + MRR=Q+MR, and the stationary workload of certain queueing and storage…

17 thms5 active usersReviewed
Operations ResearchStochastic Systems·Captain: mikedeng1

Implicit Renewal Theory and Tails of Solutions of Random Equations 2: Kesten's Theorem for R = Q + MR — Unique Stationary Law, Power Tails with Explicit C±, and C₊ + C₋ > 0 iff Q ≢ (1 − M)cResearch Paper

The random difference equation

16 thms5 active usersReviewed
🏆Completed
Machine LearningOptimizationStatistics·Captain: mikedeng1

Learning Models with Uniform Performance via Distributionally Robust Optimization 2: A Minimax Lower Bound of Order n^(−1/2) ∨ n^(−1/k*) for Estimating the Cressie–Read Robust Risk (Theorem 3)Research Paper

Distributionally robust optimization replaces the expected loss EP0[ℓ(θ;X)]\mathbb E_{P_0}[\ell(\theta; X)]EP0​​[ℓ(θ;X)] of a statistical model by its worst case over all distributions QQQ close to the data distribution P0P_0P0​. When closeness is measured by an fff-divergence ball {Q:Df(Q∥P0)≤ρ}\{Q : D_f(Q\|P_0) \le \rho\}{Q:Df​(Q∥P0​)≤ρ} of fixed radius ρ>0\rho > 0ρ>0, the robust risk upper-bounds the risk of every…

13 thms5 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations Research·Captain: mikedeng1

Optimal Inventory Policies for Assembly Systems Under Random Demands 2: If an Item and Its Predecessors Have Negative Discounted Echelon Holding Cost, the Minimal Cost Is Unbounded BelowResearch Paper

Assembly systems — components purchased from outside, assembled into subassemblies, and those into an end product facing random customer demand — are the standard model of material requirements planning under uncertainty. Rosling's paper (Oper. Res. 37(4), 1989) shows that, under a cost assumption, the optimal policies of such a system are those of an…

17 thms5 active users
🏆Completed
Convex OptimizationOptimization·Captain: mikedeng1

Primal-dual subgradient methods for convex problems 2: Stochastic Simple Averages Reach E[φ(x̄ₖ)] − φ* ≤ β̂ₖ₊₁(γd(x*) + L²/(2σγ))/(k+1)Research Paper

Many decision problems under uncertainty take the form of minimizing an expected cost φ(x)=Eξf(x,ξ)\varphi(x) = \mathbb E_\xi f(x, \xi)φ(x)=Eξ​f(x,ξ) over a convex feasible set, where ξ\xiξ is a random parameter whose distribution can be sampled but not integrated in closed form. Evaluating φ\varphiφ even approximately can cost exponentially many evaluations of fff in the dimension of ξ\xiξ,…

18 thms5 active users
🏆Completed
Information TheoryTheoretical Computer Science·Captain: mikedeng1

Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data 1: Every [n, k, 2t+1] Code Gives an Average-Case Hamming Fuzzy Extractor with ℓ = m + kf − nf − 2 log(1/ε) + 2Research Paper

Cryptographic keys must be uniformly random and reproducible exactly. Many secrets people actually possess are neither: a biometric reading (an iris code, a fingerprint template), a long passphrase recalled with typos, or the correlated bits two parties obtain from a quantum channel are noisy, so two readings of the same secret differ in a few positions,…

12 thms5 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations Research·Captain: mikedeng1

Worst-Case Equilibria I: On Two Identical Parallel Links Every Mixed Nash Equilibrium Has Expected Makespan at Most 3/2 Times the OptimumResearch Paper

When many users share a network and each routes its own traffic selfishly, the outcome is a Nash equilibrium rather than a centrally optimized assignment. Koutsoupias and Papadimitriou, in Worst-case equilibria (STACS 1999; journal version 2009), proposed to measure the loss caused by this lack of coordination by the worst-case ratio between the social cost…

11 thms5 active usersReviewed
🏆Completed
AnalysisHarmonic Analysis·Captain: mikedeng1

Distribution Function Inequalities for Martingales 4: For Convex Φ of Moderate Growth, EΦ(f*) and EΦ(S(f)) Are Comparable for Every MartingaleResearch Paper

Martingale inequalities compare what a fluctuating process does along a path with how large its successive increments are. Such estimates are used in probability and harmonic analysis because a martingale can represent information revealed step by step, while its square function measures accumulated fluctuation. In his 1973 Wald Memorial Lectures,…

17 thms5 active usersReviewed
Complexity TheoryInformation TheoryTheoretical Computer Science·Captain: mikedeng1

A Pseudorandom Generator from Any One-Way Function: One-Way Functions Exist If and Only If Pseudorandom Generators ExistResearch Paper

Cryptographic protocols use random looking strings that can be reproduced from a shorter private seed. A pseudorandom generator provides those strings if no efficient observer can tell them from uniformly sampled bits. A one-way function provides a different kind of asymmetry: anyone can evaluate it efficiently, but no efficient algorithm can usually…

21 thms5 active usersReviewed
🏆Completed
Dynamic ProgrammingMachine LearningOperations Research+1·Captain: mikedeng1

Stable Function Approximation in Dynamic Programming II: In a Nondiscounted MDP with All Policies Proper, Value Iteration Through a Self-Weighted Averager ConvergesResearch Paper

Value iteration solves a Markov decision process by repeatedly applying the Bellman backup to a table of state values. When the state space is too large for a table, the values are stored in a function approximator instead: each backup is followed by a fit, and the fitted function is backed up again. This approximate value iteration is the basis of fitted…

8 thms5 active usersReviewed
🏆Completed
Operations ResearchOptimizationStochastic Systems·Captain: mikedeng1

Optimal Starting Times for End-of-Season Sales and Optimal Stopping Times for Promotional Fares 3: With One Markdown or Markup Allowed, Thresholds x_n < z_n Give the Optimal PolicyResearch Paper

Retailers of seasonal goods, home builders selling out a development, and airlines and cruise lines selling promotional fares all face the same operational question: inventory is fixed, the selling season is finite, and the price can be changed only rarely. Menu costs, advertising commitments and customer goodwill often restrict a seller to a single price…

10 thms5 active usersReviewed
🏆Completed
Operations ResearchOptimizationStochastic Systems·Captain: mikedeng1

Optimal Starting Times for End-of-Season Sales and Optimal Stopping Times for Promotional Fares 2: Markup Is Optimal Once Time-to-Go Exceeds an Increasing Threshold z_nResearch Paper

An airline may offer a low promotional fare while seats remain available, then raise the fare as departure approaches. The choice is dynamic: a sale changes both the number of seats left and the benefit of waiting. The same decision appears for hotel rooms and theater seats. Feng and Gallego study a policy with two fixed prices and at most one price change,…

6 thms5 active usersReviewed
🏆Completed
Complexity TheoryQuantum InformationTheoretical Computer Science·Captain: mikedeng1

Strengths and Weaknesses of Quantum Computing I: Relative to a Random Oracle, a Quantum Algorithm Needs Ω(2^{n/2}) Queries to Decide Whether 1ⁿ Has a PreimageResearch Paper

Grover's algorithm (Grover 1996) finds a marked item among NNN with O(N)O(\sqrt N)O(N​) queries, a quadratic speed-up over any classical algorithm. Whether quantum computers can do substantially better on search, and so solve NP-type problems by brute force in polynomial time, was settled in the negative by Bennett, Bernstein, Brassard and Vazirani (arXiv:quant-ph/9701…

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

Poisson Arrivals See Time Averages: Under Lack of Anticipation, the Fraction of Time in B Converges a.s. iff the Fraction of Arrivals Finding B Does, to the Same LimitResearch Paper

Queueing analysis constantly moves between two kinds of long-run averages: the fraction of time a system spends in some set of states, and the fraction of arriving customers who find it there. Waiting-time formulas for the M/G/1 queue, blocking probabilities in loss systems and many decomposition arguments rest on the claim that, when arrivals form a…

13 thms5 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Optimal Pricing and Return Policies for Perishable Commodities II: Neither Unlimited Returns at Full Credit nor a No-Returns Policy Coordinates the ChannelResearch Paper

Manufacturers of perishable goods must decide how much inventory risk to leave with retailers. A retailer who pays for every ordered unit may order less than is best for the manufacturer and retailer together; a generous return policy changes that incentive. Pasternack studies this question in a single-period setting, with a fixed selling price, uncertain…

9 thms5 active usersReviewed
🏆Completed
AnalysisOperations Research·Captain: mikedeng1

The Data-Driven Newsvendor Problem: New Bounds and Insights II: Every Log-Concave Demand Has Weighted Mean Spread at Least min(b,h)/(b+h)Research Paper

The newsvendor problem is the basic single-period inventory model: a decision maker orders qqq units before a random demand DDD is observed, pays b>0b>0b>0 per unit of unmet demand and h>0h>0h>0 per unit left over, and minimizes the expected cost C(q)=E[b(D−q)++h(q−D)+]C(q)=E[b(D-q)^+ + h(q-D)^+]C(q)=E[b(D−q)++h(q−D)+]. When the distribution of DDD is known, the optimal order is the b/(b+h)b/(b+h)b/(b+h) quantile of DDD. In practice…

9 thms5 active usersReviewed
Bandit AlgorithmsDynamic ProgrammingOperations Research·Captain: mikedeng1

Bandit Processes and Dynamic Allocation Indices: A Policy Is Optimal If and Only If It Almost Surely Continues a Bandit Process of Maximal Dynamic Allocation IndexResearch Paper

The multi-armed bandit problem asks how to share effort sequentially among several independent projects, each of which evolves only while it is worked on. It models the scheduling of jobs on a single machine, the order in which to explore candidate sites, sequential clinical trials and the allocation of research effort among competing projects. Before 1972…

8 thms5 active usersReviewed
🏆Completed
Statistics·Captain: mikedeng1

On Tail Probabilities for Martingales 1: If X_n ≤ 1 and E{X_n | ℱ_{n−1}} ≤ 0, Then P{S_n ≥ a and T_n ≤ b for Some n} ≤ (b/(a+b))^{a+b} e^a ≤ exp[−a²/2(a+b)]Research Paper

For sums of independent bounded random variables, the inequalities of Bernstein and Bennett bound the probability of a large deviation by an exponential in the deviation and the variance (Bennett 1962; Hoeffding 1963). Many processes met in probability, statistics and learning theory are not sums of independent terms but martingales or supermartingales:…

19 thms5 active users
PreviousPage 6 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