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
CombinatoricsTheoretical Computer Science·Captain: iris

A polynomial scaling window for random k-SAT and a proof of the satisfiability conjectureResearch Paper

A random kkk-SAT formula on nnn Boolean variables is a conjunction of independent uniformly random clauses, each a disjunction of kkk literals on kkk distinct variables. As clauses are added, the formula passes from satisfiable to unsatisfiable, and the question of where and how fast this happens has driven work in probabilistic combinatorics, statistical physics…

25 thms4 active usersReviewed
CombinatoricsConvex OptimizationInformation Theory+1·Captain: iris

Optimal e(γ+o(1))ne^{(\gamma+o(1))n}e(γ+o(1))n-Approximation of the Permanent of Positive Semidefinite MatricesResearch Paper

The permanent of a matrix A∈Cn×nA\in\mathbb C^{n\times n}A∈Cn×n is per(A)=∑σ∈Sn∏i=1nAi,σ(i)\mathrm{per}(A)=\sum_{\sigma\in S_n}\prod_{i=1}^n A_{i,\sigma(i)}per(A)=∑σ∈Sn​​∏i=1n​Ai,σ(i)​. Computing it exactly is #P-hard even on 0/1 matrices (Valiant 1979). For nonnegative entries a randomized approximation scheme exists (Jerrum, Sinclair, Vigoda 2004). For a Hermitian positive semidefinite matrix the entries may have…

37 thms4 active usersReviewed
Bandit AlgorithmsMachine LearningReinforcement Learning·Captain: iris

Introducing Feedback Delays to Non-Delayed Adversarial MDPs: Optimal √S and √K Dependencies in Tabular and Linear AMDPsResearch Paper

An episodic adversarial Markov decision process (AMDP) models a learner who repeats an HHH-step task for KKK episodes while an adversary fixes the loss function of every episode in advance. The learner sees only the losses of the state-action pairs it visits (bandit feedback), and it does not know the transition law. The standard measure of performance is the re…

82 thms4 active usersReviewed
Graph TheoryMarkov Chain·Captain: iris

Sampling Colorings on G(n,d/n)G(n, d/n)G(n,d/n) via Glauber DynamicsResearch Paper

Sampling a uniformly random proper qqq-colouring of a graph is a basic test case for Markov chain Monte Carlo and for the theory of spin systems: proper colourings are the zero-temperature antiferromagnetic Potts model. The simplest sampler is Glauber dynamics: pick a uniform vertex and recolour it uniformly among the colours not used by its neighbours. On…

67 thms4 active usersReviewed
Machine LearningOptimization·Captain: iris

Memory-efficient Finite-sum Optimization without Full Gradient RefreshesResearch Paper

Training a model by empirical risk minimization means minimizing an average f(x)=1n∑i=1nfi(x)f(x)=\frac1n\sum_{i=1}^n f_i(x)f(x)=n1​∑i=1n​fi​(x) of nnn component losses over x∈Rdx\in\mathbb R^dx∈Rd, where nnn is the number of data points and is often very large. A full gradient ∇f\nabla f∇f costs nnn component-gradient queries; a stochastic gradient costs one query but its noise prevents convergence with a…

21 thms4 active usersReviewed
Bandit AlgorithmsMachine LearningOperations Research·Captain: iris

No-Regret Revenue Maximization in Sequential Market Making Under Inventory ConstraintsResearch Paper

A market maker quotes two prices for an asset: a bid, at which it buys, and an ask, at which it sells. It earns the spread when both sides trade, and it carries inventory risk when they do not balance: a maker that buys much more than it sells is exposed to the price of the asset itself, which defeats the purpose of quoting. Classical market-making models…

29 thms4 active usersReviewed
Graph TheoryMarkov ChainTheoretical Computer Science·Captain: iris

A Spectral Local-to-Global Principle for Spin Systems on Graphs with Girth At Least FiveResearch Paper

