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
Graph TheoryOperations ResearchOptimization·Captain: mikedeng1

Seeding with Costly Network Information: PROBE and SEED Find a Seed Set Covering (1 − 1/e)OPT − ε′n Nodes in Expectation with an Explicitly Bounded Expected Number of Edge QueriesResearch Paper

Choosing a small group of people to start an intervention can have a much larger effect when their contacts pass it on. In many applications the contacts themselves are expensive to learn: a survey worker can ask about a person's neighbors, or a crawler can request one adjacency-list entry, but neither necessarily has a complete network. Eckles, Esfandiari,…

14 thms4 active usersReviewed
Algorithmic Game TheoryOperations Research·Captain: mikedeng1

Stochastic Games with General Payoff Functions: For Every ε > 0, Every Multiplayer Stochastic Game with Bounded Borel-Measurable Payoffs Has an ε-Solvable SubgameResearch Paper

A stochastic game (Shapley, 1953) is a dynamic game in which the players' actions influence the evolution of a state variable. Whether every multiplayer stochastic game admits an ε\varepsilonε-equilibrium for every ε>0\varepsilon>0ε>0 is open even for finitely many states and the long-run average payoff; it is open as well for the general class in which each…

12 thms4 active usersReviewed
EconomicsStochastic Systems·Captain: mikedeng1

Incomplete Information, Debt Issuance, and the Term Structure of Credit Spreads: Once Debt Capacity Is Exhausted, Creditors Face a Jump-to-Default Intensity Given in Closed Form by Equation (32)Research Paper

Creditors can observe a firm's liabilities while learning its asset value only after a delay. In the model of Benzoni, Garlappi, and Goldstein, this gap matters when the firm has exhausted its ability to issue more debt: creditors know that the firm has stayed above its default boundary, but do not know how close it is to that boundary now. Even though…

9 thms4 active usersReviewed
Control TheoryOperations ResearchStochastic Systems·Captain: mikedeng1

On System-Wide Safety Staffing of Large-Scale Parallel Server Networks: Positive SWSS Makes the Limiting Diffusion Exponentially Ergodic, Negative SWSS Makes It Transient Under Every Markov ControlResearch Paper

