Cryptography Reference
In-Depth Information
Next we provide a (sketch of a) formal analysis that closely follows the fore-
going intuition. Unfortunately, this simple analysis only establishes a weaker
bound than the one claimed. This weaker bound does not suffice for our purposes,
since it is meaningful only for
1
4
µ
≥
(whereas we also need to relate to much
smaller values of
µ
, specifically, 1
/µ
, being poly-logarithmic in the size of the
graph).
Proof sketch for a weaker bound:
Let us denote by
M
the stochastic matrix
representing a random step on the graph
G
=
(
V
,
E
), and let
ρ
denote a bound on
the absolute value of the second largest eigenvalue of
M
(where the largest eigenvalue
is 1). Let
P
be a 0-1 “sieving matrix” that has 1-entries only on its diagonal and further-
more only in entries (
i
S
. We represent (residual) probability
distributions, over
V
, by vectors. For such a vector
v
, the vector
M
v
represents the
distribution obtained from the distribution
,
i
) that correspond to
i
∈
v
by taking one random step on the graph
G
,
and
P
v
v
by setting to zero all entries that
correspond to vertices in
S
. We represent the uniform distribution over
V
by the vector
π
is the (residual) distribution obtained from
(in which each entry equals 1
/
|
V
|
) and observe that
M
π
=
π
(since the uniform
distribution is the eigenvector associated with the eigenvalue 1).
One key observation is that the probability that a random
t
-step walk does not pass
through
S
equals the sum of the elements of the (non-negative) vector (
PM
)
t
−
1
P
π
=
(
PM
)
t
. Since the vector (
PM
)
t
π
π
is non-negati
ve,
we can evaluate its
L
1
-norm in-
stead, which in turn is bounded from above by
√
|
V
|·
(
PM
)
t
π
, where
·
denotes
the Euclidean norm (i.e.,
L
2
-norm). Later, we shall prove that for every vector
z
it
2
)
1
/
2
holds that
PMz
≤
((1
−
µ
)
+
ρ
·
z
, and we obtain
π
≤
(1
2
t
/
2
·
π
=
(1
2
t
/
2
1
(
PM
)
t
−
µ
+
ρ
−
µ
+
ρ
·
|
V
|·
)
)
|
V
|
2
It follows that the probability that a random
t
-step walk does not pass through
S
is
at most
(1
2
t
/
2
, which for
2
−
µ
)
+
ρ
µ
≥
2
ρ
(e.g.,
µ
≥
1
/
2 and
ρ
≤
1
/
2) yields an
upper bound of (1
−
0
.
5
·
µ
)
t
/
2
.
In order to prove that
2
)
1
/
2
z
2
such
that
z
1
is the component of
z
that is in the direction of the first eigenvector
(i.e.,
π
), and
PM
z
≤
((1
−
µ
)
+
ρ
·
z
, we write
z
=
z
1
+
π
=
√
1
z
2
is the component that is orthogonal to it. Using
M
π
=
π
,
P
−
µ
·
π
,
Mz
2
≤
ρ
·
z
2
, and
P
v
≤
v
(for every
v
), we have
PM
(
z
1
+
z
2
)
≤
PMz
1
+
PMz
2
≤
1
−
µ
·
z
1
+
ρ
·
z
2
(1
−
µ
)
+
ρ
≤
2
·
z
1
2
+
z
2
2
=
(1
−
µ
)
+
ρ
2
1
/
2
·
z
1
+
z
2
where the last inequality uses the Cauchy-Schwarz inequality (i.e.,
i
a
i
·
b
i
≤
i
a
i
1
/
2
·
i
b
i
1
/
2
), and the last equality uses the fact that
z
1
and
z
2
are
orthogonal.
We comment that the lower bound claimed in the lemma can be generalized to
1
−
(1
−
µ
+
µ
·
ρ
)
t
, where
ρ
is an upper bound on the eigenvalue ratio.
