Lecture 22: Transformations and Convolutions | Statistics 110

TL;DR

By computing the average overlap of two randomly chosen committees, we can prove the existence of two committees with an overlap of at least three.

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 is the average overlap of two random committees calculated?

The average overlap of two random committees is calculated by finding the probability of a person being on both committees. This is done using indicator random variables and the hypergeometric distribution. The result is an average overlap of 20/7.

Q: How does the average overlap prove the existence of two committees with an overlap of at least three?

The average overlap of 20/7 implies that there must exist a pair of committees with an overlap of at least 20/7. Rounding up to the next integer, we can prove the existence of two committees with an overlap of at least three.

Q: Are there any limitations or assumptions in this analysis?

One assumption made in this analysis is that the committees were chosen randomly and with equal probability. Additionally, the method used to calculate the average overlap may not apply in situations where different people are on a different number of committees.

Q: Can this method be applied to other scenarios?

Yes, this method can be applied to other scenarios where we want to prove the existence of objects with certain properties. By computing the average of a random variable representing the desired property, we can show that an object with that property exists.

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.