Chernoff’s bound

James ZouProbability

If you have some randomness in your life, chances are that you want to try Chernoff’s bound. The most common way to understand randomness is a 2-step combo: find the average behavior, and show that the reality is unlikely to differ too much from the expectation (via Chernoff’s bound or its cousins). My favorite form of Chernoff’s bound is: for independent binary random variables, and , and , then     Note that are not necessarily identically distributed, they just have to be independent. In practice, we often care about significant deviation from the mean, so is typically larger than . In the standard applications, the stochastic system has size and an event of interest, , has expectation . The … Read More

Method of moments

James ZouMachine LearningLeave a Comment

The method of moments is a simple idea for estimating the parameters of a model. Suppose the observed data are sampled iid from a distribution , our goal is to estimate the parameter . If we have enough data, we can get very close to the true mean of the distribution, , which is a ¬†function of : . We know the form of since we know the form of . For simple distributions, knowing just the mean is enough to invert to obtain . In general, we need to calculate the higher moments, which are also known functions of : . We then try to invert the systems of equations to obtain . In practice, we typically only have … Read More