随机算法 (Spring 2014)/Moment and Deviation
Tail Inequalities
When applying probabilistic analysis, we often want a bound in form of for some random variable (think that is a cost such as running time of a randomized algorithm). We call this a tail bound, or a tail inequality.
Besides directly computing the probability , we want to have some general way of estimating tail probabilities from some measurable information regarding the random variables.
Markov's Inequality
One of the most natural information about a random variable is its expectation, which is the first moment of the random variable. Markov's inequality draws a tail bound for a random variable from its expectation.
Theorem (Markov's Inequality) - Let be a random variable assuming only nonnegative values. Then, for all ,
- Let be a random variable assuming only nonnegative values. Then, for all ,
Proof. Let be the indicator such that It holds that . Since is 0-1 valued, . Therefore,
Example (from Las Vegas to Monte Carlo)
Let be a Las Vegas randomized algorithm for a decision problem , whose expected running time is within on any input of size . We transform to a Monte Carlo randomized algorithm with bounded one-sided error as follows:
- :
- Run for long where is the size of .
- If returned within time, then return what just returned, else return 1.
Since is Las Vegas, its output is always correct, thus only errs when it returns 1, thus the error is one-sided. The error probability is bounded by the probability that runs longer than . Since the expected running time of is at most , due to Markov's inequality,
thus the error probability is bounded.
Generalization
For any random variable , for an arbitrary non-negative real function , the is a non-negative random variable. Applying Markov's inequality, we directly have that
This trivial application of Markov's inequality gives us a powerful tool for proving tail inequalities. With the function which extracts more information about the random variable, we can prove sharper tail inequalities.
Variance
Definition (variance) - The variance of a random variable is defined as
- The standard deviation of random variable is
- The variance of a random variable is defined as
We have seen that due to the linearity of expectations, the expectation of the sum of variable is the sum of the expectations of the variables. It is natural to ask whether this is true for variances. We find that the variance of sum has an extra term called covariance.
Definition (covariance) - The covariance of two random variables and is
- The covariance of two random variables and is
We have the following theorem for the variance of sum.
Theorem - For any two random variables and ,
- Generally, for any random variables ,
- For any two random variables and ,
Proof. The equation for two variables is directly due to the definition of variance and covariance. The equation for variables can be deduced from the equation for two variables.
We will see that when random variables are independent, the variance of sum is equal to the sum of variances. To prove this, we first establish a very useful result regarding the expectation of multiplicity.
Theorem - For any two independent random variables and ,
- For any two independent random variables and ,
Proof.
With the above theorem, we can show that the covariance of two independent variables is always zero.
Theorem - For any two independent random variables and ,
- For any two independent random variables and ,
Proof.
We then have the following theorem for the variance of the sum of pairwise independent random variables.
Theorem - For pairwise independent random variables ,
- For pairwise independent random variables ,
- Remark
- The theorem holds for pairwise independent random variables, a much weaker independence requirement than the mutual independence. This makes the variance-based probability tools work even for weakly random cases. We will see what it exactly means in the future lectures.
Variance of binomial distribution
For a Bernoulli trial with parameter .
The variance is
Let be a binomial random variable with parameter and , i.e. , where 's are i.i.d. Bernoulli trials with parameter . The variance is
Chebyshev's inequality
With the information of the expectation and variance of a random variable, one can derive a stronger tail bound known as Chebyshev's Inequality.
Theorem (Chebyshev's Inequality) - For any ,
- For any ,
Proof. Observe that Since is a nonnegative random variable, we can apply Markov's inequality, such that
Median Selection
The selection problem is the problem of finding the th smallest element in a set . A typical case of selection problem is finding the median.
Definition - The median of a set is the th element in the sorted order of .
The median can be found in time by sorting. There is a linear-time deterministic algorithm, "median of medians" algorithm, which is quite sophisticated. Here we introduce a much simpler randomized algorithm which also runs in linear time.
The LazySelect algorithm
We introduce a randomized median selection algorithm called LazySelect, which is a variant on a randomized algorithm due to Floyd and Rivest
The idea of this algorithm is random sampling. For a set , let denote the median. We observe that if we can find two elements satisfying the following properties:
- The median is between and in the sorted order, i.e. ;
- The total number of elements between and is small, specially for , .
Provided and with these two properties, within linear time, we can compute the ranks of and in , construct , and sort . Therefore, the median of can be picked from in linear time.
So how can we select such elements and from ? Certainly sorting would give us the elements, but isn't that exactly what we want to avoid in the first place?
Observe that and are only asked to roughly satisfy some constraints. This hints us maybe we can construct a sketch of which is small enough to sort cheaply and roughly represents , and then pick and from this sketch. We construct the sketch by randomly sampling a relatively small number of elements from . Then the strategy of algorithm is outlined by:
- Sample a set of elements from .
- Sort and choose and somewhere around the median of .
- If and have the desirable properties, we can compute the median in linear time, or otherwise the algorithm fails.
The parameters to be fixed are: the size of (small enough to sort in linear time and large enough to contain sufficient information of ); and the order of and in (not too close to have between them, and not too far away to have sortable in linear time).
We choose the size of as , and and are within range around the median of .
LazySelect Input: a set of elements over totally ordered domain.
- Pick a multi-set of elements in , chosen independently and uniformly at random with replacement, and sort .
- Let be the -th smallest element in , and let be the Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \left\lceil\frac{1}{2}n^{3/4}+\sqrt{n}\right\rceil} -th smallest element in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle R} .
- Construct Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle C=\{x\in S\mid d\le x\le u\}} and compute the ranks Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle r_d=|\{x\in S\mid x<d\}|} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle r_u=|\{x\in S\mid x<u\}|} .
- If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle r_d>\frac{n}{2}} or Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle r_u<\frac{n}{2}} or Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |C|>4n^{3/4}} then return FAIL.
- Sort Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle C} and return the Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \left(\left\lfloor\frac{n}{2}\right\rfloor-r_d+1\right)} th element in the sorted order of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle C} .
"Sample with replacement" (有放回采样) means that after sampling an element, we put the element back to the set. In this way, each sampled element is independently and identically distributed (i.i.d) (独立同分布). In the above algorithm, this is for our convenience of analysis.
Analysis
The algorithm always terminates in linear time because each line of the algorithm costs at most linear time. The last three line guarantees that the algorithm returns the correct median if it does not fail.
We then only need to bound the probability that the algorithm returns a FAIL. Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle m\in S} be the median of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S} . By Line 4, we know that the algorithm returns a FAIL if and only if at least one of the following events occurs:
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{E}_1: Y=|\{x\in R\mid x\le m\}|<\frac{1}{2}n^{3/4}-\sqrt{n}} ;
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{E}_2: Z=|\{x\in R\mid x\ge m\}|<\frac{1}{2}n^{3/4}-\sqrt{n}} ;
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{E}_3: |C|>4n^{3/4}} .
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{E}_3} directly follows the third condition in Line 4. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{E}_1} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{E}_2} are a bit tricky. The first condition in Line 4 is that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle r_d>\frac{n}{2}} , which looks not exactly the same as Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{E}_1} , but both Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{E}_1} and that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle r_d>\frac{n}{2}} are equivalent to the same event: the Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \left\lfloor\frac{1}{2}n^{3/4}-\sqrt{n}\right\rfloor} -th smallest element in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle R} is greater than Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle m} , thus they are actually equivalent. Similarly, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{E}_2} is equivalent to the second condition of Line 4.
We now bound the probabilities of these events one by one.
Lemma 1 - Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \Pr[\mathcal{E}_1]\le \frac{1}{4}n^{-1/4}} .
Proof. Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle X_i} be the Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle i} th sampled element in Line 1 of the algorithm. Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle Y_i} be a indicator random variable such that - Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle Y_i= \begin{cases} 1 & \mbox{if }X_i\le m,\\ 0 & \mbox{otherwise.} \end{cases} }
It is obvious that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle Y=\sum_{i=1}^{n^{3/4}}Y_i} , where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle Y} is as defined in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{E}_1} . For every Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle X_i} , there are Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \left\lceil\frac{n}{2}\right\rceil} elements in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S} that are less than or equal to the median. The probability that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle Y_i=1} is
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle p=\Pr[Y_i=1]=\Pr[X_i\le m]=\frac{1}{n}\left\lceil\frac{n}{2}\right\rceil, }
which is within the range of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \left[\frac{1}{2},\frac{1}{2}+\frac{1}{2n}\right]} . Thus
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathbf{E}[Y]=n^{3/4}p\ge \frac{1}{2}n^{3/4}. }
The event Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{E}_1} is defined as that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle Y<\frac{1}{2}n^{3/4}-\sqrt{n}} .
Note that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle Y_i} 's are Bernoulli trials, and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle Y} is the sum of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle n^{3/4}} Bernoulli trials, which follows binomial distribution with parameters Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle n^{3/4}} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle p} . Thus, the variance is
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathbf{Var}[Y]=n^{3/4}p(1-p)\le \frac{1}{4}n^{3/4}. }
Applying Chebyshev's inequality,
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \begin{align} \Pr[\mathcal{E}_1] &= \Pr\left[Y<\frac{1}{2}n^{3/4}-\sqrt{n}\right]\\ &\le \Pr\left[|Y-\mathbf{E}[Y]|>\sqrt{n}\right]\\ &\le \frac{\mathbf{Var}[Y]}{n}\\ &\le\frac{1}{4}n^{-1/4}. \end{align} }
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \square}
By a similar analysis, we can obtain the following bound for the event Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{E}_2} .
Lemma 2 - Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \Pr[\mathcal{E}_2]\le \frac{1}{4}n^{-1/4}} .
We now bound the probability of the event Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{E}_3} .
Lemma 3 - Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \Pr[\mathcal{E}_3]\le \frac{1}{2}n^{-1/4}} .
Proof. The event Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{E}_3} is defined as that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |C|>4 n^{3/4}} , which by the Pigeonhole Principle, implies that at leas one of the following must be true: - Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{E}_3'} : at least Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle 2n^{3/4}} elements of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle C} is greater than Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle m} ;
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{E}_3''} : at least Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle 2n^{3/4}} elements of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle C} is smaller than Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle m} .
We bound the probability that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{E}_3'} occurs; the second will have the same bound by symmetry.
Recall that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle C} is the region in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S} between Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle d} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle u} . If there are at least Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle 2n^{3/4}} elements of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle C} greater than the median Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle m} of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S} , then the rank of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle u} in the sorted order of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S} must be at least Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \frac{1}{2}n+2n^{3/4}} and thus Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle R} has at least Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \frac{1}{2}n^{3/4}-\sqrt{n}} samples among the Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \frac{1}{2}n-2n^{3/4}} largest elements in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S} .
Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle X_i\in\{0,1\}} indicate whether the Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle i} th sample is among the Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \frac{1}{2}n-2n^{3/4}} largest elements in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S} . Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle X=\sum_{i=1}^{n^{3/4}}X_i} be the number of samples in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle R} among the Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \frac{1}{2}n-2n^{3/4}} largest elements in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S} . It holds that
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle p=\Pr[X_i=1]=\frac{\frac{1}{2}n-2n^{3/4}}{n}=\frac{1}{2}-2n^{-1/4}} .
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle X} is a binomial random variable with
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathbf{E}[X]=n^{3/4}p=\frac{1}{2}n^{3/4}-2\sqrt{n}, }
and
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathbf{Var}[X]=n^{3/4}p(1-p)=\frac{1}{4}n^{3/4}-4n^{1/4}<\frac{1}{4}n^{3/4}. }
Applying Chebyshev's inequality,
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \begin{align} \Pr[\mathcal{E}_3'] &= \Pr\left[X\ge\frac{1}{2}n^{3/4}-\sqrt{n}\right]\\ &\le \Pr\left[|X-\mathbf{E}[X]|\ge\sqrt{n}\right]\\ &\le \frac{\mathbf{Var}[X]}{n}\\ &\le\frac{1}{4}n^{-1/4}. \end{align} }
Symmetrically, we have that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \Pr[\mathcal{E}_3'']\le\frac{1}{4}n^{-1/4}} .
Applying the union bound
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \Pr[\mathcal{E}_3]\le \Pr[\mathcal{E}_3']+\Pr[\mathcal{E}_3'']\le\frac{1}{2}n^{-1/4}. }
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \square}
Combining the three bounds. Applying the union bound to them, the probability that the algorithm returns a FAIL is at most
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \Pr[\mathcal{E}_1]+\Pr[\mathcal{E}_2]+\Pr[\mathcal{E}_3]\le n^{-1/4}. }
Therefore the algorithm always terminates in linear time and returns the correct median with high probability.
Erdős–Rényi Random Graphs
Consider a graph Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle G(V,E)} which is randomly generated as:
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |V|=n} ;
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \forall \{u,v\}\in{V\choose 2}} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle uv\in E} independently with probability Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle p} .
Such graph is denoted as Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle G(n,p)} . This is called the Erdős–Rényi model or Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle G(n,p)} model for random graphs.
Informally, the presence of every edge of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle G(n,p)} is determined by an independent coin flipping (with probability of HEADs Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle p} ).
Monotone properties
A graph property is a predicate of graph which depends only on the structure of the graph.
Definition - Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{G}_n=2^{V\choose 2}} , where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |V|=n} , be the set of all possible graphs on Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle n} vertices. A graph property is a boolean function Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle P:\mathcal{G}_n\rightarrow\{0,1\}} which is invariant under permutation of vertices, i.e. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle P(G)=P(H)} whenever Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle G} is isomorphic to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle H} .
We are interested in the monotone properties, i.e., those properties that adding edges will not change a graph from having the property to not having the property.
Definition - A graph property Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle P} is monotone if for any Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle G\subseteq H} , both on Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle n} vertices, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle G} having property Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle P} implies Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle H} having property Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle P} .
By seeing the property as a function mapping a set of edges to a numerical value in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \{0,1\}} , a monotone property is just a monotonically increasing set function.
Some examples of monotone graph properties:
- Hamiltonian;
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle k} -clique;
- contains a subgraph isomorphic to some Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle H} ;
- non-planar;
- chromatic number Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle >k} (i.e., not Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle k} -colorable);
- girth Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle <\ell} .
From the last two properties, you can see another reason that the Erdős theorem is unintuitive.
Some examples of non-monotone graph properties:
- Eulerian;
- contains an induced subgraph isomorphic to some Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle H} ;
For all monotone graph properties, we have the following theorem.
Theorem - Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle P}
be a monotone graph property. Suppose Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle G_1=G(n,p_1)}
, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle G_2=G(n,p_2)}
, and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle 0\le p_1\le p_2\le 1}
. Then
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \Pr[P(G_1)]\le \Pr[P(G_2)]} .
- Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle P}
be a monotone graph property. Suppose Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle G_1=G(n,p_1)}
, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle G_2=G(n,p_2)}
, and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle 0\le p_1\le p_2\le 1}
. Then
Although the statement in the theorem looks very natural, it is difficult to evaluate the probability that a random graph has some property. However, the theorem can be very easily proved by using the idea of coupling, a proof technique in probability theory which compare two unrelated random variables by forcing them to be related.
Proof. For any Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \{u,v\}\in{[n]\choose 2}} , let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle X_{\{u,v\}}} be independently and uniformly distributed over the continuous interval Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle [0,1]} . Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle uv\in G_1} if and only if Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle X_{\{u,v\}}\in[0,p_1]} and let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle uv\in G_2} if and only if Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle X_{\{u,v\}}\in[0,p_2]} .
It is obvious that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle G_1\sim G(n,p_1)\,} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle G_2\sim G(n,p_2)\,} . For any Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \{u,v\}} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle uv\in G_1} means that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle X_{\{u,v\}}\in[0,p_1]\subseteq [0,p_2]} , which implies that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle uv\in G_2} . Thus, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle G_1\subseteq G_2} .
Since Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle P} is monotone, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle P(G_1)=1} implies . Thus,
- .