Difference between revisions of "高级算法 (Fall 2019)/Concentration of measure"

From EtoneWiki
Jump to: navigation, search
(Created page with "= Conditional Expectations = The '''conditional expectation''' of a random variable <math>Y</math> with respect to an event <math>\mathcal{E}</math> is defined by :<math> \mat...")
(No difference)

Revision as of 05:52, 8 October 2019

Conditional Expectations

The conditional expectation of a random variable with respect to an event is defined by

In particular, if the event is , the conditional expectation

defines a function

Thus, can be regarded as a random variable .

Example
Suppose that we uniformly sample a human from all human beings. Let be his/her height, and let be the country where he/she is from. For any country , gives the average height of that country. And is the random variable which can be defined in either ways:
  • We choose a human uniformly at random from all human beings, and is the average height of the country where he/she comes from.
  • We choose a country at random with a probability proportional to its population, and is the average height of the chosen country.

The following proposition states some fundamental facts about conditional expectation.

Proposition (fundamental facts about conditional expectation)
Let and be arbitrary random variables. Let and be arbitrary functions. Then
  1. .
  2. .
  3. .

The proposition can be formally verified by computing these expectations. Although these equations look formal, the intuitive interpretations to them are very clear.

The first equation:

says that there are two ways to compute an average. Suppose again that is the height of a uniform random human and is the country where he/she is from. There are two ways to compute the average human height: one is to directly average over the heights of all humans; the other is that first compute the average height for each country, and then average over these heights weighted by the populations of the countries.

The second equation:

is the same as the first one, restricted to a particular subspace. As the previous example, inaddition to the height and the country , let be the gender of the individual. Thus, is the average height of a human being of a given sex. Again, this can be computed either directly or on a country-by-country basis.

The third equation:

.

looks obscure at the first glance, especially when considering that and are not necessarily independent. Nevertheless, the equation follows the simple fact that conditioning on any , the function value becomes a constant, thus can be safely taken outside the expectation due to the linearity of expectation. For any value ,

The proposition holds in more general cases when and are a sequence of random variables.