1Percolation

III Percolation and Random Walks on Graphs

1.2 Correlation inequalities

In this section, we are going to prove some useful inequalities and equalities,

and use them to prove some interesting results about

θ

(

p

) and the decay of

P

p

(0 ↔ ∂B

n

).

To motivate our first inequality, suppose we have 4 points

x, y, u, v

, and we

want to ask for the conditional probability

P

p

(x ↔ y | u ↔ v).

Intuitively, we expect this to be greater than

P

p

(

x ↔ y

), since

u ↔ v

tells us

there are some open edges around, which is potentially helpful. The key property

underlying this intuition is that having more edges is beneficial to both of the

events. To quantify this, we need the notion of an increasing random variable.

Again, let

G

= (

V, E

) be a graph and Ω =

{

0

,

1

}

E

. We shall assume that

E

is countable.

Notation (≤). Given ω, ω

0

∈ Ω, we write ω ≤ ω

0

if ω(e) ≤ ω

0

(e) for all e ∈ E.

This defines a partial order on Ω.

Definition

(Increasing random variable)

.

A random variable

X

is increasing if

X(ω) ≤ X(ω

0

) whenever ω ≤ ω

0

, and is decreasing if −X is increasing.

Definition

(Increasing event)

.

An event

A

is increasing (resp. decreasing) if

the indicator 1(A) is increasing (resp. decreasing)

Example. {|C(0)| = ∞} is an increasing event.

An immediate consequence of the definition is that

Theorem. If N is an increasing random variable and p

1

≤ p

2

, then

E

p

1

[N] ≤ E

p

2

[N],

and if an event A is increasing, then

P

p

1

(A) ≤ P

p

2

(A).

Proof. Immediate from coupling.

What we want to prove is the following result, which will be extremely useful.

Theorem

(Fortuin–Kasteleyn–Ginibre (FKG) inequality)

.

Let

X

and

Y

be

increasing random variables with E

p

[X

2

], E

p

[Y

2

] < ∞. Then

E

p

[XY ] ≥ E

p

[X]E

p

[Y ].

In particular, if A and B are increasing events, then

P

p

(A ∩ B) ≥ P

p

(A)P

p

(B).

Equivalently,

P

p

(A | B) ≥ P

p

(A).

Proof.

The plan is to first prove this in the case where

X

and

Y

depend on a

finite number of edges, and we do this by induction. Afterwards, the desired

result can be obtained by an application of the martingale convergence theorem.

In fact, the “real work” happens when we prove it for

X

and

Y

depending on

a single edge. Everything else follows from messing around with conditional

probabilities.

If

X

and

Y

depend only on a single edge

e

1

, then for any

ω

1

, ω

2

∈ {

0

,

1

}

, we

claim that

(X(ω

1

) − X(ω

2

))(Y (ω

1

) − Y (ω

2

)) ≥ 0.

Indeed,

X

and

Y

are both increasing. So if

ω

1

> ω

2

, then both terms are

positive; if

ω < ω

2

, then both terms are negative, and there is nothing to do if

they are equal.

In particular, we have

X

ω

1

,ω

2

∈{0,1}

(X(ω

1

) −X(ω

2

))(Y (ω

1

) − Y (ω

2

))P

p

(ω(e

1

) = ω

1

)P

p

(ω(e

1

) = ω

2

) ≥ 0.

Expanding this, we find that the LHS is 2(

E

p

[

XY

]

− E

p

[

X

]

E

p

[

Y

]), and so we

are done.

Now suppose the claim holds for

X

and

Y

that depend on

n < k

edges. We

shall prove the result when they depend on k edges e

1

, . . . , e

k

. We have

E

p

[XY ] = E

p

[E

p

[XY | ω(e

1

), . . . , ω(e

k−1

)]].

Now after conditioning on

ω

(

e

1

)

, . . . , ω

(

e

k−1

), the random variables

X

and

Y

become increasing random variables of ω(e

k

). Applying the first step, we get

E

p

[XY | ω(e

1

), . . . , ω(e

k−1

)]

≥ E

p

[X | ω(e

1

), . . . , ω(e

k−1

)]E

p

[Y | ω(e

1

), . . . , ω(e

k−1

)]. (∗)

But

E

p

[

X | ω

(

e

1

)

, . . . , ω

(

e

k−1

)] is a random variable depending on the edges

