统计代写| 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$“用概率和期望证明存在
一个惊人而美丽的事实是，我们可以使用概率和期望来证明具有我们关心的属性的对象的存在。这种技术被称为概率方法，它基于两个简单但令人惊讶的强大想法。假设我想证明集合中存在一个具有特定属性的对象。起初，这种愿望似乎与概率无关，对象具有所需的属性。
概率方法拒绝这种有利于随机选择的艰苦检查：我们的策略是从集合中随机挑选一个对象，并表明随机对象具有所需属性的概率为正。请注意，我们不需要计算确切的概率，而只是表明它大于 0 。如果我们可以证明持有该属性的概率是正的，那么我们就知道一定存在一个对象，而我们不知道如何显式地构造这样一个对象。
类似地，假设每个对象都有一个分数，我想证明存在一个具有“好”分数的对象，即分数超过特定阈值。同样，我们继续选择一个随机对象并考虑其分数 $X$。我们知道集合中有一个对象的分数至少为 $E(X)$——不可能每个对象都低于平均水平！如果$E(X)$ 已经是一个很好的分数，那么集合中肯定也有一个分数很高的对象。因此，我们可以通过显示平均分数已经很好来表明存在具有好分数的对象。
让我们正式陈述两个关键思想。
- 可能性原则：设$A$ 为集合中随机选择的对象具有特定属性的事件。如果 $P(A)>0$，则存在具有该属性的对象。
- 好分数原则：设 $X$ 为随机选择的对象的分数。如果$E(X) \geq c$，则存在一个得分至少为$c$ 的对象。
要了解为什么可能性原理是正确的，请考虑其对立面：如果不存在具有所需属性的对象，则随机选择的对象具有该属性的概率为 0 。类似地，好分数原则的反义词是“如果所有对象的分数低于 $c$，则平均分数低于 $c$”，这是正确的，因为小于 $c$ 的数字的加权平均值是一个数字小于$c$。
概率方法并没有告诉我们如何找到具有所需属性的对象。它只向我们保证存在一个。
例 4.9.1。一组 100 人被分配到 15 个大小为 20 的委员会，每个人在 3 个委员会任职。证明存在至少有 3 个共同成员的 2 个委员会。
直接的方法在这里是不可取的：必须列出所有可能的委员会分配，并为每个委员会计算每对委员会的共同人数。概率方法让我们绕过蛮力计算。为了证明至少有三个人重叠的两个委员会的存在，我们将计算任意委员会分配中两个随机选择的委员会的平均重叠。所以随机选择两个委员会，让$X$ 是两个委员会的人数。我们可以表示 $X=I_{1}+I_{2}+\cdots+I_{100}$，如果第 $j$ 人同时在两个委员会中，则 $I_{j}=1$，否则为 0。通过对称性，所有指标都具有相同的期望值，所以 $E(X)=100 E\left(I_{1}\right)$，我们只需要找到 $E\left(I_{1}\对）$。通过基本的桥梁，$E\left(I_{1}\right)$ 是个人 1（我们将其命名为 Bob）在两个委员会（我们将其称为 A 和 B）中的概率。有多种方法可以计算这个概率；一种方法是将 Bob 的委员会视为人口 15 中的 3 个标记的麋鹿。那么 A 和 B 是 2 只麋鹿的样本，没有替换。使用 HGeom(3,12,2) PMF，这两个麋鹿都被标记的概率（即两个委员会都包含 Bob 的概率）是 $\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$。因此，$$ E(X)=100 / 35=20 / 7，$$
这只是 3 的理想“好分数”。但希望并没有消失！好分数原则说存在两个委员会，重叠至少为 $20 / 7$，但 $20 / 7$ 意味着至少有 3 个重叠。因此，至少存在两个委员会。 3个人共同。
。
R语言代写
统计代写|SAMPLE SPACES AND PEBBLE WORLD stat 代写 请认准UprivateTA™. UprivateTA™为您的留学生涯保驾护航。
