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 ProgrammingMachine LearningReinforcement Learning·Captain: mikedeng1

Technical Note: Q-Learning: With Bounded Rewards and Learning Rates with Σα = ∞, Σα² < ∞ at Every State–Action Pair, Tabular Q-Learning Converges to Q* with Probability 1Research Paper

Q-learning is the basic model-free algorithm of reinforcement learning: an agent that does not know the transition probabilities or the reward structure of a controlled Markov process learns the optimal action values from experience alone, by a one-line update applied after every observed transition. It was introduced in C. J. C. H. Watkins' 1989 thesis,…

8 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations Research·Captain: mikedeng1

Optimal Ordering and Rationing Policies in a Nonstationary Dynamic Inventory Model with n Demand Classes I: Critical Rationing Levels z̄ₜ¹ ≥ ⋯ ≥ z̄ₜⁿ Give an Optimal Policy When Each aₜ Is 0 or 1Research Paper

A firm that holds a single stock of a product often serves customers of different priority: military and civilian requisitions, contract and spot customers, emergency and routine orders for spare parts. When stock runs short, it must decide not only how much demand to satisfy but whose. Satisfying a low-priority order now may leave the firm unable to serve…

10 thms3 active usersReviewed
🏆Completed
Operations ResearchStatisticsStochastic Systems·Captain: mikedeng1

Estimating Variance From High, Low and Closing Prices I: S_t(S_t − X_t) + I_t(I_t − X_t) Has Mean σ²t for Brownian Motion With Any DriftResearch Paper

The logarithm of a share price is commonly modelled as a Brownian motion with drift, Xt=σBt+ctX_t=\sigma B_t+ctXt​=σBt​+ct. The Black–Scholes option pricing formula needs the volatility σ\sigmaσ but not the drift ccc, so a practitioner must estimate σ2\sigma^2σ2 from data. Observing the whole path would give σ2\sigma^2σ2 exactly through its quadratic variation, but a real observer sees…

9 thms3 active usersReviewed
🏆Completed
CombinatoricsOperations Research·Captain: mikedeng1

Concentration of Measure and Isoperimetric Inequalities in Product Spaces VII: Bin Packing — P(|B_N − M| ≥ 1 + u) ≤ 8 exp(−u²/(64 N E X₁²))Textbook