e

1

, . . . , e

k−1

, and moreover it is increasing. So the induction hypothesis tells us

E

p

E

p

[X | ω(e

1

), . . . , ω(e

k−1

)]E

p

[Y | ω(e

1

), . . . , ω(e

k−1

)]

≥ E

p

E

p

[X | ω(e

1

), . . . , ω(e

k−1

)]

E

p

E

p

[Y | ω(e

1

), . . . , ω(e

k−1

)]

Combining this with (the expectation of) (∗) then gives the desired result.

Finally, suppose

X

and

Y

depend on the states of a countable set of edges

e

1

, e

2

, . . .. Let’s define

X

n

= E

p

[X | ω(e

1

), . . . , ω(e

n

)]

Y

n

= E

p

[Y | ω(e

1

), . . . , ω(e

n

)]

Then

X

n

and

Y

n

are martingales, and depend only on the states of only finitely

many edges. So we know that

E

p

[X

n

Y

n

] ≥ E

p

[X

n

]E

p

[Y

n

] = E

p

[X]E

p

[Y ].

By the

L

2

-martingale convergence theorem,

X

n

→ X

,

Y

n

→ Y

in

L

2

and almost

surely. So taking the limit n → ∞, we get

E

p

[XY ] ≥ E

p

[X]E

p

[Y ].

What we want to consider next is the notion of disjoint occurrence. For

example, we want to able to ask the probability that there exists two disjoint

paths connecting a pair of points.

To formulate this disjointness, suppose we have an event

A

, and let

ω ∈ A

.

To ask whether this occurrence of

A

depends only on some set

S ⊆ E

of edges,

we can look at the set

[ω]

S

= {ω

0

∈ Ω : ω

0

(e) = ω(e) for all e ∈ S}.

If [

ω

]

S

⊆ A

, then we can rightfully say this occurrence of

A

depends only on

the edges in

S

. Note that this depends explicitly and importantly on

ω

, i.e. the

“reason”

A

happened. For example, if

A

=

{x ↔ y}

, and

ω ∈ A

, then we can

take

S

to be the set of all edges in a chosen path from

x

to

y

in the configuration

of ω. This choice will be different for different values of ω.

Using this, we can define what it means for two events to occur disjointly.

Definition

(Disjoint occurrence)

.

Let

F

be a set and Ω =

{

0

,

1

}

F

. If

A

and

B

are events, then the event that A and B occurs disjointly is

A ◦ B = {ω ∈ Ω : ∃S ⊆ F s.t. [ω]

S

⊆ A and [ω]

F \S

⊆ B}.

Theorem

(BK inequality)

.

Let

F

be a finite set and Ω =

{

0

,

1

}

F

. Let

A

and

B be increasing events. Then

P

p

(A ◦ B) ≤ P

p

(A)P

p

(B).

This says if

A

and

B

are both events that “needs” edges to occur, then requir-

ing that they occur disjointly is more difficult than them occurring individually.

The proof is completely magical. There exist saner proofs of the inequality,

but they are rather longer.

Proof (Bollob´as and Leader).

We prove by induction on the size

n

of the set

F

.

For n = 0, it is trivial.

Suppose it holds for

n −

1. We want to show it holds for

n

. For

D ⊆ {

0

,

1

}

F

and i = 0, 1, set

D

i

= {(ω

1

, . . . , ω

n−1

) : (ω

1

, . . . , ω

n−1

, i) ∈ D}.

Let A, B ⊆ {0, 1}

F

, and C = A ◦ B. We check that

C

0

= A

0

◦ B

0

, C

1

= (A

0

◦ B

1

) ∪ (A

1

◦ B

0

).

Since

A

and

B

are increasing,

A

0

⊆ A

1

and

B

0

⊆ B

1

, and

A

i

and

B

i

are also

increasing events. So

C

0

⊆ (A

0

◦ B

1

) ∩ (A

1

◦ B

0

)

C

1

⊆ A

1

◦ B

1

.

By the induction hypothesis, we have

P

p

(C

0

) = P

p

(A

0

◦ B

0

) ≤ P

p

(A

0

)P

p

(B

0

)

P

p

(C

1

) ≤ P

p

(A

1

◦ B

1

) ≤ P

p

(A

1

)P

p

(B

1

)

