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
 
Search WWH ::




Custom Search