Bin packing asks for the minimum number of unit-capacity bins into which a list of items with sizes in [0,1][0,1][0,1] can be packed. It is one of the basic NP-hard problems of combinatorial optimization and operations research, and its stochastic version, where the item sizes are random, has a large literature (Coffman and Lueker, Probabilistic Analysis of Packing…

6 thms3 active usersReviewed
🏆Completed
CombinatoricsGraph Theory·Captain: mikedeng1

Concentration of Measure and Isoperimetric Inequalities in Product Spaces X: The Chromatic Number of Random Graphs — χ(G(n,p), m) Lies in an Interval of Length k with High ProbabilityTextbook

The chromatic number of the random graph G(n,p)G(n,p)G(n,p) is one of the central random variables of probabilistic combinatorics. Its order of magnitude for constant ppp, χ(G(n,p))∼n/(2log⁡1/(1−p)n)\chi(G(n,p)) \sim n/(2\log_{1/(1-p)} n)χ(G(n,p))∼n/(2log1/(1−p)​n), was settled by Bollobás ([B], 1988); the question that remains is how much χ\chiχ fluctuates around its typical value. Shamir and Spencer ([S-S], 1987) used the…

5 thms3 active usersReviewed
🏆Completed
AnalysisCombinatorics·Captain: mikedeng1

Concentration of Measure and Isoperimetric Inequalities in Product Spaces V: The Convex Hull Distance — ∫ exp f_α(A,x) dP ≤ P(A)^{−α}Textbook

A product probability space (ΩN,P)(\Omega^N, P)(ΩN,P), P=μ⊗NP=\mu^{\otimes N}P=μ⊗N, concentrates its mass: a set AAA of non-negligible measure is "close" to most points. How closeness is measured decides what the statement can be used for. The Hamming distance (Chapter 2 of the paper) counts coordinates in which a point differs from AAA; it gives Gaussian concentration, but only for…

10 thms3 active usersReviewed
🏆Completed
Bandit AlgorithmsOperations ResearchStatistics·Captain: mikedeng1

Some Aspects of the Sequential Design of Experiments I: Greedy Sampling with Density-Zero Forced Draws Earns max(α, β) per Draw from Any Two Populations with Finite MeansResearch Paper

An experimenter can draw observations from two populations AAA and BBB, one at a time, and wants the sum of the observations to be as large as possible. The populations might be two treatments, two seed varieties or two manufacturing processes; their means are unknown. Each draw both earns a reward and tells the experimenter something about the population it…

8 thms3 active usersReviewed
🏆Completed
Operations ResearchStochastic Systems·Captain: mikedeng1

Regenerative Stochastic Processes 1: The State Probabilities of an Aperiodic Equilibrium Process Converge to (1/μ₁)∫φ_A(v){1 − F(v)}dvResearch Paper

Many stochastic systems studied in operations research "start afresh" at certain random instants: a single-server queue each time a customer arrives to find the server idle, an inventory system each time stock is replenished to its order level, a reliability system each time a failed unit is replaced. Between such instants the system may evolve in a…

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

Regenerative Stochastic Processes 3: A Cumulative Process Has Mean (κ₁/μ₁)t + o(t) and Variance (t/μ₁){σ₂² − 2ρσ₁σ₂κ₁/μ₁ + σ₁²(κ₁/μ₁)²} + o(t)Research Paper

Many stochastic systems accumulate a real-valued quantity while repeatedly returning to a state at which a new cycle begins. A queue may accumulate work or cost, a component may accumulate wear, and a recurrent system may accumulate time in a state. The observations at a fixed clock time usually cut through a cycle. This makes the moments of the observed…

7 thms3 active usersReviewed
🏆Completed
Markov ChainStochastic Systems·Captain: mikedeng1

Random Walks in a Random Environment 1: Transience to +∞, to −∞, or Recurrence According to Σ n⁻¹P(ρ_n > 1) < ∞, Σ n⁻¹P(ρ_n < 1) < ∞, or Both Infinite (E ln σ < 0, > 0, = 0)Research Paper

A random walk on the integers in which the probability of stepping right depends on the current site is the simplest model of motion through a disordered medium: a particle diffusing in a crystal with impurities, a molecule moving along a heterogeneous polymer, or a gene frequency drifting under fluctuating selection. When the site-dependent probabilities…

9 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Optimal Pricing and Return Policies for Perishable Commodities I: Unlimited Returns at Partial Credit Coordinate the Channel for Every Demand DistributionResearch Paper

A manufacturer of a perishable good (newspapers, magazines, bread, seasonal fashion, printed books) sells through a retailer who must commit to an order before demand is known. Unsold units lose most of their value; unmet demand costs goodwill. When the retailer alone bears the risk of leftovers, it orders less than an integrated firm would, and the channel…

7 thms3 active usersReviewed
🏆Completed
CombinatoricsNumber TheoryTheoretical Computer Science·Captain: mikedeng1

A New Class of Random Number Generators 1: For Prime m = bʳ + bˢ − 1, Every Nontrivial Add-with-Carry Sequence Is Periodic After r Steps, with Period the Order of b mod mResearch Paper

Simulation, Monte Carlo integration and randomized algorithms consume long streams of numbers that should behave like independent uniform draws. A deterministic generator with finite state is eventually periodic, so its period is the first figure of merit: a stream cannot be longer than its cycle. G. Marsaglia and A. Zaman, A new class of random number…

17 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryAnalysisOperations Research·Captain: mikedeng1

Values of Large Games II: Oceanic Games 1: Closed-Form Values of Interior Oceanic GamesResearch Paper

Weighted voting bodies often combine a few large blocs with a mass of small, unorganized voters: shareholders' meetings with a handful of large holders and a dispersed float, legislatures with party blocs and independents. The Shapley value measures each participant's voting power as the probability of being pivotal — the one whose arrival first turns a…

9 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingMarkov ChainOperations Research·Captain: mikedeng1

Some Monotonicity Results for Partially Observed Markov Decision Processes: MLR-Monotone Optimal Values and the Myopic Policy as a Lower Bound on the Optimal PolicyResearch Paper

A partially observed Markov decision process (POMDP) models a controller that cannot see the state of the system it controls. It sees only noisy observations, and so it acts on a belief: a probability vector over the hidden states. Machine maintenance, medical screening, quality control and search problems all have this form. The dynamic program of a POMDP…

16 thms3 active usersReviewed
🏆Completed
Markov ChainOperations ResearchStochastic Systems·Captain: mikedeng1

Stochastic Processes Occurring in the Theory of Queues and their Analysis by the Method of the Imbedded Markov Chain: In GI/M/s, a Positive Wait Is Exponential and a Positive Queue GeometricResearch Paper

A many-server queue in which customers arrive at the epochs of a renewal process and are served for exponential times is the basic model of a telephone exchange, a call centre, or a bank of identical machines. Its continuous-time queue-length process is not Markovian unless the arrivals are Poisson, so Erlang's birth–death formulas for M/M/s do not apply.…

22 thms3 active usersReviewed
🏆Completed
Operations ResearchStochastic Systems·Captain: mikedeng1

Stochastic Inequalities on Partially Ordered Spaces 1: Stochastically Ordered Initial Laws and Kernels Give Coupled Random Sequences with Xₙ ≤ Yₙ for All n Almost SurelyResearch Paper

Comparison theorems for stochastic processes answer a practical question: if one system starts "lower" and moves "upward" less aggressively than another, does it stay below the other one for all time? Queueing, reliability and inventory models use such statements to order performance measures of two systems without computing either distribution. Results of…

14 thms3 active usersReviewed
🏆Completed
Operations ResearchStatistics·Captain: mikedeng1

The Data-Driven Newsvendor Problem: New Bounds and Insights I: The SAA Order Is ε-Optimal with Probability at Least 1 − 2exp(−Nε²min(b,h)/((18 + 8ε)(b + h)))Research Paper

The newsvendor problem is the basic model of stocking under uncertain demand: an order quantity is fixed before a random demand is observed, and every unit short or left over is penalized. Its solution is a quantile of the demand distribution. In practice that distribution is unknown and only a sample of past demands is available. The standard remedy, sample…

7 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryFunctional Analysis·Captain: mikedeng1

Existence of Correlated Equilibria III: A Game with Compact Hausdorff Strategy Spaces and Continuous Payoffs Has a Countably Additive Correlated EquilibriumResearch Paper

A correlated equilibrium (Aumann 1974) describes play in a game where a mediator draws a profile of recommended actions from a joint distribution and tells each player only that player's own recommendation; the distribution is an equilibrium when no player gains, on average, by departing from the recommendation. Correlated equilibria are the natural outcome…

9 thms3 active usersReviewed
🏆Completed
Markov ChainOperations ResearchStochastic Systems·Captain: mikedeng1

Contact Interactions on a Lattice I: A Contact Process with (2d − 1)λₖ < kμ Dies Out from Every Finite Initial SetResearch Paper

The contact process is the basic model of an infection spreading on a lattice: each infected site recovers at a constant rate, and each healthy site becomes infected at a rate that depends on how many of its neighbours are infected. It was introduced by T. E. Harris in Contact Interactions on a Lattice (Ann. Probab. 2, 1974), and it became one of the…

13 thms3 active usersReviewed
🏆Completed
Operations ResearchStochastic Systems·Captain: mikedeng1

Heavy-Traffic Limits for Queues with Many Exponential Servers: The Scaled Stationary M/M/n Queue Length Converges to a Hybrid Exponential–Normal LawResearch Paper

Telephone exchanges, call centers, hospital wards and cloud server pools are queues with a large number sss of parallel servers. For such systems two classical approximations pull in opposite directions. Holding sss fixed and letting the traffic intensity ρ→1\rho \to 1ρ→1 gives the conventional heavy-traffic limit, in which almost every customer waits. Letting sss grow…

13 thms3 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchTheoretical Computer Science·Captain: mikedeng1

Packet Routing and Job-Shop Scheduling in O(Congestion + Dilation) Steps: Edge-Simple Paths with Congestion c and Dilation d Admit an O(c + d)-Step Schedule with Constant-Size QueuesResearch Paper

In a store-and-forward network, messages are cut into packets that travel from node to node along wires, one wire per time step, and wait in buffers between moves. Routing such traffic splits into two problems: choosing a path for each packet, and scheduling the packets along their paths, deciding at every step which packets move and which wait. Leighton,…

10 thms3 active usersReviewed
🏆Completed
Dynamical SystemsOperations ResearchStochastic Systems·Captain: mikedeng1

Subadditive Ergodic Theory 1: Kingman's Theorem — x₀ₜ/t Converges with Probability One and in Mean to a Finite ξ with E(ξ) = γResearch Paper

Many stochastic systems have an accumulated cost or passage time that grows with the length of an observation window. Splitting a window at an intermediate time gives an upper bound on the total, even when it does not give an equality. First-passage percolation and products of random matrices are examples discussed by Kingman (1973). A central question is…

8 thms3 active usersReviewed
🏆Completed
Markov ChainStochastic Systems·Captain: mikedeng1

On the Generalized “Birth-and-Death” Process 1: For Rates λ(t), μ(t) ≥ 0 the Population Size Is Geometric with a Modified Zero Term, ξ_t = 1 − e^{−ρ}/W, η_t = 1 − 1/WResearch Paper

Population models often allow each individual to produce a new individual or die at rates that change over time. Seasonal conditions, exposure to an epidemic, and changing conditions in a laboratory population all make a constant rate a restrictive assumption. In Kendall's 1948 paper, the question is how the entire distribution of the population size…

8 thms3 active usersReviewed
🏆Completed
Graph TheoryOperations ResearchStochastic Systems·Captain: mikedeng1

Loss Networks 3: If E e^{λX} < ∞ and 2E(X − C)⁺ < E(C − X)⁺, i.i.d. Loads on the Complete Graph Fit on Direct and Two-Edge Routes with Probability → 1Research Paper

Telephone and data networks are often fully connected at the core: every pair of switching centres has a direct trunk group, and a call that finds its direct trunk full may be alternatively routed over a two-link path through a third, tandem centre. Whether such a network can absorb fluctuations of demand without losing traffic depends on how the spare…

9 thms3 active usersReviewed
🏆Completed
Statistics·Captain: mikedeng1

On Tail Probabilities for Martingales 3: If E exp[−e(λ)W] ≤ e^{−λa} and E exp[−f(λ)W] ≥ e^{−λ(a+1)} for All λ ≥ 0, Then P{W < b} > ½ exp[−(½ + 2δ)a²/b]Research Paper

Freedman's inequality bounds the probability that a martingale with increments bounded above by 111 reaches a level aaa before its accumulated conditional variance exceeds bbb: the bound is exp⁡[−a2/2(a+b)]\exp[-a^2/2(a+b)]exp[−a2/2(a+b)] (D. A. Freedman, On Tail Probabilities for Martingales, Ann. Probab. 3 (1975) 100–118, Theorem (4.1), doi:10.1214/aop/1176996452). It is the standard tool…

14 thms3 active usersReviewed
PreviousPage 29 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