P

p

(C

0

) + P

p

(C

1

) ≤ P

p

((A

0

◦ B

1

) ∩ (A

1

◦ B

0

)) + P

p

((A ◦ B

1

) ∪ (A

1

◦ B

0

))

= P

p

(A

0

◦ B

1

) + P

p

(A

1

◦ B

0

)

≤ P

p

(A

0

)P

p

(B

1

) + P

p

(A

1

)P

p

(B

0

).

Now note that for any D, we have

P

p

(D) = pP

p

(D

1

) + (1 − p)P

p

(D

0

).

By some black magic, we multipy the first inequality by (1

− p

)

2

, the second by

p

2

and the third by p(1 − p). This gives

pP

p

(C

1

) + (1−p)P

p

(C

0

) ≤ (pP

p

(A

1

) + (1 −p)P

p

(A

0

))(pP

p

(B

1

) + (1 −p)P

p

(B

0

)).

Expand and we are done.

It turns out the increasing hypothesis is not necessary:

Theorem

(Reimer)

.

For all events

A, B

depending on a finite set, we have

P

p

(A ◦ B) ≤ P

p

(A)P

p

(B).

But the proof is much harder, and in all the case where we want to apply

this, the variables are increasing.

As an application of the BK inequality, we first prove a preliminary result

about the decay of

P

p

(0

↔ ∂B

(

n

)). To prove our result, we will need a stronger

condition than p < p

c

. Recall that we defined

θ(p) = P

p

(|C(0)| = ∞).

We also define

χ(p) = E

p

[|C(0)|].

If χ(p) is finite, then of course θ(p) = 0. However, the converse need not hold.

Theorem.

If

χ

(

p

)

< ∞

, then there exists a positive constant

c

such that for all

n ≥ 1,

P

p

(0 ↔ ∂B(n)) ≤ e

−cn

.

Later, we will show that in fact this holds under the assumption that

p < p

c

.

However, that requires a bit more technology, which we will develop after this

proof.

The idea of the proof is that if we want a path from, say, 0 to

B

(2

n

), then

the path must hit a point on

∂B

(

n

). So there is a path from 0 to a point on

∂B

(

n

), and a path from that point to

∂B

(2

n

). Moreover, these two paths are

disjoint, which allows us to apply the BK inequality.

Proof. Let

X

n

=

X

x∈∂B(n)

1(0 ↔ x).

Now consider

∞

X

n=0

E[X

n

] =

X

n

X

x∈∂B(n)

P

p

(0 ↔ x) =

X

x∈Z

d

P

p

(0 ↔ x) = χ(p).

Since

χ

(

p

) is finite, we in particular have

E

p

[

X

n

]

→

0 as

n → ∞

. Take

m

large

enough such that E

p

[X

m

] < δ < 1.

Now we have

P

p

(0 ↔ ∂B(m + k)) = P

p

(∃x ∈ ∂B(m) : 0 ↔ x and x ↔ ∂B(m + k) disjointly)

≤

X

x∈∂B(m)

P

p

(0 ↔ x)P

p

(x ↔ ∂B(m + k)) (BK)

≤

X

x∈∂B(m)

P

p

(0 ↔ x)P

p

(0 ↔ ∂B(k)) (trans. inv.)

≤ P

p

(0 ↔ B(k))E

p

[X

m

].

So for any

n > m

, write

n

=

qm

+

r

, where

r ∈

[0

, m −

1]. Then iterating the

above result, we have

P

p

(0 ↔ ∂B(n)) ≤ P

p

(0 ↔ B(mq)) ≤ δ

q

≤ δ

−1+

n

m

≤ e

−cn

.

To replace the condition with the weaker condition

p < p

c

, we need to

understand how

θ

(

p

) changes with

p

. We know

θ

(

p

) is an increasing function in

p

. It would be great if it were differentiable, and even better if we could have an

explicit formula for

dθ

dp

.

To do so, suppose we again do coupling, and increase

p

by a really tiny bit.

Then perhaps we would expect that exactly one of the edges switches from being

closed to open. Thus, we want to know if the state of this edge is pivotal to the

event |C(0)| = ∞, and this should determine the rate of change of θ.

Definition

(Pivotal edge)

.

Let

A

be an event and

ω

a percolation configuration.

The edge e is pivotal for (A, ω) if

