Lecture 22: Transformations and Convolutions | Statistics 110

TL;DR

The hypergeometric variance equals the binomial variance, np(1-p), multiplied by the finite population correction (N-n)/(N-1). The derivation writes the number of sampled white balls as a sum of dependent indicators and includes their negative covariance. The lecture also shows how an average overlap of 20/7 proves that two of 15 committees overlap by at least three people. Read on for the derivations and intuition.

Transcript

Picking up right where we left off last time, we were deriving the variance of a hypergeometric, right? So I was just wanting to quickly recap that and make a few more comments about it. We basically did the calculation last time, just didn't simplify the algebra. But I wanna say a few more things about that and remind you. So we were doing the var... Read More

Key Insights

• 👍 Probability can be used to prove the existence of objects with desired properties.
• 💻 Computing the average of a random variable can provide evidence for the existence of an object with a certain property.
• 👍 Even if it is difficult to explicitly find an object with a desired property, the existence of one can be proven through probability analysis.

Questions & Answers

Q: How do you derive the variance of a hypergeometric random variable?

Write X as the sum of n indicator variables, where Xj indicates whether the jth sampled ball is white. Add their variances and all pairwise covariances; symmetry reduces the calculation to n Var(X1) + 2 times n choose 2 times Cov(X1, X2), which simplifies to np(1-p)(N-n)/(N-1).

Q: What is the hypergeometric variance formula?

With population size N = w + b, sample size n, and white-ball proportion p = w/(w+b), the variance is np(1-p)(N-n)/(N-1). It is the binomial variance np(1-p) multiplied by the finite population correction.

Q: Why are covariance terms needed in the hypergeometric variance calculation?

Sampling is performed without replacement, so the indicator variables are not independent. Consequently, the variance of their sum must include the pairwise covariance terms rather than only the individual variances.

Q: How is the covariance between the first two draw indicators calculated?

Use Cov(X1, X2) = E(X1X2) - E(X1)E(X2). Here, E(X1)E(X2) = p², while E(X1X2) is the probability that both balls are white: [w/(w+b)] × [(w-1)/(w+b-1)].

Q: What does the finite population correction mean?

The factor (N-n)/(N-1) adjusts the binomial variance for sampling without replacement from a finite population. When N is much larger than n, the factor is extremely close to 1, so the hypergeometric variance is extremely close to the binomial variance.

Q: What happens to the variance when the sample size is one?

When n = 1, the finite population correction becomes 1, leaving the Bernoulli variance p(1-p). This makes sense because drawing only one ball produces no practical difference between sampling with and without replacement.

Q: How is the average overlap of two random committees calculated?

Represent each person's presence in both selected committees with an indicator variable, then add the indicators to obtain the overlap. For 100 people, 15 committees of 20, and three committee memberships per person, the expected overlap is 20/7.

Q: Why does an average committee overlap of 20/7 prove that some pair overlaps by at least three?

If the average overlap among pairs is 20/7, at least one pair must have an overlap no smaller than that average. Because overlap is an integer, that pair must share at least three people.

Summary

In this video, the speaker begins by recapping the concept of variance for a hypergeometric distribution. They then introduce the notation and formulas used to calculate the variance, highlighting the importance of covariance terms in non-independent situations. The speaker goes on to demonstrate the simplification of the variance formula, resulting in a neat and simple expression. They discuss the implications of this expression in various scenarios, including extreme cases. The focus then shifts to the topic of change of variables in probability, with the speaker explaining the process of transforming a random variable using a function. They introduce the Jacobian and discuss the different interpretations and formula variations for calculating the Jacobian. The speaker concludes the video by exploring the concept of convolution, which represents the distribution of the sum of random variables. They explain the analogy between convolution in the discrete and continuous cases and highlight the usefulness of convolution in certain scenarios. Finally, the speaker presents a novel approach to proving the existence of objects with desired properties using probability theory. They discuss the strategies of showing the probability of an event is greater than zero for a random object and the existence of an object with a score at least equal to the average. A practical example involving committees and overlap of members is used to illustrate the application of these strategies.

Questions & Answers

Q: What is the variance of a hypergeometric distribution?

The variance of a hypergeometric distribution measures the spread or variability of the number of successes in a sample drawn without replacement from a finite population. It is calculated using a formula that includes the variances of individual indicator random variables and the covariances between them.

Q: How can we simplify the expression for the variance of a hypergeometric distribution?

The expression for the variance of a hypergeometric distribution can be simplified by taking advantage of symmetry. Since the indicator random variables representing the presence or absence of a success in each draw are all the same, we can treat them as if they are independent and calculate the variance of just one of them. This leads to a simpler expression of the variance as the product of the sample size, the probability of success, and the complement of the probability of success.

Q: What is the Jacobian in probability theory?

The Jacobian is a matrix of partial derivatives that represents the transformation between two sets of variables. In probability theory, it is used to calculate the density function of a transformed random variable. It is computed by taking all possible partial derivatives of the new variables with respect to the original variables and forming a matrix. The determinant of the Jacobian matrix is then used to adjust the probability density function in the transformation.

Q: What is the concept of convolution in probability theory?

Convolution in probability theory refers to finding the distribution of the sum of two random variables. It allows us to compute the probability mass function or probability density function of the sum variable, given the probability mass functions or probability density functions of the individual variables. Convolution can be applied to discrete and continuous random variables, and it is often used to analyze the combined effect of independent random variables.

Q: How can probability theory be used to prove the existence of objects with desired properties?

Probability theory can be used to prove the existence of objects with desired properties by demonstrating that the probability of the property being satisfied is greater than zero. This can be done by defining a probability measure on the set of possible objects and showing that it assigns a positive probability to the event of interest. By choosing a random object according to this probability measure, we can show that there must exist at least one object with the desired property.

Q: Can you provide an example of using probability to prove existence of objects with desired properties?

Sure! Let's consider the example of committees formed by a group of people. Suppose we have 100 people and 15 committees, each consisting of 20 people. The desired property we want to show exists is the existence of two committees with an overlap of at least three people. We can show this by calculating the average overlap of two random committees. By using indicator random variables and linearity of expectation, we find the expected value of the overlap to be 20/7. Since the overlap is an integer, we can round up to conclude that there must exist two committees with an overlap of at least three people.

Takeaways

Probability theory has various applications beyond just calculating probabilities and expected values. It can be used to derive key properties and distributions, such as the variance of a hypergeometric distribution. Furthermore, probability theory enables transformations of random variables through change of variables methods, which involve the calculation of Jacobians. Convolution allows for the computation of the distribution of the sum of random variables, providing a powerful tool for analyzing combined effects. Additionally, probability theory can be employed to prove the existence of objects with desired properties by demonstrating positive probabilities associated with those properties. Finally, probability theory plays a crucial role in fields such as information theory, where the existence of optimal codes and communication strategies relies on probabilistic arguments.

Summary & Key Takeaways

• We have 100 people forming 15 committees of 20 people each, with each person on three committees.

• The task is to prove the existence of two committees with an overlap of at least three.

• To do this, we compute the average overlap of two random committees.

• By using indicator random variables and calculating the probability of a person being on both committees, we find an average overlap of 20/7.

• Since we can round the overlap up to the next integer, we can prove the existence of two committees with an overlap of at least three.