Information Technology Reference
In-Depth Information
At the
i
th step of the random walk, the state can be described by a probability
distribution vector
x
0 for each
k
and
k
x
k
=
T
, where
x
k
≥
=
(
x
1
,
x
2
,...,
x
n
)
1.
Each
x
k
in this vector denotes the probability of the random walk being at vertex
k
at the
i
th step. We note that any probability vector
x
can be written as
x
u
↥
,
=
u
+
T
where
u
=
(
1
/
n
,
1
/
n
, ...,
1
/
n
)
is the uniform distribution and their difference
u
↥
=
0.
The normalized adjacency matrix
A
is the stochastic matrix that governs this random
walk. If the probability distribution vector at the
i
th step is
x
then at the
x
−
u
is clearly orthogonal to
u
because the inner product
(
u
,
x
−
u
)
=
st
step
(
i
+
1
)
the distribution vector is
A
x
.
Now, the initial distribution vector is
x
T
, where
e
s
=
=
(
e
1
,
e
2
,...,
e
n
)
1 and
e
j
=
s
. Thus, after
i
steps of the randomwalk the probability distribution
is
A
i
x
. Therefore, writing
x
0 for all
j
=
u
↥
we get
=
u
+
A
i
x
A
i
u
↥
.
=
u
+
max
x
↥
1
,
||
x
||=
1
x
T
Ax
, it follows that
Since
ʻ
2
=
A
i
u
↥
||
2
u
↥
)
T
A
2
i
u
↥
)
|≤|
ʻ
2
(
2
i
u
↥
||
2
||
=|
(
G
)
|
||
.
/
√
n
.
u
↥
||
2
u
↥
||≤||
We can bound
||
≤
2, since
||
x
||+||
u
||
,
||
x
|| =
1 and
||
u
|| =
1
4
dn
3
2
dn
3
in Lemma 6.2 gives the bound
e
−
n
.Itfollowsthat
Letting
i
=
|
ʻ
2
(
G
)
|
≤
A
i
x
2
A
i
u
↥
)
||
2
e
−
n
||
−
u
||
=||
≤
.
n
, the above bound implies that each entry of
A
i
x
is at
Since each entry of
u
is 1
/
least 1
/
2
n
. We can conclude that if
t
reachable from
s
then with probability at least
2
dn
3
steps. Consequently, the
probability that the randomwalk visits
t
within 4
dn
4
steps is at least 1
1
/
2
n
the random walk starting at
s
visits
t
within
i
=
2
n
−
(
1
−
1
/
2
n
)
>
1
2 for sufficiently large
n
. This bound on the success probability proves that the
random walk algorithm is indeed an RL algorithm.
/
1.7 Logspace Counting Classes
We now briefly introduce logspace counting classes. These complexity classes
provide a tight classification of many natural computational problems. Formal defin-
itions of these classes and their basic properties can be found in [
BDHM92
,
AO96
].
The central complexity class here is denoted GapL and captures the complexity of
computing the integer determinant.
:
ˇ
∗
ₒ Z
Definition 7.1
GapL is the class of functions
f
, for which there is a
logspace bounded nondeterministic Turing machine
M
such that on input
x
∈
ˇ
∗
,
we have
f
(
x
)
=
acc
M
(
x
)
−
rej
M
(
x
)
, where acc
M
(
x
)
and rej
M
(
x
)
denote the number
