19th Ave New York, NY 95822, USA

# 统计代写| Using probability and expectation to prove existence stat代写

## 统计代考

$4.9$ “Using probability and expectation to prove existence
An amazing and beautiful fact is that we can use probability and expectation to prove the existence of objects with properties we care about. This technique is called the probabilistic method, and it is based on two simple but surprisingly powerful ideas. Suppose I want to show that there exists an object in a collection with a certain property. This desire seems at first to have nothing to do with probability, object with the desired property.

The probabilistic method rejects such painstaking inspection in favor of random selection: our strategy is to pick an object at random from the collection and show that there is a positive probability of the random object having the desired property. Note that we are not required to compute the exact probability, but merely to show it is greater than 0 . If we can show that the probability of the property holding is positive, then we know that there must exist an object with we don’t know how to explicitly construct such an object.
Similarly, suppose each object has a score, and I want to show that there exists an object with a “good” score that is, a score exceeding a particular threshold. Again, we proceed by choosing a random object and considering its score, $X$. We know there is an object in the collection whose score is at least $E(X)$-it’s impossible for every object to be below average! If $E(X)$ is already a good score, then there must also be an object in the collection with a good score. Thus we can show the existence of an object with a good score by showing that the average score is already good.
Let’s state the two key ideas formally.

• The possibility principle: Let $A$ be the event that a randomly chosen object in a collection has a certain property. If $P(A)>0$, then there exists an object with the property.
• The good score principle: Let $X$ be the score of a randomly chosen object. If $E(X) \geq c$, then there is an object with a score of at least $c$.

To see why the possibility principle is true, consider its contrapositive: if there is no object with the desired property, then the probability of a randomly chosen object having the property is 0 . Similarly, the contrapositive of the good score principle is “if all objects have a score below $c$, then the average score is below $c$ “, which is true since a weighted average of numbers less than $c$ is a number less than $c$.
The probabilistic method doesn’t tell us how to find an object with the desired property; it only assures us that one exists.
Example 4.9.1. A group of 100 people are assigned to 15 committees of size 20 , such that each person serves on 3 committees. Show that there exist 2 committees that have at least 3 people in common.

A direct approach is inadvisable here: one would have to list all possible committee assignments and compute, for each one, the number of people in common in every pair of committees. The probabilistic method lets us bypass brute-force calculations. To prove the existence of two committees with an overlap of at least three people, we’ll calculate the average overlap of two randomly chosen committees in an arbi- trary committee assignment. So choose two committees at random, and let $X$ be the number of people on both committees. We can represent $X=I_{1}+I_{2}+\cdots+I_{100}$, where $I_{j}=1$ if the $j$ th person is on both committees and 0 otherwise. By symmetry, all of the indicators have the same expected value, so $E(X)=100 E\left(I_{1}\right)$, and we just need to find $E\left(I_{1}\right)$. By the fundamental bridge, $E\left(I_{1}\right)$ is the probability that person 1 (whom we’ll name Bob) is on both committees (which we’ll call A and B). There are a variety of ways to calculate this probability; one way is to think of Bob’s committees as 3 tagged elk in a population of 15 . Then A and B are a sample of 2 elk, made without replacement. Using the HGeom(3,12,2) PMF, the probability that both of these elk are tagged (i.e., the probability that both committees contain Bob) is $\left(\begin{array}{l}3 \ 2\end{array}\right)\left(\begin{array}{c}12 \ 0\end{array}\right) /\left(\begin{array}{c}15 \ 2\end{array}\right)=1 / 35$. Therefore, $$E(X)=100 / 35=20 / 7,$$
which is just shy of the desired “good score” of 3 . But hope is not lost! The good score principle says there exist two committees with an overlap of at least $20 / 7$, but $20 / 7$ implies an overlap of at least 3 . Thus, there exist two committees with at least. 3 people in common.

## 统计代考

4

$4.9$“用概率和期望证明存在

• 可能性原则：设$A$ 为集合中随机选择的对象具有特定属性的事件。如果 $P(A)>0$，则存在具有该属性的对象。
• 好分数原则：设 $X$ 为随机选择的对象的分数。如果$E(X) \geq c$，则存在一个得分至少为$c$ 的对象。