Database Reference
In-Depth Information
P
m−2
e
m−1
e
m
v
1
v
m+1
v
m−1
v
m
P
m−1
P
m
(
w
P
m
−
2
and
w
e
m
are conditionally independent given
w
e
m
−
1
)
Fig. 8.2
A path
P
m
.
Pr
[
w
P
≤
55
|
w
e
3
=
20
]
∑
x
1
+
=
Pr
[
w
e
1
=
x
1
,
w
e
6
=
x
3
|
w
e
3
=
20
]
x
3
≤
35
∑
x
1
+
=
f
e
1
|
e
3
(
x
1
|
20
)
·
f
e
6
|
e
3
(
x
3
|
20
)
x
3
≤
35
The sets of samples and their membership probabilities of
f
e
1
|
e
3
(
x
1
|
20
)
and
f
e
6
|
e
3
(
x
3
|
20
)
are
{
10
(
0
.
375
)
,
15
(
0
.
375
)
,
20
(
0
.
25
)
}
and
{
20
(
0
.
25
)
,
20
(
0
.
5
)
,
50
(
, respectively. We sort the samples in the weight ascending order.
There are in total
3
0
.
25
)
}
×
3
=
9
samples on w
e
1
×
w
e
6
when w
e
3
=
20
. To enumerate
all samples, we can build a
3
×
3
sample array M as shown in Figure 8.1. Cell
M
[
i
,
j
]
stores two pieces of information: (1) M
[
i
,
j
]
.
ws is the sum of the i-th sample
of w
e
1
and the j-th sample of w
e
6
; and (2) M
[
i
,
j
]
.
pr is the membership probability
of sample M
ws which equals the product of the corresponding membership
probabilities. For example, the lowest left-most cell M
[
i
,
j
]
.
[
1
,
1
]
corresponds to a sample
where w
e
1
is
10
and w
e
6
is
10
. Thus, M
[
1
,
1
]
.
ws
=
10
+
10
=
20
and M
[
1
,
1
]
.
pr
=
0
.
375
09375
.
When w
e
3
takes sample
20
, in order to satisfy w
P
1
≤
×
0
.
25
=
0
.
w
e
6
should take values of at most
35
. Those samples are at the lower-left part of the
array. We call the region of those cells the l
-weight constrained region
when w
e
3
=
20
. The sum of the membership probabilities of the cells in the region is
0
55
, the samples of w
e
1
+
625
.
The l-weight constrained region when w
e
3
takes other samples can be calcu-
lated similarly. When w
e
3
=
.
30
, the sum of the membership probabil-
ities of the cells in the l-weight constraint regions are
0
25
and w
e
3
=
.
53125
and
0
, respectively.
F
P
1
(
55
)=
f
e
3
(
20
)
×
0
.
625
+
f
e
3
(
25
)
×
0
.
53125
+
f
e
3
(
30
)
×
0
=
0
.
4625
<
τ
.P
1
is
not an answer to Q
l
.
The idea in Example 8.1 can be generalized to paths of arbitrary length.
Theorem 8.1 (Path
weight
distribution).
Let
P
m
=
v
1
,...,
v
m
+
1
,
P
m
−
1
=
v
1
,...,
v
m
and e
m
=(
v
m
,
v
m
+
1
)
(m
>
2
), the conditional probability of
w
P
m
given w
e
m
is
)=
∑
z
f
P
m
|
e
m
(
x
|
y
f
e
m
−
1
|
e
m
(
z
|
y
)
×
f
P
m
−
1
|
e
m
−
1
(
x
−
y
|
z
)
(8.1)
≤
x
−
y
Moreover, the probability mass function of w
P
m
is