Định lý Brégman và entropy

1. Permanents

Gọi ${\mathbf A}$ là một ma trận vuông ${n \times n}$ , ${S_n}$ là tập các hoán vị của ${[n]}$ , và ${\text{sgn}(\sigma)}$ là dấu của một hoán vị ${\sigma \in S_n}$ . Ta có thể tính định thức của ${\mathbf A}$ bằng biểu thức

$\displaystyle \text{det}(\mathbf A) = \sum_{\sigma \in S_n} \text{sgn}(\sigma) \prod_{i=1}^n a_{i\sigma(i)}.$

Cũng công thức trên, nếu ta bỏ phần dấu của hoán vị ${\sigma}$ đi thì ta có cái gọi là permanent của ma trận ${\mathbf A}$ :

$\displaystyle \text{per}(\mathbf A) = \sum_{\sigma \in S_n} \prod_{i=1}^n a_{i\sigma(i)}.$

Khi ${\mathbf A}$ là ma trận ${0,1}$ thì ta có thể xem nó là ma trận kề của một đồ thị hai phần (bipartite graph): các hàng là một phần và các cột là phần còn lại; có một cạnh giữa hàng ${i}$ và cột ${j}$ nếu ${a_{ij}=1}$ . Khi đó, dễ thấy rằng ${\text{per}(\mathbf A)}$ chính là tổng số cách bắt cặp hoàn hảo (perfect matchings) của đồ thị. Bài toán tính permanent của một ma trận ${0,1}$ cho trước là bài toán ${\#P}$ -complete cơ bản, công trình rất dễ thương của Les Valiant, người được giải Turing năm ngoái.

2. Định lý Brégman

Henryk Minc là một trong những chuyên gia đầu tiên (và hàng đầu) về permanents. Ông vốn là người Ba Lan; gia nhập quân đội khi Đức chiếm Ba Lan. Bị Đức Quốc Xã bắt và trốn thoát 3 lần. Được thưởng huân chương quân đội Ba Lan. Sau đệ nhị thế chiến ông dạy một thời gian ở đại học Florida, và sau đó là UC Santa Barbara cho đến cuối đời. Năm 1963, Henryk Minc có một conjecture như sau. Cho một ma trận ${0,1}$ ${\mathbf A = (a_{ij})_{i,j=1}^n}$ mà hàng thứ ${i}$ của ma trận có ${r_i}$ số ${1}$ , thì

$\displaystyle \text{per}(\mathbf A) \leq \prod_{i=1}^n (r_i!)^{1/r_i}. \ \ \ \ \ (1)$

Đến năm 1973 thì Brégman (như trong Bregman divergence) chứng minh được bất đẳng thức trên. Kết quả này ngày nay thường được gọi là định lý Brégman hoặc bất đẳng thức Brégman. (Rất thú vị là có cả phiên bản 3-chiều của định lý Brégman; lưu ý rằng có ít nhất 2 cách định nghĩa permanent của một ma trận khối 3 chiều.)

Năm 1978, Alex Schrijver tìm ra một chứng minh tuyệt vời, rất ngắn gọn, dùng quy nạp. Bạn có thể đọc nó trong quyển A Course in Combinatorics Wilson và van Lint. Lập luận của Alex Schrijver có thể được “xác suất hoá”; và trong quyển The Probabilistic Method thì Joel Spencer và Noga Alon đã trình bày một chứng minh xác suất của bất đẳng thức Brégman.

Cuối cùng, đến năm 1997 thì Jaikumar Radhakrishnan entropy hoá chứng minh xác suất của Spencer và Alon. Ý tưởng chính của chứng minh định lý Brégman bằng entropy đã nằm trong chứng minh của Schrijver; nhưng đây là một bài tập cực kỳ không tầm thường. Đóng góp của Radhakrishnan rất thú vị.

3. Chứng minh định lý Brégman bằng phương pháp entropy

3.1. Entropy có điều kiện và một bất đẳng thức đơn giản

Để tiện tham khảo, ta chép lại từ http://en.wikipedia.org/wiki/Conditional_entropy dùng để đo tính ngẫu nhiên của biến ${X}$ sau khi đã biết biến ${Y}$ . Entropy của ${X}$ cho biết ${Y}$ được định nghĩa là giá trị kỳ vọng của entropy của biến ${X | Y}$ , biết ${Y}$ rồi thì tính trung bình ta biết thêm được bao nhiêu về ${X}$ :

$\displaystyle \begin{array}{rcl} H(X | Y) &=& \text{\bf E}[H( X \ | \ Y)]\\ &=& \sum_{y} p(y) H(X | Y=y)\\ &=& \text{\bf E}_{x,y}\left[ \log \frac{1}{p(x | y)} \right] \end{array}$

Từ ${p(x,y) = p(x|y)p(y)}$ ta có luật chuỗi:

$\displaystyle H(X,Y) = H(X | Y) + H(Y). \ \ \ \ \ (2)$

Tinh thần của chứng minh định lý Brégman bằng entropy cũng hao hao với tinh thần của chứng minh định lý Loomis-Whitney (tổng quát) bằng entropy; tuy nhiên, thay vì dùng bất đẳng thức Shearer ta dùng một bất đẳng thức khác trên entropy có điều kiện. Cụ thể là, ta sẽ dùng bất đẳng thức sau. Gọi ${X,Y}$ là các biến ngẫu nhiên rời rạc, và miền của ${Y}$ có thể phân hoạch được thành ${r}$ phần ${P_1, \dots, P_r}$ , sao cho với mọi ${y \in P_j}$ ta có ${|\text{support}(X \ | \ Y=y)| \leq j}$ , thì

$\displaystyle H(X \ | \ Y) \leq \sum_{j=1}^r \text{Prob}[Y \in P_j]\cdot \log j. \ \ \ \ \ (3)$

Ở đây, support của một biến rời rạc là tổng số các giá trị khác nhau mà nó có thể giữ. (Ví dụ support của một con xúc xắc là 6, của một đồng xu là 2.)

Bài tập: chứng minh BĐT (3).

3.2. Chứng minh của Radhakrishnan

Gọi ${S}$ là tập tất cả cả hoán vị của ${[n]}$ tương ứng với các số hạng khác ${0}$ trong khai triển ${\text{per}(\mathbf A)}$ ; nghĩa là ${S}$ bao gồm các hoán vị ${\sigma}$ sao cho ${\prod_{i=1}^na_{i\sigma(i)}=1}$ . Chọn ${\sigma \in S}$ ngẫu nhiên dùng phân bố đều, thì ta có

$\displaystyle \log(\text{per}(\mathbf A)) = H(\sigma).$

Thay vì chặn trên ${\text{per}(\mathbf A)}$ ta sẽ tìm cách chặn ${H(\sigma)}$ . Gọi ${\tau\in S_n}$ là một hoán vị tuỳ hỉ (cố định) của ${[n]}$ ; từ luật chuỗi ta suy ra

$\displaystyle \begin{array}{rcl} H[\sigma] &=& H[\sigma(\tau(1)), \sigma(\tau(2),\cdots,\sigma(\tau(n))]\\ &=& \sum_{k=1}^n H[\sigma(\tau(k)) \ | \ \sigma(\tau(1)),\cdots \sigma(\tau(k-1))] \end{array}$

Ta cần một chặn trên tốt của biểu thức bên vế phải. Với một ${\tau}$ tuỳ hỉ thì khó lấy chặn trên. Ta trung bình hoá vế phải và chặn trên trị kỳ vọng của vế phải. Phương pháp này sẽ làm chặn trên dễ dàng hơn. Đây cũng là cái mẹo nằm ẩn trong chứng minh tổ hợp của Alex Schrijver. Chọn ${\tau\in S_n}$ ngẫu nhiên bằng phân bố đều, ta có

$\displaystyle \begin{array}{rcl} H[\sigma] &=& \text{\bf E}_\tau\left[ \sum_{k=1}^n H[\sigma(\tau(k)) \ | \ \sigma(\tau(1)),\cdots \sigma(\tau(k-1))]\right]\\ &=& \text{\bf E}_\tau\left[ \sum_{i=1}^n H[\sigma(i) \ | \ \sigma(\tau(1)),\cdots \sigma(\tau(k-1))]\right] \end{array}$

trong đó ${k=\tau^{-1}(i)}$ (hoặc ${i=\tau(k)}$ ). Lưu ý rằng đa đã đổi chỉ số của tổng bên trong trị kỳ vọng. Đổi chỉ số ở đây đơn giản là một cách khác để nhóm các số hạng lại với nhau.

Ta cần chặn (trên) lượng thông tin về biến ${X = \sigma(i)}$ được tiết lộ sau khi đa đã nhìn thấy giá trị của biến ${Y = \sigma(\tau(1)), \cdots,\sigma(\tau(k-1))}$ . Gọi ${R_i(\sigma,\tau)}$ là tập các chọn lựa của ${\sigma(i)}$ sau khi ta đã nhìn thấy ${\sigma(\tau(1)), \cdots,\sigma(\tau(k-1))}$ ; nghĩa là:

$\displaystyle R_i(\sigma,\tau) = \left\{ j \ | \ a_{ij}=1 \right\} \setminus \left\{\sigma(\tau(1)), \cdots,\sigma(\tau(k-1)) \right\}.$

Lưu ý rằng, ${1\leq |R_i(\sigma,\tau)| \leq r_i}$ vì ta chỉ có ${r_i}$ số ${1}$ trên hàng thứ ${i}$ của ma trận. Ngoài ra, dễ thấy rằng, với ${\sigma \in S}$ cố định tuỳ hỉ, ta có

$\displaystyle \text{Prob}_{\tau}[|R_i(\sigma,\tau)|=j] = \frac{1}{r_i}, \ \ \ \forall j \in [r_i].$

(Bài tập: chứng minh điều này.) Do đó,

$\displaystyle \text{Prob}_{\sigma,\tau}[|R_i(\sigma,\tau)|=j] = \frac{1}{r_i}, \ \ \ \forall j \in [r_i].$

Từ bất đẳng thức (3),

$\displaystyle H[\sigma(i) \ | \ \sigma(\tau(1)),\cdots \sigma(\tau(k-1))] \leq \sum_{j=1}^{r_i} \text{Prob}_\sigma[|R_i(\sigma,\tau)|=j] \cdot \log j.$

Cuối cùng,

$\displaystyle \begin{array}{rcl} \log(\text{per}(\mathbf A))&=&H(\sigma)\\ &\leq &\text{\bf E}_\tau\left[ \sum_{i=1}^n \sum_{j=1}^{r_i} \text{Prob}_\sigma[|R_i(\sigma,\tau)|=j] \cdot \log j \right]\\ &=& \sum_{i=1}^n \sum_{j=1}^{r_i} \text{\bf E}_\tau[\text{Prob}_\sigma[|R_i(\sigma,\tau)|=j]] \cdot \log j\\ &=& \sum_{i=1}^n \sum_{j=1}^{r_i} \text{Prob}_{\sigma,\tau}[|R_i(\sigma,\tau)|=j] \cdot \log j\\ &=& \sum_{i=1}^n \sum_{j=1}^{r_i} \frac{1}{r_i} \cdot \log j\\ &=& \sum_{i=1}^n \log (r_i!)^{1/r_i}. \end{array}$