随机算法 (Spring 2014)/Martingales

From EtoneWiki
Jump to: navigation, search

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.

Martingales

"Martingale" originally refers to a betting strategy in which the gambler doubles his bet after every loss. Assuming unlimited wealth, this strategy is guaranteed to eventually have a positive net profit. For example, starting from an initial stake 1, after losses, if the th bet wins, then it gives a net profit of

which is a positive number.

However, the assumption of unlimited wealth is unrealistic. For limited wealth, with geometrically increasing bet, it is very likely to end up bankrupt. You should never try this strategy in real life. And remember: gambling is bad!

Suppose that the gambler is allowed to use any strategy. His stake on the next beting is decided based on the results of all the bettings so far. This gives us a highly dependent sequence of random variables , where is his initial capital, and represents his capital after the th betting. Up to different betting strategies, can be arbitrarily dependent on . However, as long as the game is fair, namely, winning and losing with equal chances, conditioning on the past variables , we will expect no change in the value of the present variable on average. Random variables satisfying this property is called a martingale sequence.

Definition (martingale)
A sequence of random variables is a martingale if for all ,

Examples

coin flips
A fair coin is flipped for a number of times. Let denote the outcome of the th flip. Let
.
The random variables defines a martingale.
Proof
We first observe that , which intuitively says that the next number of HEADs depends only on the current number of HEADs. This property is also called the Markov property in statistic processes.
Polya's urn scheme
Consider an urn (just a container) that initially contains balck balls and white balls. At each step, we uniformly select a ball from the urn, and replace the ball with balls of the same color. Let , and be the fraction of black balls in the urn after the th step. The sequence is a martingale.
edge exposure in a random graph
Consider a random graph generated as follows. Let be the set of vertices, and let be the set of all possible edges. For convenience, we enumerate these potential edges by . For each potential edge , we independently flip a fair coin to decide whether the edge appears in . Let be the random variable that indicates whether . We are interested in some graph-theoretical parameter, say chromatic number, of the random graph . Let be the chromatic number of . Let , and for each , let , namely, the expected chromatic number of the random graph after fixing the first edges. This process is called edges exposure of a random graph, as we "exposing" the edges one by one in a random grpah.
360px
As shown by the above figure, the sequence is a martingale. In particular, , and . The martingale moves from no information to full information (of the random graph ) in small steps.

It is nontrivial to formally verify that the edge exposure sequence for a random graph is a martingale. However, we will later see that this construction can be put into a more general context.

Generalizations

The martingale can be generalized to be with respect to another sequence of random variables.

Definition (martingale, general version)
A sequence of random variables is a martingale with respect to the sequence if, for all , the following conditions hold:
  • is a function of ;

Therefore, a sequence is a martingale if it is a martingale with respect to itself.

The purpose of this generalization is that we are usually more interested in a function of a sequence of random variables, rather than the sequence itself.

Azuma's Inequality

We introduce a martingale tail inequality, called Azuma's inequality.

Azuma's Inequality
Let be a martingale such that, for all ,
Then

Before formally proving this theorem, some comments are in order. First, unlike the Chernoff bounds, there is no assumption of independence. This shows the power of martingale inequalities.

Second, the condition that

is central to the proof. This condition is sometimes called the bounded difference condition. If we think of the martingale as a process evolving through time, where gives some measurement at time , the bounded difference condition states that the process does not make big jumps. The Azuma's inequality says that if so, then it is unlikely that process wanders far from its starting point.

A special case is when the differences are bounded by a constant. The following corollary is directly implied by the Azuma's inequality.

Corollary
Let be a martingale such that, for all ,
Then

This corollary states that for any martingale sequence whose diferences are bounded by a constant, the probability that it deviates far away from the starting point after steps is bounded by .

Generalization

Azuma's inequality can be generalized to a martingale with respect another sequence.

Azuma's Inequality (general version)
Let be a martingale with respect to the sequence such that, for all ,
Then

The Proof of Azuma's Inueqality

We will only give the formal proof of the non-generalized version. The proof of the general version is almost identical, with the only difference that we work on random sequence conditioning on sequence .

The proof of Azuma's Inequality uses several ideas which are used in the proof of the Chernoff bounds. We first observe that the total deviation of the martingale sequence can be represented as the sum of deferences in every steps. Thus, as the Chernoff bounds, we are looking for a bound of the deviation of the sum of random variables. The strategy of the proof is almost the same as the proof of Chernoff bounds: we first apply Markov's inequality to the moment generating function, then we bound the moment generating function, and at last we optimize the parameter of the moment generating function. However, unlike the Chernoff bounds, the martingale differences are not independent any more. So we replace the use of the independence in the Chernoff bound by the martingale property. The proof is detailed as follows.