1(ω ∈ A) 6= 1(ω

0

∈ A),

where ω

0

is defined by

ω

0

(f) =

(

ω(f) f 6= e

1 − ω(f) f = e

.

The event that

e

is pivotal for

A

is defined to be the set of all

ω

such that

e

is

pivotal for (A, ω).

Note that whether or not e is pivotal for (A, ω) is independent of ω(e).

Theorem

(Russo’s formula)

.

Let

A

be an increasing event that depends on the

states of a finite number of edges. Then

d

dp

P

p

(A) = E

p

[N(A)],

where N(A) is the number of pivotal edges for A.

Proof.

Assume that

A

depends the states of

m

edges

e

1

, . . . , e

m

. The idea is to

let each

e

i

be open with probability

p

i

, whree the

{p

i

}

may be distinct. We then

vary the p

i

one by one and see what happens.

Writing ¯p = (p

1

, . . . , p

m

), we define

f(p

1

, . . . , p

m

) = P

¯p

(A),

Now

f

is the sum of the probability of all configurations of

{e

1

, . . . , e − m}

for

which

A

happens, and is hence a finite sum of polynomials. So in particular, it

is differentaible.

We now couple all percolation process. Let (

X

(

e

) :

e ∈ L

d

) be iid

U

[0

,

1]

random variables. For a vector ¯p = (p(e) : e ∈ L

d

), we write

η

¯p

(e) = 1(X(e) ≤ p(e)).

Then we have P

¯p

(A) = P(η

¯p

∈ A).

Fix an edge

f

and let

¯p

0

= (

p

0

(

e

)) be such that

p

0

(

e

) =

p

(

e

) for all

e 6

=

f

, and

p

0

(f) = p(f) + δ for some δ > 0. Then

P

¯p

0

(A) − P

¯p

(A) = P(η

¯p

0

∈ A) − P(η

¯p

∈ A)

= P(η

¯p

0

∈ A, η

¯p

∈ A) + P(η

¯p

0

∈ A, η

¯p

∈ A) − P(η

¯p

∈ A).

But we know

A

is increasing, so

P

(

η

¯p

0

∈ A, η

¯p

∈ A

) =

P

(

η

¯p

∈ A

). So the first

and last terms cancel, and we have

P

¯p

0

(A) − P

¯p

(A) = P(η

¯p

0

∈ A, η

¯p

6∈ A).

But we observe that we simply have

P(η

¯p

0

∈ A, η

¯p

6∈ A) = δ · P

¯p

(f is pivotal for A).

Indeed, we by definition of pivotal edges, we have

P(η

¯p

0

∈ A, η

¯p

6∈ A) = P

¯p

(f is pivotal for A, p(f ) < X(f ) ≤ p(f ) + δ).

Since the event

{f is pivotal for A}

is independent of the state of the edge

f

,

we obtain

P

¯p

(f is pivotal, p(f ) < X(f ) ≤ p(f ) + δ) = P

¯p

(f is pivotal) · δ.

Therefore we have

∂

∂p(f)

P

¯p

(A) = lim

δ→0

P

¯p

0

(A) − P

¯p

(A)

δ

= P

¯p

(f is pivotal for A).

The desired result then follows from the chain rule:

d

dp

P

p

(A) =

m

X

i=1

∂

∂p(e

i

)

P

¯p

(A)

¯p=(p,...,p)

=

m

X

i=1

P

p

(e

i

is pivotal for A)

= E

p

[N(A)].

If

A

depends on an infinite number of edges, then the best we can say is that

lim inf

δ↓0

P

p+δ

(A) − P

p

(A)

δ

≥ E

p

[N(A))].

To see this, again set B(n) = [−n, n]

d

∩ Z

d

. Define ¯p

n

by

¯p

n

(e) =

