Probability – Page 4 – Applied Probability Notes

Diffusion Control Problems

The Hamilton-Jacobi-Bellman Equation.
Heuristic derivation of the HJB equation.
Davis-Varaiya Martingale Prinicple for Optimality

Continue reading “Diffusion Control Problems”

Stochastic Integration – a Heuristic view

Heuristic derivation of

the Stochastic Integral
Stochastic Differential Equations
Ito’s Formula

Continue reading “Stochastic Integration – a Heuristic view”

Infinite Time Horizon, MDP

Positive Programming, Negative Programming & Discounted Programming.
Optimality Conditions.

Continue reading “Infinite Time Horizon, MDP”

Markov Chains

A short introduction to Markov chains for dynamic programming
Definition, Markov Property, some Potential Theory.

Continue reading “Markov Chains”

Talagrand’s Concentration Inequality

We prove a powerful inequality which provides very tight gaussian tail bounds “ $e^{-ct^2}$ ” for probabilities on product state spaces $\Omega^n$ . 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.

Continue reading “Talagrand’s Concentration Inequality”

Markov Chains: a functional view

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.

Continue reading “Markov Chains: a functional view”

Spitzer’s Lyapunov Ergodicity

We show that relative entropy decreases for continuous time Markov chains.

Continue reading “Spitzer’s Lyapunov Ergodicity”

A Mean Field Limit

We consider a system consisting of $N$ interacting objects. As we let the number of objects increase, we can characterize the limiting behaviour of the system.

Continue reading “A Mean Field Limit”

Cross Entropy Method

In the Cross Entropy Method, we wish to estimate the likelihood

$l = {\mathbb P} ( S(X) \geq \gamma ).$

Here $X$ is a random variable whose distribution is known and belongs to a parametrized family of densities $f( , v)$ . Further $S(X)$ is often a solution to an optimization problem.

Continue reading “Cross Entropy Method”

Sanov’s Theorem

Sanov’s asks how likely is it that the empirical distribution some IIDRV’s is far from the distribution. And shows that the relative entropy determines the likelihood of being far.

Continue reading “Sanov’s Theorem”