In order to bound the probability of , we first bound the upper tail . The bound of the lower tail can be symmetrically proved with the replaced by .

Represent the deviation as the sum of differences

We define the martingale difference sequence: for , let

It holds that

The second to the last equation is due to the fact that is a martingale and the definition of conditional expectation.

Let be the accumulated differences

The deviation can be computed by the accumulated differences:

We then only need to upper bound the probability of the event .

Apply Markov's inequality to the moment generating function

The event is equivalent to that for . Apply Markov's inequality, we have

This is exactly the same as what we did to prove the Chernoff bound. Next, we need to bound the moment generating function .

Bound the moment generating functions

The moment generating function

The first and the last equations are due to the fundamental facts about conditional expectation which are proved by us in the first section.

We then upper bound the by a constant. To do so, we need the following technical lemma which is proved by the convexity of .

Lemma
Let be a random variable such that and . Then for ,
Proof.
Observe that for , the function of the variable is convex in the interval . We draw a line between the two endpoints points and . The curve of lies entirely below this line. Thus,

Since , we have

By expanding both sides as Taylor's series, it can be verified that .

Apply the above lemma to the random variable

We have already shown that its expectation and by the bounded difference condition of Azuma's inequality, we have Thus, due to the above lemma, it holds that

Back to our analysis of the expectation , we have

Apply the same analysis to , we can solve the above recursion by

Go back to the Markov's inequality,

We then only need to choose a proper .

Optimization

By choosing , we have that

Thus, the probability

The upper tail of Azuma's inequality is proved. By replacing by , the lower tail can be treated just as the upper tail. Applying the union bound, Azuma's inequality is proved.

The Doob martingales

The following definition describes a very general approach for constructing an important type of martingales.

Definition (The Doob sequence)
The Doob sequence of a function with respect to a sequence of random variables is defined by
In particular, and .

The Doob sequence of a function defines a martingale. That is

for any .

To prove this claim, we recall the definition that , thus,

where the second equation is due to the fundamental fact about conditional expectation introduced in the first section.

The Doob martingale describes a very natural procedure to determine a function value of a sequence of random variables. Suppose that we want to predict the value of a function of random variables . The Doob sequence represents a sequence of refined estimates of the value of , gradually using more information on the values of the random variables . The first element is just the expectation of . Element is the expected value of when the values of are known, and when is fully determined by .

The following two Doob martingales arise in evaluating the parameters of random graphs.

edge exposure martingale
Let be a random graph on vertices. Let be a real-valued function of graphs, such as, chromatic number, number of triangles, the size of the largest clique or independent set, etc. Denote that . Fix an arbitrary numbering of potential edges between the vertices, and denote the edges as . Let
Let and for , let .
The sequence gives a Doob martingale that is commonly called the edge exposure martingale.
vertex exposure martingale
Instead of revealing edges one at a time, we could reveal the set of edges connected to a given vertex, one vertex at a time. Suppose that the vertex set is . Let be the subgraph of induced by the vertex set , i.e. the first vertices.
Let and for , let .
The sequence gives a Doob martingale that is commonly called the vertex exposure martingale.

Chromatic number

The random graph is the graph on vertices , obtained by selecting each pair of vertices to be an edge, randomly and independently, with probability . We denote if is generated in this way.

Theorem [Shamir and Spencer (1987)]
Let . Let be the chromatic number of . Then
Proof.
Consider the vertex exposure martingale

where each exposes the induced subgraph of on vertex set . A single vertex can always be given a new color so that the graph is properly colored, thus the bounded difference condition

is satisfied. Now apply the Azuma's inequality for the martingale with respect to .

For , the theorem states that the chromatic number of a random graph is tightly concentrated around its mean. The proof gives no clue as to where the mean is. This actually shows how powerful the martingale inequalities are: we can prove that a distribution is concentrated to its expectation without actually knowing the expectation.

Hoeffding's Inequality

The following theorem states the so-called Hoeffding's inequality. It is a generalized version of the Chernoff bounds. Recall that the Chernoff bounds hold for the sum of independent trials. When the random variables are not trials, the Hoeffding's inequality is useful, since it holds for the sum of any independent random variables whose ranges are bounded.

Hoeffding's inequality
Let , where are independent random variables with for each . Let . Then
Proof.
Define the Doob martingale sequence . Obviously and .

Apply Azuma's inequality for the martingale with respect to , the Hoeffding's inequality is proved.