166 ADVANCED ACCEPTANCE/REJECTION
Restricted permutations basic bound, Input: A, Output:
σ
, n
1) n ← 0
2) Repeat
3) n ← n + 1, i ← 0,
σ
← (0, 0,...,0)
4) Repeat
5) i ← i + 1
6) Draw
σ
(i) uniformly from {j : A(i, j)=1}
7) Until i = n or
σ
(i) ∈{
σ
(1),...,
σ
(i −1)}
8) Until
σ
∈ S
n
In the matrix of (9.8),
∏
3
i=1
r
i
= 2 ·2 ···2 = 8, and per(A)=2. Therefore the
chance of accepting is 2/8 = 1/4 and 4 draws will be necessary on average in order
to obtain one sample.
This basic bound is terrible. Even when the matrix is as dense as possible and
r
i
= n for all i, using this basic bound is a bad idea. Consider the first order Sterling
bound on factorials.
Theorem 9.1 (Ster ling’s formula).
n
e
n
√
2
π
n ≤ n! ≤
n
e
n
e
√
n. (9.15)
If D
i
= n for all i,then
∏
#D
i
= n
n
, making the expected number of steps to get
a sample at least e
n−1
/
√
n.
So to get a polynomial time algorithm, it is necessary to find better bounds. This
section will present two such bounds, both of which give a polynomial time algorithm
forsamplingwhen#D
i
is large (for instance when #D
i
= n for all i) but still tend to
be exponential when the #D
i
are small.
9.2.3 Union of D
i
bound
This bound takes advantage of the fact that when a 0 in the matrix is changed to a 1,
the p ermanent might stay the same or become larger. So build a new problem where
D
i
= ∪
i
i
=1
D
i
. Algebraically, this means make A
(i, j)=max
i
≤i
A(i, j). Using this
on the matrix from (9.8) gives
A
=
⎛
⎝
110
111
111
⎞
⎠
. (9.16)
The reason for doing this is that now D
i
⊆ D
i+1
. So when a choice is made for
σ
(i), it reduces the number of possib ilities for
σ
(i + 1) by 1. In fact, each of the
choices
σ
(1),...,
σ
(i) reduces the number of possibilities for
σ
(i + 1) by 1. This is
the reasoning behind the following result.
Lemma 9.5. Fo r a {0, 1} matrix A, let g(i)=#{j : ∃i
≤ i with A(i
, j)=1}.
M
2
(A)=
n
∏
i=1
max(0,g(i) −(i −1)). (9.17)
APPLICATION: APPROXIMATING PERMANENTS 167
If M
2
(A)=0 then per(A)=0.IfM
2
(A) > 0,g(i
)=1 fo r i
< i, and g(i) −(i −1)
is the number of nonzero entries of A in row i, then
M
2
(A)=
∑
j
M
2
(A
i, j
). (9.18)
Before proving the lemma, suppose that M
2
is being used with SAR. Then when a
column j is chosen, A(i, j) remains 1, but all other elements in that row and column
are removed. So after i −1 steps, the first i −1 rows have exactly i −1 nonzero
elements, all in different columns. Moreover, in each of these columns the entry
of row i has been zeroed out, so #D
i
= g(i) −(i −1).Soforalli
< i, g(i
)=1
and #D
i
= g (i) −(i −1), which is why these are the conditions given in the lemma
for (9.18).
Proof. If M
2
(A)=0, that means there is a row i such that strictly fewer than i
columns in rows 1,...,i have a 1 anywhere in them. Therefore, no rook placement
with i rooks exists for these first i rows. So there is no rook placement for the whole
matrix.
Now suppose that M
2
(A) > 0and
∏
i−1
i
=1
#
∪
i
i
=1
D
i
−(i −1)
= 1. Then for
each row i,#(∪
i
i
=1
D
i
) −(i −1) > 0. Consider how M
2
(A
i, j
) and M
2
(A) are related.
In A
i, j
, the only nonzero entry in row i is in column j.
Let g
i, j
(i
)=#{j : (∃i
≤ i
)(A
i, j
(i
, j)=1}.Then
M
2
(A
i, j
)=
∏
i
<i
g
i, j
(i
) −(i
−1))
(g
i, j
(i) −(i −1))
∏
i
>i
g
i, j
(i
) −(i
−1))
M
2
(A)=
∏
i
<i
g(i
) −(i
−1))
(g(i) −(i −1))
∏
i
>i
g(i
) −(i
−1))
.
For i
> i, ∪
i
≤i
D
i
)=∪
i
≤i
D
i, j
i
, so the right-most factors are the same in both
expressions. The left-most factors of M
2
(A
i, j
) and M
2
(A) are both 1.
That leaves the center factor. Since #(∪
i
≤i
D
i, j
i
−(i −1)) = 1, that means
M
2
(A
i, j
) ≤ M
2
(A)/#(∪
i
≤i
D
i
−(i −1)). (9.19)
But there are exactly g(i) −(i −1) nonzero entries of A in row i by assumption, so
summing over j gives (9.18).
Restricted permutations union bound, Input: A, Output:
σ
, n
1) n ← 0
2) Repeat
3) n ← n + 1, i ← 0
4) Repeat
5) i ← i + 1
6) Draw
σ
(i) uniformly from ∪
i
i
=1
D
i
{
σ
(1),...,
σ
(i −1)}
7) Until i = n or
σ
(i) /∈D
i
8) Until
σ
∈S
n
168 ADVANCED ACCEPTANCE/REJECTION
For (9.8), this bound is (2)(3 −1)(3 −2)=4, twice as good a bound as the basic
bound. When #D
i
= n for all i, this gives a bound of n!, so unlike the simplest bound,
this bound is tight for the maximum density matrix.
Of course, it is not necessary to move through the rows from 1 up to n in or-
der. Permuting the rows of a matrix does not change the permanent, but can change
this upper bound! Or instead of moving along the rows, one could m ove across the
columns. Again that would not change the permanent, but would change the upper
bound being used.
9.2.4 Generalized Bregman inequ ality
Let r
i
= #D
i
. In 1963, Minc [93] conjectured the following upper bound for the
permanent of a matrix with entries in {0, 1}:
per(A) ≤
n
∏
i=1
(r
i
!)
1/r
i
. (9.20)
This bound is tight when the rows and columns of the matrix can be permuted
so that the 1’s form into square blocks. For A from (9.8), (2!)
1/2
·(2!)
1/2
·(2!)
1/2
=
2
3/2
= 2.828 ..., and so knowing that the permanent is an integer actually obtains the
correct answer.
Minc’s conjecture was proven true by Bregman in 1973 [13]. Unfortunately, the
proof did not use self-reducibility, and so does not allow the use of SAR.
To use a Minc-Bregman style bound for SAR, first let A
i, j
be the same matrix as
A, but with all entries in both row i and column j, except (i, j), zeroed out. So for A
from (9.8),
A
1,1
=
⎛
⎝
100
011
001
⎞
⎠
. (9.21)
Next the bound needs to be unpacked a bit. Using Stirling’s approximation:
(r!)
1/r
≈
r
e
r
√
2
π
r
=
r
e
(2
π
r)
1/(2r )
=
r
e
exp
ln(2
π
)
2r
+
ln(r)
2r
=
r
e
1 +
ln(2
π
)
2r
+
ln(r)
2r
+ O
ln(r)
2
r
2
.
So each factor in Minc-Bregman is (to the first order) about e
−1
[r +(1/2)ln(r)+
(1/2)ln(2
π
)] The generalized Bregman factor uses this approximation.
Definition 9.1. The generalized Bregman factor is
h
1
(r)=[e
−1
+(1 −e
−1
)r]1(0 < r < 1)+e
−1
[r +(1/2)ln(r)+exp(1)−1]1(r ≥ 1).
(9.22)
Table 9.1 illustrates how close h
1
is to the original Bregman factors. Since the
original Bregman factor bound was tight, it must be true that h
1
(r) ≥ (r!)
1/r
.The
table shows that in fact the ratio between the two tends to be very small.
In order to show that h
1
can be used for SAR, the following fact about the behav-
ior of h
1
is needed.
APPLICATION: APPROXIMATING PERMANENTS 169
Table 9.1 Comparison of h
1
(r) to (r!)
1/r
. The maximum relative error between the two values
is 6.65% at r = 3.
r 123456
h
1
(r) 1 1.4953 1.9378 2.3586 2.7675 3.1689
(r!)
1/r
1 1.4142 1.8171 2.2133 2.6051 2.9937
Lemma 9.6. Fo r a ll a ∈[0,min{r,1}],
a
h
1
(r −a)
≤ e ln
h
1
(r)
h
1
(r −a)
. (9.23)
The proof of this technical lemma, while straightforward, is fairly lengthy. The
interested reader can find the entire proof in [60]. Figure 9.1 illustrates this Lemma
by plotting the right-hand side of (9.23) minus the left-hand side for various values
of r and a.
Instead of partitioning the space of permu tations b y the choice of x(1), partition
by the choice of x
−1
(1). That is, partition by which nonzero entry in the first column
(rather than the first row) is chosen to be part of the permutation. The following
lemma shows that this methodology can be used with SAR.
Lemma 9.7. Let A be a matrix whose elements all lie in [0,1],C⊂{1,2,...,n}, and
σ
a permutation. Then set r
i
=
∑
j /∈
σ
(C)
A(i, j) and
M
3
(A,C,
σ
)=
∏
i∈C
A(i,
σ
( j))
∏
i /∈C
h
1
(r
i
). (9.24)
Fix j such that j /∈
σ
(C). Then for i /∈C, let
σ
i
be a permutation such that
σ
i
(k)=
σ
(k) for all k ∈C, and
σ
i
(i)= j. The key fact about M
3
is
M
3
(A,C,
σ
) ≥
∑
i /∈C:A(i, j)>0
M
3
(A,C ∪{i},
σ
i
). (9.25)
0 5
0
0.4
r
a = 1
0 5
0
0.4
r
a = 0.5
0 5
0
0.4
r
a = 01
Figure 9.1 Illustration of Lemma 9.6. The figures plot the right-hand side of Equation (9.23)
minus the left-hand side. The inequality is actually a strict inequality everywhere except when
r = a = 1.
170 ADVANCED ACCEPTANCE/REJECTION
Proof. Fix a column j.LetC
j
= {i /∈C : A(i, j) > 0}. The three cases to consider are
when #C
j
is 0, 1, or at least 2.
If C
j
= /0, then the right-hand side of (9.25) is 0 and the result is trivially true.
ThenextcaseiswhenC
j
= {i}.If
σ
(i) = j, M
3
(A,C ∪i,
σ
)=0 since it includes
A(i,
σ
(i)) = 0 as a factor. So to show (9.25), it is necessary to show that M
3
(A,C,
σ
) ≥
M
3
(A,C ∪{i},
σ
i
). This holds because
∑
j
/∈
σ
i
(C∪{i})
A(i
, j
) ≤
∑
j
/∈
σ
i
(C)
A(i
, j
), h
1
is
an increasing function, and A(i, j) ≤ h
1
(A(i, j)) ≤ h
1
(r
i
).
The last case is when #C
j
≥ 2. Consider how M
3
(A,C,
σ
) and M
3
(A,C ∪{i},
σ
i
)
are related. First, the row i is zeroed out except at (i, j), changing by a factor of
A(i, j)/h
1
(r
i
). Then all the entries of C
j
{i} are zeroed out, changing by a factor of
∏
i∈C
j
{i}
h
1
(r
i
−A(i, j))/h
1
(r
i
).
Let M = M
3
(A,C,
σ
). Then the above argument gives
M
3
(A,C ∪{i},
σ
i
) ≤ M
A(i, j)
h
1
(r
i
)
∏
j∈C
j
{i}
h
1
(r
i
−A(i, j))
h
1
(r
1
)
= M
A(i, j)
h
2
(r
i
−A(i, j))
∏
j∈C
j
h
1
(r
i
−A(i, j))
h
1
(r
1
)
= M
A(i, j)
h
1
(r
i
−A(i, j))
exp
!
∑
i∈C
j
ln
h
1
(r
i
−A(i, j))
h
1
(r
1
)
"
.
Summing over i gives
∑
i∈C
j
M
3
(A
i, j
) ≤ M
3
(A)
∑
i∈C
j
A(i, j)
h
2
(r
i
−A(i, j))
exp
!
∑
i∈C
j
ln
h
1
(r
i
−A(i, j))
h
1
(r
1
)
"
.
Now apply Lemma 9.6, and use ln(x)=−ln(1/x) to get
∑
i∈C
j
M(A,C ∪{i},
σ
i
) ≤ M
∑
i∈C
j
eln
h
1
(r
i
)
h
1
(r
1
−A(i, j))
exp
!
−
∑
i∈C
j
ln
h
1
(r
i
)
h
1
(r
1
−A(i, j))
"
.
The right-hand side is now of the form eMyexp(−y) where y ≥ 0. This function
has a maximum value of M at y = 1, yielding
∑
i∈C
j
M
3
(A,C ∪{i},
σ
i
) ≤ M = M
3
(A,C,
σ
). (9.26)
as desired.
This result immediately gives a SAR-type algorithm for generating from
weighted permutations where the weights all fall in the closed interval from 0 to
1. The expected number of partial permutations generated by the algorithm will be
M(A)/per(A).
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.