Blog Archives

Lovasz Local Lemma

The probabilistic method is a non-constructive way of proving the existence of an object having certain property. The argument usually goes as follows: a randomly selected object has the desired property with probability strictly positive, thus there must exist an

Tagged with: , ,
Posted in Probability

Azuma’s Inequality

The Chernoff bound gives the concentration of sums of independent random variables. The concentration result can be generalized to martingales. Martingales and Azuma’s Inequality A sequence of random variables \(X_0, X_1, \ldots, X_n\) is called a martingale if \[ {\bf

Tagged with: ,
Posted in Probability

Normal, Chi-Squared and Gamma Distributions

Here we show the classical example on how the normal, chi-squared, and gamma distributions are related. If \(Z_1, \ldots, Z_n\) are i.i.d. variables with the standard normal distribution, then \(\sum_{i=1}^n Z_i \sim \chi^2_n\). Let \(X_1, \ldots, X_n \sim \text{Normal}(\mu, \sigma^2)\)

Tagged with: , , ,
Posted in Probability

Conditional and Marginal Independence

Let \(A, B, C\) be three random variables. Consider the following dependency structures modeled with Bayesian networks. \(A \leftarrow B \rightarrow C\) \(A \rightarrow B \rightarrow C\) \(A \rightarrow B \leftarrow C\) The first two cases both say that \(A\)

Tagged with: , ,
Posted in Probability