Information Technology Reference
In-Depth Information
We are now ready to compute the distribution of the number of even in-degree
vertices for any connected graph.
Theorem 4.
Suppose that G is a connected graph on d vertices and m
1
edges.
Let E
d
,
m
be the number of even in-degree vertices after a random orientation on
the edges. Then E
d
,
m
has the probability distribution of a Bin
≥
d
−
(
d
)
random variable
(
)
−
conditional on the event that the outcome of Bin
d
has the parity of m
d. To be
more precise,
d
k
1
2
d
−
1
,
P[
E
d
,
m
=
k
]=
where k runs over the odd integers up to d, if m
−
d is odd and over the even integers
if m
−
d is even.
Proof.
Fix some spanning tree,
T
,of
G
and toss the coins corresponding to the
edges that do not belong to
T
. Enumerate the vertices of the tree
v
1
,
v
2
,...,
v
d
and
the edges
e
1
,
e
d
−
1
in
that order. The enumeration on the vertices and edges gives that once the coin
e
j
is flipped, then the parity of vertex
v
j
is determined. Lemma
11
gives that once
the parity of some vertex
v
j
is determined, the parity of the next vertex
v
j
+
1
is
independent of the parity of
v
1
,
e
2
,...,
e
d
−
1
as in Lemma
12
. Now toss the coins
e
1
,
e
2
,...,
v
j
−
1
. Only the parity of
v
d
is deterministic
given the parities of the previous vertices. Thus, if we set
v
2
,...,
deg
−
(
δ
i
:
=
v
i
)
mod 2, for
i
=
1
,
2
,...,
d
, we have that each
δ
i
is distributed as a Bin
(
1
)
random variable which,
d
−
1
by independence, means that
.Let
O
d
,
m
be the number of odd
in-degree vertices. Then
O
d
,
m
=
δ
1
+
···
+
δ
d
−
1
+
δ
d
∼
∑
δ
i
∼
Bin
(
d
−
1
)
i
=
1
X
+
δ
d
,where
X
∼
Bin
(
d
−
1
)
and
δ
d
depends on the outcome of
X
. From the relation
O
d
,
m
+
E
d
,
m
=
d
and the fact
∼
−
−
X
, we get that
E
d
,
m
=
−
−
δ
d
∼
+
−
δ
d
.
that
X
is symmetric, i.e.
X
d
1
d
X
X
1
−
−
Suppose that
m
d
is even. In case
m
d
is odd, the argument is similar. Then
E
d
,
m
−
δ
d
equals 0, if
X
is even and equals 1, if
X
is also even, by Lemma
6
, and thus 1
is odd. Hence, we have that
E
d
,
m
=
k
,forsomeeven
k
, if and only if either
X
=
k
or
X
=
k
−
1. This means that
d
k
1
2
d
−
1
.
P[
E
d
,
m
=
k
]=
P
[
Bin
(
d
−
1
)=
k
]+
P
[
Bin
(
d
−
1
)=
k
−
1
]=
For any positive integer,
s
, we write
W
∼
Bin
(
s
,
even
)
(resp. Bin
(
s
,
odd
)
) when-
ever the random variable
W
is distributed as a Bin
(
s
)
random variable conditioned to
be even (resp. odd). We will also write Bin
whenever we don't want to specify
the exact parity and refer to it as a
half-Binomial
.
Note that the proof of the last Theorem says that if we are interested in an out-
come of, say, Bin
(
s
,
)
1 coins and if
the result is even, add a 0 (resp. a 1), if it is odd add 1 (resp. a 0). Call such a toss an
even-sum
(resp.
odd-sum
)tossof
s
coins.
We now consider the general case of a disconnected graph,
G
. Suppose that it
consists of connected components,
G
1
,
(
s
,
even
)
(resp. Bin
(
s
,
odd
)
), we can toss
s
−
1fair0
/
G
2
,...,
G
t
each having
d
i
vertices and
m
i
Search WWH ::
Custom Search