We prove a powerful inequality which provides very tight gaussian tail bounds “” for probabilities on product state spaces . Talagrand’s Inequality has found lots of applications in probability and combinatorial optimization and, if one can apply it, it generally outperforms inequalities like Azzuma-Hoeffding.
We will regularly need to employ certain calculations. In MATH10951 the context might vary but the maths varies much less. These notes are more of a background check on prequisties. We cover
- Power, the exponential, logarithms, the (natural) logarithm.
- Arithmetic and Geometric progressions.
- Laplacian; Adjoints; Harmonic fn; Green’s fn; Forward Eqn; Backward Eqn.
- Markov Chains and Martingales; Green’s Functions and occupancy; Potential functions; time-reversal and adjoints.
We show that relative entropy decreases for continuous time Markov chains.
We explain why certain distributions arise naturally as the limit of coin throws.
- Bernoulli, Binomial Distributions, Geometric Distributions.
- Binomial to Poisson Distribution; Geometric to Exponential; Binomial to Normal.
We consider a system consisting of interacting objects. As we let the number of objects increase, we can characterize the limiting behaviour of the system.
Lyapunov functions are an extremely convenient device for proving that a dynamical system converges.