Large service systems such as call centres, hospital wards and cloud server farms route several customer classes to several server pools, with each pool trained for only some of the classes. Staffing such a network sits between two failure modes: too few servers make queues explode, and too many waste capacity. In the Halfin–Whitt (quality-and-efficiency-dri…

26 thms4 active usersReviewed
Bandit AlgorithmsStatistics·Captain: mikedeng1

Asymptotically Optimal Sequential Design for Rank Aggregation: The ε-Greedy Generalized-Likelihood-Ratio Ranking Policies Attain the Minimal Bayes Risk as the Comparison Cost Tends to ZeroResearch Paper

Rank aggregation turns many local comparisons into one global ordering. In a sequential setting, the experimenter chooses which two items to compare next, sees a noisy binary answer, and decides when enough evidence has been collected. More comparisons can improve the ranking, but each comparison has a cost. This tradeoff appears in preference elicitation…

15 thms4 active usersReviewed
Machine LearningReinforcement LearningStatistics·Captain: mikedeng1

Optimistic Posterior Sampling for Reinforcement Learning: Worst-Case Regret Bounds II: Along Any h, the Empirical Transition Vector Is within 2√(log(n/ρ)Σγᵢcᵢ²/n) + 3D log(2/ρ)/n of the TruthResearch Paper

Model-based reinforcement learning algorithms for Markov decision processes estimate each transition distribution Ps,aP_{s,a}Ps,a​ from the transitions they have observed out of the state–action pair (s,a)(s,a)(s,a). Their regret analyses then need to know how far the empirical distribution p^\hat pp^​ can be from the true one ppp. The standard tool is an ℓ1\ell_1ℓ1​ bound on p^−p\hat p-pp^​−p,…

7 thms4 active usersReviewed
CombinatoricsOperations ResearchOptimization+1·Captain: mikedeng1

Improved Guarantees for Offline Stochastic Matching via New Ordered Contention Resolution Schemes I: With Patience at Least 2, Attenuated Random-Order Probing Gives Every Edge a(e)·Pr[e Is Free] ≥ β*Research Paper

In offline stochastic matching a graph is given in which every edge is present only with some known probability, and the only way to find out is to probe it: a probed edge that turns out to be present must be added to the matching at once. Each vertex may also limit how many of its edges are probed (its patience). The model captures applications in which a…

14 thms4 active usersReviewed
Operations ResearchStochastic Systems·Captain: mikedeng1

Rank-Based Stochastic Differential Inclusions and Diffusion Limits for a Load-Balancing Model: Diffusion-Scaled Queue Lengths and Idle Times Converge to the Reflected Rank-Based DiffusionResearch Paper

Randomized load balancing assigns arriving jobs to one of several parallel servers using only partial information about queue lengths. The best-known example is the power-of-choice rule: sample ℓ\ellℓ of the NNN queues and join the shortest. Such rules are used in large server farms because the dispatcher communicates with only a few servers per job. The case…

22 thms4 active usersReviewed
Bandit AlgorithmsMachine LearningOperations Research·Captain: mikedeng1

Thompson Sampling with Information Relaxation Penalties I: For Natural Exponential Families the Suboptimality Gaps of TS, IRS.FH and IRS.V-Zero Are at Most 2√L[1/√ν + √(2 log T)(K/√ν + 2√(KT))]Research Paper

Thompson sampling (TS) is the most widely used heuristic for Bayesian multi-armed bandits: at each step it samples a parameter from the current posterior and plays the arm that is best for the sample. Its Bayesian regret has been analysed extensively (Russo and Van Roy, 2014; Bubeck and Liu, 2013). Min, Maglaras and Moallemi (arXiv:1902.04251) place TS…

9 thms4 active usersReviewed
Bandit AlgorithmsOperations ResearchStochastic Systems·Captain: mikedeng1

Learning Unknown Service Rates in Queues 3: In Heavy Traffic Every α-Consistent Scheduling Policy Has Average Queue-Regret at Least D(μ)(K−1) log t / (4 log log t) Up to Time (K−1)D(μ)/(4ε)Research Paper

A switch network is a set of UUU queues served by K≥UK\ge UK≥U servers. In every time slot each server can serve at most one queue, so a scheduler must pick a matching of queues to servers. Such systems model input-queued packet switches, crowdsourcing platforms that route job types to worker types, and wireless links with unknown channel quality. When the success…

10 thms4 active usersReviewed
Bandit AlgorithmsOperations ResearchStochastic Systems·Captain: mikedeng1

Learning Unknown Service Rates in Queues 1: Every α-Consistent Scheduling Policy Has Average Queue-Regret at Least λ_min D(μ)(1−α)(K−1)/(8t) for Infinitely Many tResearch Paper

Many service systems must route work to servers whose quality is not known in advance: crowdsourcing platforms matching job types to worker types, wireless schedulers assigning users to channels, call centers routing request classes to agent pools. Learning the unknown service rates is a multi-armed bandit problem, but the cost of a bad decision is not a…

8 thms4 active usersReviewed
Bandit AlgorithmsOperations Research·Captain: mikedeng1

A Primal-Dual Learning Algorithm for Personalized Dynamic Pricing with an Inventory Constraint: The Primal-Dual Learning Algorithm Has Regret at Most C(log n)^(2+δ) n^(−1/2)Research Paper

A firm selling a fixed stock of a perishable product over a finite season must set prices without knowing how demand responds to them. Online retail and travel platforms often see a customer's segment before quoting a price, so they can price-discriminate across consumer types. Learning a separate demand curve for each type, however, seems to cost more…

21 thms4 active usersReviewed
Algorithmic Game TheoryOperations Research·Captain: mikedeng1

Posted Price Mechanisms and Optimal Threshold Strategies for Random Arrivals II: For I.I.D. Variables, Adaptive Thresholds Achieve E[max Xᵢ] ≤ β*·E[X_t] with β* ≈ 1.341Research Paper

A prophet inequality compares a gambler who sees nonnegative random rewards X1,…,XnX_1,\ldots,X_nX1​,…,Xn​ one at a time, and must accept or reject each on arrival, with a prophet who knows all values in advance and simply takes max⁡iXi\max_i X_imaxi​Xi​. For independent and identically distributed (i.i.d.) rewards the question is the best constant β\betaβ such that some online rule always…

17 thms4 active usersReviewed
Operations ResearchOptimal TransportOptimization·Captain: mikedeng1

On a Problem of Optimal Transport Under Marginal Martingale Constraints 3: Between Probability Measures in Convex Order There Is Exactly One Left-Monotone Martingale PlanResearch Paper

In classical optimal transport on the real line, one coupling plays a distinguished role: the monotone (Hoeffding–Fréchet) coupling, which sends the qqq-quantile of the first marginal to the qqq-quantile of the second. It is canonical (every initial segment of the first marginal goes as far left as possible) and it is optimal for a whole family of costs at once.

17 thms4 active usersReviewed
Linear OptimizationOperations Research·Captain: mikedeng1

Stochastic Machine Scheduling with Precedence Constraints 2: LP-Based Graham List Scheduling Is a (2 − 1/m + max{1, (m − 1)Δ/m})-Approximation for P|in-forest|E[Σ w_j C_j]Research Paper

Scheduling jobs whose durations are uncertain is the normal situation in project management, manufacturing and computing: a job's processing time becomes known only when the job finishes, but a distribution for it is available in advance. Stochastic machine scheduling models this by random, independent processing times PjP_jPj​ and asks for a scheduling policy,…

11 thms4 active usersReviewed
Machine LearningStatistics·Captain: mikedeng1

Local Rademacher Complexities I: The Error Is Bounded by the Fixed Point of a Sub-Root Bound on Local Rademacher Averages of the Star-Hull (Theorem 3.3, Part 2)Research Paper

A learning algorithm that picks a function f^\hat ff^​ from a class F\mathcal FF by minimizing an empirical average is only as good as the gap between the empirical average PnfP_n fPn​f and the true mean PfPfPf, uniformly over the functions it might choose. The classical way to control this gap uses a global complexity of the whole class, such as its Rademacher average, and…

22 thms4 active users
Control TheoryDynamic ProgrammingOperations Research+1·Captain: mikedeng1

Stochastic Optimal Control: The Discrete-Time Case VIII: The Infinite-Horizon Borel Models — the Optimality Equation J* = T(J*) under (P), (N), (D)Textbook

Infinite horizon dynamic programming asks for the least expected cost of controlling a stochastic system forever, and for a policy attaining it. On finite or countable state spaces the theory has been classical since Bellman, Blackwell (1965) and Strauch (1966). Many models in operations research, inventory control, queueing and economics have continuous…

23 thms4 active usersReviewed
Algorithmic Game TheoryDynamical SystemsStochastic Systems·Captain: mikedeng1

On the Global Convergence of Stochastic Fictitious Play III: Almost Sure Convergence to Linearly Stable Rest Points in Potential GamesResearch Paper

Stochastic fictitious play is a basic model of learning in repeated games. Each period every player best responds to the empirical frequencies of the opponents' past play, after the player's payoffs have been hit by a fresh random shock. It was introduced by Fudenberg and Kreps (1993), is a standard object in the theory of learning in games (Fudenberg and…

14 thms4 active usersReviewed
Operations ResearchStatisticsStochastic Systems·Captain: mikedeng1

Weak Convergence and Optimal Scaling of Random Walk Metropolis Algorithms: Langevin Diffusion Limit of the First CoordinateResearch Paper

The random walk Metropolis algorithm is one of the most widely used Markov chain Monte Carlo methods for sampling from a density known up to a constant. Its one tuning parameter is the variance of the Gaussian proposal. If the variance is too small, the chain accepts almost every move but barely moves. If it is too large, it proposes long jumps that are…

15 thms4 active usersReviewed
Bandit AlgorithmsMachine LearningOperations Research·Captain: mikedeng1

Stochastic Linear Optimization under Bandit Feedback 1: The Regret Bound of ConfidenceBallResearch Paper

In stochastic linear optimization under bandit feedback a learner repeatedly chooses a decision xtx_txt​ from a fixed set D⊆RnD\subseteq\mathbb R^nD⊆Rn and observes only the noisy cost of that one decision, whose expectation is a fixed but unknown linear function μ⊤xt\mu^\top x_tμ⊤xt​. The model covers online routing, ad and product selection with feature vectors, and any…

24 thms4 active users
Machine LearningStatisticsTheoretical Computer Science·Captain: mikedeng1

Foundations of Machine Learning VIII: Multi-Class Classification and the Margin BoundTextbook

Every generalization bound in chapters 2-5 is for binary classification. Most real-world classification problems have more than two classes, and the number of classes can itself be in the hundreds or thousands (topic classification, speech recognition). Chapter 9 extends the margin-based generalization theory of chapter 5 (SVMs) to this multi-class,…

18 thms4 active users
Machine LearningStatisticsTheoretical Computer Science·Captain: mikedeng1

Foundations of Machine Learning III: Structural Risk Minimization and Model SelectionTextbook

Chapters 2 and 3 bound the estimation error of a hypothesis chosen from a fixed hypothesis set HHH, but the choice of HHH itself is left open: a richer HHH lowers the approximation error (how close HHH comes to the Bayes classifier) at the price of a looser generalization bound, and a poorer HHH does the reverse. Chapter 4 is the book's answer to this trade-off. It…

16 thms4 active users
Algorithmic Game TheoryMathematical Logic·Captain: martelus trismortuus

Online problems as Abramsky–Jagadeesan games: memoryless 2-taxi is not competitiveOpen Problem

Online algorithms are usually analysed as a game between an algorithm and an adversary who issues requests. The platform already hosts several such missions: competitive analysis of the kkk-taxi problem, optimal stopping and prophet inequalities, bandits. Each defines its own players, strategies and adversaries from scratch. For example, …

27 thms3 active usersReviewed
Dynamical SystemsMachine Learning·Captain: iris

Mitigating error propagation in chaotic dynamics via inference-time noising: a view from backward samplingResearch Paper

Machine-learned models of dynamical systems are usually trained to predict the next state and are then applied repeatedly to generate whole trajectories. For chaotic systems this is fragile: small one-step errors are amplified by the dynamics, and the states visited by the rollout drift away from the training distribution. Yet individual trajectories…

40 thms3 active usersReviewed
Combinatorics·Captain: iris

A Note on a Result of Chen Li: the Thinning Problem via the Kernel MethodResearch Paper

In Are many small sets explicitly small? (STOC 2010, doi:10.1145/1806689.1806693), Talagrand posed a list of problems at the meeting point of probability and combinatorics. They concern when a family of sets that is small in a measure-theoretic sense is also small for an explicit, combinatorial reason. Several of them have since driven major results: the…

17 thms3 active usersReviewed
PreviousPage 7 of 48Next

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