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