(

p e 6∈ B(n)

p + δ e ∈ B(n)

.

Then since a is increasing, we know

P

p+δ

(A) − P

p

(A)

δ

≥

P

¯p

n

(A) − P

p

(A)

δ

.

We can then apply the previous claim, take successive differences, and take

n → ∞.

Corollary.

Let

A

be an increasing event that depends on

m

edges. Let

p ≤ q ∈

[0, 1]. Then P

q

(A) ≤ P

p

(A)

q

p

m

.

Proof.

We know that

{f is pivotal for A}

is independent of the state of

f

, and

so

P

p

(ω(f) = 1, f is pivotal for A) = pP

p

(f is pivotal for A).

But since

A

is increasing, if

ω

(

f

) = 1 and

f

is pivotal for

A

, then

A

occurs.

Conversely, if f is pivotal and A occurs, then ω(f) = 1.

Thus, by Russo’s formula, we have

d

dp

P

p

(A) = E

p

[N(A)]

=

X

e

P

p

(e is pivotal for A)

=

X

e

1

p

P

p

(ω(e) = 1, e is pivotal for A)

=

X

e

1

p

P

p

(e is pivotal | A)P

p

(A)

= P

p

(A)

1

p

E

p

[N(A) | A].

So we have

d

dp

P

p

(A)

P

p

(A)

=

1

p

E

p

[N(A) | A].

Integrating, we find that

log

P

q

(A)

P

p

(A)

=

Z

q

p

1

u

E

u

[N(A) | A] du.

Bounding E

u

[N(A) | A] ≤ m, we obtain the desired bound.

With Russo’s formula, we can now prove the desired theorem.

Theorem. Let d ≥ 2 and B

n

= [−n, n]

d

∩ Z

d

.

(i)

If

p < p

c

, then there exists a positive constant

c

for all

n ≥

1,

P

p

(0

↔

∂B

n

) ≤ e

−cn

.

(ii) If p > p

c

, then

θ(p) = P

p

(0 ↔ ∞) ≥

p − p

c

p(1 − p

c

)

.

This was first proved by Aizenman and Barsky who looked at the more

general framework of long-range percolation. Menshikov gave an alternative

proof by analyzing the geometry of pivotal edges. The proof we will see is by

Duminil-Copin and Tassion. Recall that we defined

χ(p) = E

p

[|C(0)|].

We saw that if

χ

(

p

)

< ∞

, then

P

p

(0

↔ ∂B

n

)

≤ e

−cn

. We now see that

χ

(

p

)

< ∞

iff p < p

c

.

The strategy of the proof is to define a new percolation probability

˜p

c

, whose

definition makes it easier to prove the theorem. Once we have established the

two claims, we see that (i) forces ˜p

c

≤ p

c

, and (ii) forces ˜p

c

≥ p

c

. So they must

be equal.

Proof (Duminil-Copin and Tassion). If S ⊆ V is finite, we write

∂S = {(x, y) ∈ E : x ∈ S, y 6∈ S}.

We write

x

S

↔ y

if there exists an open path of edges from

x

to

y

all of whose

end points lie in S.

Now suppose that 0 ∈ S. We define

ϕ

p

(S) = p

X

(x,y)∈∂S

P

p

(0

S

↔ x).

Define

˜p

c

= sup{p ∈ [0, 1] : exists a finite set S with 0 ∈ S and ϕ

p

(S) < 1}.

Claim. It suffices to prove (i) and (ii) with p

c

replaced by ˜p

c

.

Indeed, from (i), if

p < ˜p

c

, then

P

p

(0

↔ ∂B

n

)

≤ e

−cn

. So taking the limit

n → ∞

, we see

θ

(

p

) = 0. So

˜p

c

≤ p

c

. From (ii), if

p > ˜p

c

, then

θ

(

p

)

>

0. So

p

c

≤ ˜p

c

. So p

c

= ˜p

c

.

We now prove (i) and (ii):

(i)

Let

p < ˜p

c

. Then there exists a finite set

S

containing 0 with

ϕ

p

(

S

)

<

1.

Since

S

is finite, we can pick

L

large enough so that

S ⊆ B

L−1

. We will

prove that P

p

(0 ↔ ∂B

kL

) ≤ (ϕ

p

(S))

k−1

for k ≥ 1.

Define C = {x ∈ S : 0

S

↔ x}. Since S ⊆ B

L−1

, we know S ∩ ∂B

kL

= ∅.

Now if we have an open path from 0 to

∂B

kL

, we let

x

be the last element

on the path that lies in

C

. We can then replace the path up to

x

by a path

that lies entirely in

S

, by assumption. This is then a path that lies in

C

up

to

x

, then takes an edge on

∂S

, and then lies entirely outside of

C

c

. Thus,

P

p

(0 ↔ ∂B

kL

) ≤

X

A⊆S

0∈A

X

(x,y)∈∂A

P

p

(0

A

↔ x, (x, y) open, C = A, y

A

C

↔ ∂B

kL

).

Now observe that the events

{C

=

A,

0

S

↔ x}

,

{

(

x, y

)

is open}

and

{y

A

c

↔

∂B

kL

} are independent. So we obtain

P

p

(0 ↔ ∂B

kL

) ≤

X

A⊆S,0∈A

X

(x,y)∈∂S

p P

p

(0

S

↔ x, C = A) P

p

(y

A

c

↔ ∂B

kL

).

Since we know that y ∈ B

L

, we can bound

P

p

(y

A

c

↔ ∂B

kL

) ≤ P

p

(0 ↔ ∂B

(k−1)L

).

So we have

P

p

(0 ↔ ∂B

kL

) ≤ p P

p

(0 ↔ ∂B

(k−1)L

)

X

A⊆S,0∈A

X

(x,y)∈∂S

P

p

(0

S

↔ x, C = A)

= P

p

(0 ↔ ∂B

(k−1)L

) p

X

(x,y)∈∂S

P

p

(0

S

↔ x)

= P

p

(0 ↔ ∂B

(k−1)L

)ϕ

p

(S).

Iterating, we obtain the deseired result.

(ii) We want to use Russo’s formula. We claim that it suffices to prove that

d

dp

P

p

(0 ↔ ∂B

n

) ≥

1

p(1 − p)

inf

S⊆B

n

,0∈S

ϕ

p

(S)(1 − P

p

(0 ↔ ∂B

n

)).

Indeed, if

p > ˜p

c

, we integrate from

˜p

c

to

p

, use in this range

ϕ

p

(

S

)

≥

1,

and then take the limit as n → ∞.

The event

{

0

↔ ∂B

n

}

is increasing and only dependson a finite number of

edges. So we can apply Russo’s formula

d

dp

P

p

(0 ↔ ∂B

n

) =

X

e∈B

n

P

p

(e is pivotal for {0 ↔ ∂B

n

})

Since being pivotal and being open/closed are independent, we can write

this as

=

X

e∈B

n

1

1 − p

P

p

(e is pivotal for {0 ↔ ∂B

n

}, e is closed)

=

X

e∈B

n

1

1 − p

P

p

(e is pivotal for {0 ↔ ∂B

n

}, 0 6↔ ∂B

n

)

Define S = {x ∈ B

n

: x 6↔ ∂B

n

}. Then {0 6↔ ∂B

n

} implies 0 ∈ S. So

d

dp

P

p

(0 ↔ ∂B

n

) =

1

1 − p

X

e∈B

n

X

A⊆B

n

,0∈A

P

p

(e is pivotal, S = A)

Given that

S

=

A

, an edge

e

= (

x, y

) is pivotal iff

e ∈ ∂A

and 0

A

↔ x

. So

we know

d

dp

P

p

(0 ↔ ∂B

n

) =

1

1 − p

X

A⊆B

n

,0∈A

X

(x,y)∈∂A

P

p

(0

A

↔ x, S = A).

Observe that

{

0

A

↔ x}

and

{S

=

A}

are independent, since to determine if

S

=

A

, we only look at the edges on the boundary of

A

. So the above is

equal to

1

1 − p

X

A⊆B

n

,0∈A

X

(x,y)∈∂A

P

p

(0

A

↔ x)P

p

(S = A)

=

1

p(1 − p)

X

A⊆B

n

,0∈A

ϕ

p

(A)P

p

(S = A)

≥

1

p(1 − p)

inf

S⊆B

n

,0∈S

ϕ

P

(S)P

p

(0 6↔ ∂B

n

),

as desired.

We might ask if

P

p

(0

↔ ∂B

n

)

≤ e

−cn

is the best convergence rate when

p < p

c

, but we cannot do better, since P

p

(0 ↔ ∂B

n

) ≥ p

n

.

Also, if p < p

c

, then we can easily bound

P

p

(|C(0)| ≥ n) ≤ P

p

(0 ↔ ∂B

n

1/d

) ≤ exp(−cn

1/d

).

However, this is not a good bound. In fact,

n

1/d

can be replaced by

n

, but we

will not prove it here. This tells us the largest cluster in

B

n

will have size of

order log n with high probability.