Sampling a uniformly random proper qqq-colouring of a graph G=(V,E)G=(V,E)G=(V,E), a map χ:V→[q]\chi:V\to[q]χ:V→[q] with χ(u)≠χ(v)\chi(u)\ne\chi(v)χ(u)=χ(v) on every edge, is a basic problem of discrete probability, statistical physics and the theory of approximate counting. A folklore conjecture states that for every graph of maximum degree Δ\DeltaΔ, efficient sampling is possible as soon as q≥Δ+1q\ge\Delta+1q≥Δ+1 (…

26 thms4 active usersReviewed
Algorithmic Game TheoryMachine Learning·Captain: iris

Non-manipulability and Approachability Beyond Two-Player GamesResearch Paper

Online learning algorithms are routinely deployed against a single strategic party that sees how they behave: buyers bidding through autobidders on an ad platform, sellers pricing against a marketplace's matching rule, agents trained by self-play. The learners are usually asked for a worst-case guarantee, no regret, which protects each of them whatever the…

15 thms4 active usersReviewed
Functional AnalysisRepresentation Theory·Captain: iris

Equivalence of the Brownian and Energy Representations: URU^RUR and ULU^LUL Are Unitarily Equivalent to the Energy Representation of H(G)H(G)H(G) (Normalization Corrected)Research Paper

Let GGG be a compact connected Lie group. Its path group is the group of paths in GGG starting at the identity, with pointwise multiplication. Unitary representations of path and current groups were studied by Gelfand, Graev and Vershik (Compositio Math. 35, 1977) and by Albeverio and Høegh-Krohn (Compositio Math. 36, 1978), in connection with quantum field…

54 thms4 active usersReviewed
Dynamic ProgrammingOperations Research·Captain: iris

Markov Decision Processes with Applications to Finance XV: The Perpetual American Put Is the Smallest Superharmonic Majorant of the Payoff and Is Exercised Below a ThresholdTextbook

An American option may be exercised at any time up to its expiry, so its fair price is the value of an optimal stopping problem under the risk-neutral measure, and its optimal exercise rule is an optimal stopping time. Chapter 11 of Bäuerle and Rieder's Markov Decision Processes with Applications to Finance (Springer, 2011) treats this problem as a Markov…

26 thms4 active usersReviewed
Dynamic ProgrammingOperations ResearchOptimization·Captain: iris

Markov Decision Processes with Applications to Finance V: Under Regime Switching Ordered in the Increasing Concave Order the Value Rises and Consumption Falls with the RegimeTextbook

Return distributions of risky assets are not constant over time: they shift with the business cycle, monetary policy, regulation or catastrophes. A standard way to capture this in portfolio theory is a regime-switching (Markov-modulated) market, in which an observable finite-state Markov chain, the environment process, selects the distribution of next…

33 thms4 active usersReviewed
Machine LearningOperations ResearchStatistics·Captain: iris

Optimal Policies for Dynamic Pricing and Inventory Control with Nonparametric Censored Demands: Trisection Search with a Difference Estimator Has √T·ln²T Regret for Strongly Concave RewardsResearch Paper

A retailer that sets both a price and a stock level each period, without knowing how demand responds to price or how demand fluctuates, has to learn while selling. In the lost-sales setting the learning problem is harder than in pure pricing: when a period ends with empty shelves, the firm sees only its sales, not the demand that went unmet. Joint pricing…

13 thms4 active usersReviewed
Complexity TheoryOperations ResearchOptimization·Captain: iris

Efficient Approximation Schemes for Stochastic Probing and Selection-Stopping Problems: Free-Order Prophets Admits an EPTAS, a t(ε)·poly(n)-Time (1 − ε)-Approximate OrderResearch Paper

In Free-Order Prophets a decision maker faces nnn independent non-negative random values with known laws, chooses in advance the order in which to inspect them, and on seeing each value must stop and take it or move on for good. The problem models selection with a sequence the decision maker controls: sequencing interviews, or inspecting alternatives whose…

43 thms4 active usersReviewed
Operations ResearchRevenue Management and PricingTheoretical Computer Science·Captain: iris

Assortment Optimization Under the Multi-Purchase Multinomial Logit Choice Model: A Deterministic Algorithm Earns 1 − ε of Optimal Revenue in Time n^O(m²/ε) When Each Customer Buys at Most m ProductsResearch Paper

In many retail settings a customer leaves with several products, not one: a basket of groceries, a set of streaming titles, a bundle of software modules. Classical discrete choice models used in revenue management, above all the multinomial logit (MNL) model, describe a customer who buys at most one product. Bai, Feldman, Segev, Topaloglu and Wagner (author…

18 thms4 active usersReviewed
Information TheoryQuantum Information·Captain: iris

From Classical to Quantum Shannon Theory XIV: The Packing LemmaTextbook

Every coding theorem for sending classical data over a quantum channel has to answer the same question: given a family of quantum states that a sender can prepare, how many of them can a receiver tell apart reliably, and with which measurement? The packing lemma is a one-shot answer. It asks for an ensemble of states and a set of projectors satisfying four…

12 thms4 active usersReviewed
Bandit AlgorithmsMachine LearningOperations Research·Captain: iris

Technical Note—On Dynamic Pricing with Covariates: UCB Pricing Has Regret at Most 4ḡp̄γ̄√(Td log((2d+T)/(2d))) + p̄D̄ for Arbitrary CovariatesResearch Paper

A retailer that sets prices online sees, before each sale, information about the customer, the product or the market: a covariate vector. Demand depends on the price and on these covariates through parameters the seller does not know, so the seller must learn the demand model while pricing. This dynamic pricing with covariates problem is a standard model in…

11 thms4 active usersReviewed
Operations ResearchOptimization·Captain: iris

Supermodularity in Two-Stage Distributionally Robust Optimization: With a Supermodular Second-Stage Cost, the Two-Stage DRO Problem Is Equivalent to a Linear Program over K(2n+1) Worst-Case PointsResearch Paper

Two-stage decisions under uncertainty are a basic model of operations planning: capacities, inventories or facility locations are fixed first, demand or yield is observed, and a recourse decision is then taken at the cost of a linear program. When the distribution of the uncertainty is known only through a few statistics, distributionally robust optimization…

27 thms4 active usersReviewed
Operations ResearchOptimizationTheoretical Computer Science·Captain: iris

The Stability of MNL-Based Demand Under Dynamic Customer Substitution and Its Algorithmic Implications: A Randomized (1 − ε)-Approximation Scheme for Dynamic Assortment PlanningResearch Paper

A retailer chooses which products to carry and how many units of each to stock, under a shelf or warehouse capacity, before a selling season in which inventory is not replenished. Customers who find their favourite product sold out may buy another one instead: this dynamic substitution couples the demand of all products through the stock-out history.…

44 thms4 active usersReviewed
Operations ResearchStochastic Systems·Captain: iris

Processing Networks XV: A State-Dependent Foster–Lyapunov Drift Condition Implies Positive Recurrence of a Discrete-Time Markov ChainTextbook

Stability of a stochastic processing network (a queueing network, a switch, a wireless scheduler) is usually proved by representing the network as a Markov chain on a countable state space and showing that the chain is positive recurrent: every state is revisited after a finite expected time. Dai and Harrison's Processing Networks: Fluid Models and Stability…

10 thms4 active usersReviewed
Bandit AlgorithmsOperations ResearchReinforcement Learning+1·Captain: iris

Regret Analysis of a Markov Policy Gradient Algorithm for Multiarm Bandits: SAMBA Converges to the Optimal Arm Almost Surely with Regret at Most NαΔlog⁡T+Q\frac{N}{\alpha\Delta}\log T + QαΔN​logT+QResearch Paper

Policy-gradient methods adjust the probabilities with which a learner picks actions by following an estimated gradient of its expected reward. They underlie much of modern reinforcement learning (Williams 1992; Sutton–Barto 2018), yet regret guarantees for them are scarce even in the simplest setting, the stochastic multi-armed bandit, where the benchmark…

24 thms4 active usersReviewed
Dynamic ProgrammingOperations ResearchStochastic Systems·Captain: iris

Risk Averse Stochastic Programming: Time Consistency and Optimal Stopping: The Nested-Risk Snell Envelope Is the Optimal Stopping Value, Attained by the First Time It Meets the RewardResearch Paper

Optimal stopping asks when to stop a reward process Z0,…,ZTZ_0,\dots,Z_TZ0​,…,ZT​ so as to make the stopped reward ZτZ_\tauZτ​ as large as possible. In its classical form the criterion is the expectation E[Zτ]\mathbb E[Z_\tau]E[Zτ​], and the solution is the Snell envelope: the value process obtained by comparing, at each date, the reward for stopping now with the conditional expectation…

22 thms4 active usersReviewed
Operations ResearchStochastic Systems·Captain: iris

Heavy-Traffic Universality of Redundancy Systems with Assignment Constraints: The Scaled Stationary Job Counts Collapse onto One Exponential Variable Times the Critical Arrival ProportionsResearch Paper

Parallel-server systems in data centres cannot send every job everywhere: data locality and license restrictions tie each job to a subset of the servers. Redundancy scheduling copes with this by replicating a job to all of its compatible servers. Under cancel-on-completion (c.o.c.) the other replicas are discarded when the first one finishes; under cancel-on…

54 thms4 active usersReviewed
Convex OptimizationOperations Research·Captain: iris

Stochastic Localization Methods for Convex Discrete Optimization via Simulation: Shrinking Uniform Sampling Returns an (ε, δ)-PGS Solution at Cost O(ε⁻² log(N/δ) + N)Research Paper

Many operational decisions are a single integer: the number of trucks to recruit for a region, the number of staff for an event, the number of servers in a queueing system. When the performance of each choice can only be estimated by simulation, finding a good choice is a problem of optimization via simulation: each evaluation of a candidate returns a noisy…

44 thms4 active usersReviewed
Linear OptimizationOperations ResearchOptimization·Captain: iris

Assign-to-Seat: Dynamic Capacity Control for Selling High-Speed Train Tickets: re-solving a dynamic primal loses O(√θ) revenue against the hindsight optimum, and O(1) under no early endingResearch Paper

Railway operators in China sell tickets for high-speed trains on routes with many intermediate stops, at fares fixed by regulation. A ticket from stop iii to stop j+1j+1j+1 uses legs i,…,ji,\dots,ji,…,j, and at the moment of purchase the passenger must be given one seat for the whole trip. Seats cannot be swapped later. This assign-to-seat restriction is absent from…

19 thms4 active usersReviewed
Linear OptimizationOperations ResearchOptimization·Captain: iris

Online Linear Programming: Dual Convergence, New Algorithms, and Regret Bounds: the sampled dual LP optimum converges to the stochastic-program optimum with E‖p_n − p‖² ≤ C·m log m·log log n / nResearch Paper

Online linear programming (OLP) models sequential resource allocation: orders (rj,aj)(r_j,a_j)(rj​,aj​) arrive one at a time, each must be accepted or rejected on arrival, and accepted orders consume the capacities bbb of a linear program. It covers network revenue management, online auctions, matching and the multi-secretary problem. Almost every OLP algorithm uses the same…

15 thms4 active usersReviewed
PreviousPage 5 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