Notes
This is a collection of technical notes that I’ve kept since partway through graduate school. They are mostly for my own use and are thus occasionally messy (e.g. links to not-yet-written notes), opinionated (e.g. thoughts about teaching), or both. But I sometimes point my students or collaborators to them, so they’re posted here to facilitate easy sharing.
Proofs in the notes are generally not fully rigorous. In the unlikely event that there’s a fact from the notes you’d like to use for which you can’t find a rigorous citation, please feel free to reach out.
Starting points
Technically, everything is reachable from Probability theory, but I’ve spent the most effort on the following Queueing theory areas:
- Laplace and Z transforms and the Method of collective marks.
- M/G/1 and M/G/k, including the following highlights:
- Many ways of analyzing the M/G/1 equilibrium work in system.
- The weird but useful Inverse busy period rate adjustment trick.
- The M/G/k last job lemma, which I believe is new (Yu et al., 2025; Lemma 3.7), but I’d be curious (and not too surprised) to hear about any earlier sources.
All notes
- Accumulating priority
- Age-residual joint transform
- Arrival-departure symmetry
- Arrival-sensitive busy period transform
- Arrival-sensitive inverse busy period rate adjustment trick
- Arrival-sensitive M/G/1
- Arrival-sensitive M/G/1 analysis
- Backwards notation for kernel composition
- Bandit processes
- Bernoulli random walk recurrence
- Big bad M/G/1 FCFS transform
- Boost policy
- Borel-Cantelli lemma
- Busy period age-residual joint transform
- Busy period joint transform
- Busy period rate adjustment
- Busy period transform
- Busy period tree
- CARD
- Categorical probability
- Combining SRPT with JSQ
- Continuity of probability
- Convergence almost surely
- Convergence in distribution
- Convergence in distribution setwise
- Convergence in Lᵖ
- Convergence in mean
- Convergence in mean squared
- Convergence in probability
- Convergence of random variables
- Convergence of random variables A–Z
- Covering number
- cµ rule
- Dispatching policies
- Distributional Little’s law
- Doob martingale
- DTMC to CTMC trick
- Envelope theorem
- Eric’s bag of bagels
- Eric’s randomly weighted coin puzzle
- Etemadi’s inequality
- Excess
- Excess transform
- Exponential sandwich probability
- First-come first-served
- Focusing on a subsystem
- Foster’s theorem
- G/G/1
- G/G/1 busy and idle periods
- Generalized Little’s law
- Generic chaining
- Geometric distribution transform
- Gittins
- Gittins game
- Gittins in combinatorial optimization
- Gittins index
- Guardrails dispatching
- Heavy-traffic SRPT is effectively two priority classes
- In-service state of a Markov process job
- Increasing steps in a permutation
- Inverse busy period rate adjustment trick
- Joint transform of time before and after exponential interruption
- Joint transform of two random variables and their sum
- Kernel
- Kernel composition
- Kolmogorov’s three-series theorem
- Kolmogorov’s zero-one law
- Laplace and Z transforms
- Laplace transform as probability of no interruptions
- Laplace transforms are completely monotonic
- Laplace transforms are determined by their value on an interval
- Laws of large numbers for i.i.d. sequences
- Linear envelope counterexample
- Little’s law
- Little’s law for red jobs
- Local hedging
- Localized Poisson process
- Lorden’s inequality
- Lévy’s equivalence theorem
- M/G arrivals
- M/G/1
- M/G/1 busy period
- M/G/1 equilibrium system state under FCFS
- M/G/1 equilibrium system state under PLCFS
- M/G/1 equilibrium system state under PS
- M/G/1 equilibrium time since idle and work in system
- M/G/1 equilibrium work in system
- M/G/1 number of jobs in system under FCFS
- M/G/1 transient work in system
- M/G/k
- M/G/k last job lemma
- M/G/∞
- M/G/∞ Euclidean Poisson perspective
- M/M/1
- Markov category
- Markov chain
- Markov process generator
- Markov process job model
- Markov process morphism
- Mean from excess transform
- Mean number of arrivals in a busy period
- Mean response time of Gittins
- Mean time before exponential interruption
- Method of collective marks
- Mills ratio
- Nudge
- Number of Poisson arrivals transform
- p-coin
- Palm calculus
- Palm inversion formula
- Pandora’s box
- PASTA
- Poisson process
- Poisson process construction from coin flips
- Preemptive last-come first-served
- Principle of maximum entropy
- Probability curriculum ideas
- Probability exercise ideas
- Probability of at most one exponential interruption
- Probability of probing an idle system after exponential delay
- Probability paradoxes
- Probability theory
- Processor sharing
- QPLEX
- Queueing theory
- Random walk
- Rate conservation law
- Reaching zero and staying nonnegative are equiprobable for the simple random walk
- Recovering a distribution from its excess
- Recycled relevant jobs
- Reflection principle for random walks
- Relating transient and equilibrium transforms for renewal processes
- Relationship between Laplace and Z transforms
- Relevant work
- Relevant work decomposition law
- Renewal cycles yield stationary measures of Markov chains
- Scheduling policies
- Server sharing
- Shooting room paradox
- Shortest remaining processing time
- Shorthand notation for measure of a random variable
- Sid’s conditional dice puzzle
- Skorohod embedding theorem
- Skorohod representation theorem
- SMART
- SOAP
- SRPT in heavy traffic
- State space collapse
- Stirling’s formula
- Stoppable bandit processes
- Sum of random number of random variables
- Tauberian theorem
- Transform operators
- Transient work transform via equilibrium joint transform
- Transient work transform via exponential sandwich
- WINE
- Work decomposition law
- Work transform via arrival-departure symmetry
- Work transform via busy period transform
- Work transform via Lindley equation
- Work transform via probability of probing an idle system
- Work transform via rate conservation law
- Work transform via relating queueing time to response time
- Work transform via system state under PLCFS
- Z transform as probability of no breakages