偏序集排序（八）

今天來證明定理 29，的前半部。

定理 29

基於貪婪鏈分解的合併排序法，其比較次數 \(T_{合併貪婪鏈} \le 6.33 \log e(P) + n\)。

首先我們來證明加強版的引理 26。

引理 30 [Cardinal, Fiorini, Joret, Jungers, Munro 2013]

對於任意偏序集 \(P\)，都有 \(4\log e(P) + nH(P) \ge n\log n\)。

引理 30 的證明

證明的方法依舊是數學歸納法（萬用科科），歸納的方向是：讓 \(n\) 從小到大、然後對於同樣集合大小的偏序集，根據 \(e(P)\) 值由小到大的順序進行歸納（也就是說依照偏序關係的多寡，由大至小歸納）。

Base Case: \(n=1\) 的時候不等式右邊是 \(0\)、而左邊非負，結論顯然成立。

Inductive Case: 令偏序集 \((P, <)\) 內的元素為 \(x_1, x_2, \ldots, x_n\)。我們假設 \(z=(z_1, z_2, \ldots, z_n)\) 是直鏈和多胞形 \(\mathcal{C}(P)\) 定義出來的最佳化問題的最佳解，也就是 \(nH(P) = -\sum_{i=1}^n \log z_i\)。 現在令 \(i^* = \arg\max_i\{z_i\}\) 是為數值最大的座標，如果有多個座標值相同我們可以隨意挑選一個。

證明的計畫如下：我們如果能找到另一個與 \(x_{i^*}\) 無關的元素 \(x_j\)，然後考慮 \(x_{i^*}\) 與 \(x_j\) 之間的大小關係。 根據新加入的大小關係，我們可以得到兩種可能的偏序集 \(P_1\) 與 \(P_2\)。此時根據線性延伸 \(e(P)\) 的定義，我們知道 \(e(P) = e(P_1) + e(P_2)\)。其中 \(\min\{e(P_1), e(P_2)\}\le \frac12 e(P)\)。 不妨假設 \(e(P_1)\) 是比較小的那個。那麼，如果能夠透過修改目前達到 \(nH(P)\) 的 \(z\) 得到另一個座落於 \(\mathcal{C}(P_1)\) 內部的座標 \(z'\)，來證明 \(\eqref{eq2}\)。就能夠利用數學歸納法，把下列兩式加起來，得到結論。

\[ \begin{eqnarray} 4\log e(P_1) &\le& 4\log e(P) - 4 \\ nH(P_1) & \le& nH(z') = nH(P) + 4 \label{eq2}\tag{*} \end{eqnarray} \]

加起來，利用歸納假設可以得到：\(4\log e(P) + nH(P) \ge 4\log e(P_1) + nH(P_1) \ge n\log n\)。

怎麼把 \(z\in \mathcal{C}(P)\) 修改成 \(z'\in\mathcal{C}(P_1)\) 又不會使熵值 \(nH(P_1)\) 變化太大呢？現在，對於一個 \(z_i\)，我們想像一下 \(z_i\) 是怎麼來的。由於 \(z\in \mathcal{C}(P)\)，因此所有通過 \(x_i\) 的鏈，其對應到的 \(z\) 值加總都不超過 \(1\)。於是，我們可以定義這個點 \(x_i\) 的「活動範圍」\([L_i, R_i]\)，其中 \(L_i = \max_{I(< x_i)} \sum_{k\in I-\{i\}} z_k\)，白話來說就是所有以 \(x_i\) 為結尾的鏈、不包含 \(x_i\) 本身之 \(z\) 值總和，的最大值。 而類似地上界可定義為 \(R_i=1 - \max_{I(> x_i)} \sum_{k \in I-\{i\}} z_k\)，也就是 \(x_i\) 後面能夠跟著的鏈的 \(z\) 值總和。

由於 \(z\) 是最佳化問題的最佳解，所以保證有 \(z_i = R_i - L_i\)（也就是說左邊的最長鏈與右邊的最長鏈，恰好留給了 \(x_i\) 寬度為 \(z_i\) 的空間）。若不然，我們可以讓 \(z_i\) 的值變大，定義成 \(R_i - L_i\)，這麼一來 \(nH(z)\) 的值會變得更小，與 \(z\) 是最佳解矛盾。

在這樣的結構之下，如果有兩個元素 \(x_i\) 與 \(x_j\) 其對應出來的區間重疊 \((L_i, R_i)\cap (L_j, R_j) = \emptyset\)，那麼我們便能保證 \(x_i\) 與 \(x_j\) 一定不可比較（incomparable）。

第一種情況

如果今天有個元素 \(x_*\) 無法與 \(x_{i^*}\) 進行比較，那麼此時必定存在一條通過 \(x_*\) 的鏈，其上頭元素對應到的 \(z\) 值總和恰好是 \(1\)。換句話說，此時必定存在另一個 \(z_j\)。使得它的活動範圍蓋住 \([L_{i^*}, R_{i^*}]\) 的中點，即 \((L_{i^*}+R_{i^*})/2 \in [L_j, R_j]\)，如下圖所示。

這種時候，考慮 \(P_1\) 與 \(P_2\)。無論是何種情形，我們總是可以修改 \(z_{i^*}\) 與 \(z_j\)，把它們變成原本的 \(1/4\)。這時候，不難說明新的 \(z'\in\mathcal{C}(P_1)\) 且 \(z'\in\mathcal{C}(P_2)\)，如下圖所示：

這邊的證明會用到兩個條件：其一，\(z_{i^*} \ge z_j\)、其二，\(x_j\) 的活動範圍涵蓋了 \(x_{i^*}\) 的活動範圍中間點。 此時，將 \(x_{i^*}\) 與 \(x_j\) 進行比較後，無論誰大誰小，都能夠透過新的偏序集（歸納假設），說明 \(4e(P) + nH(P) \ge n\log n\)。

第二種情況

現在假設 \(x_{i^*}\) 與所有其他元素都可以比較。 此時我們想要把它歸納到 \(n-1\) 個點的偏序集：把這個元素從偏序集拿掉就可以了！ 令 \(P'\) 是偏序集 \((P, <)\) 把 \(x_{i^*}\) 移除後（保持其他元素之間的可比較關係）得到的子偏序集。 對於最佳解 \(z=(z_1, \ldots, z_n)\)，我們把除了 \(z_{i^*}\) 以外的所有數值通通等比例放大 \(1/(1-z_{i^*})\) 倍！ 如此一來，得到的點 \(z'\) 保證有 \(z'\in\mathcal{C}(P')\)。

那麼，我們將得到

\[ \begin{aligned} (n-1)H(P') &\le (n-1)H(z') \\ &= - \sum_{i\in [n]-\{i^*\}} \log z'_i\\ &= - \sum_{i\in [n]-\{i^*\}} \log z_i + \sum_{i\in [n]-\{i^*\}} \log (1-z_{i^*})\\ &= nH(P) + \log z_{i^*} + (n-1)\log (1-z_{i^*}) \end{aligned} \]

加上 \(e(P)=e(P')\) 這個觀察後，可以得到

\[ \begin{aligned} 4\log e(P) + n H(P) &= 4\log e(P') + nH(P)\\ &\ge 4\log e(P') + nH(P') - \log \left(z_{i^*} (1-z_{i^*})^{n-1}\right)\\ &\ge (n-1)\log (n-1) - \log \left(z_{i^*} (1-z_{i^*})^{n-1}\right) \end{aligned} \]

而後面這一項，透過算幾不等式可以知道，對任意 \(t\in (0, 1)\)：

\[ t(1-t)^{n-1} \le \frac{1}{n-1}\left( \frac{n-1}{n} \right)^n \]

因此

\[ - \log \left(z_{i^*} (1-z_{i^*})^{n-1}\right) \ge -\log \frac{1}{n-1} - n\log \frac{n-1}{n} \]

從而

\[ \begin{aligned} 4\log e(P) + n H(P) &\ge (n-1)\log (n-1) - \log \left(z_{i^*} (1-z_{i^*})^{n-1}\right)\\ &\ge (n-1)\log (n-1) + \log (n-1) - n\log (n-1) + n\log n \\ &= n\log n \end{aligned} \]

得證。 \(\square\)

接下來是證明的第二步

引理 31

對於任意 \(\delta\in [0, 1]\)，都有 \(nH(P) + (1-\delta) T_{合併貪婪鏈} \le n\log \frac{n}{\delta}\)。

引理 31 的證明

對於每一個偏序集中的元素 \(x_i\)，我們定義對應的座標

\[z_i = \frac{\delta}{n}\left(\frac{n}{\vert C_{id(x_i)}\vert }\right)^{1-\delta}\]

我們想要說 \(z=(z_1, z_2, \ldots, z_n)\) 這個點座落在 \(\mathcal{C}(P)\) 裡面即可。 要怎麼檢驗呢？只要說明對任意的鏈 \(C=\{v_1, v_2, \ldots, v_{\vert C\vert }\}\)，都有 \(\sum_{j} z_{v_j} \le 1\) 即可。 透過引理 28，我們知道 \(|C_{id(v_j)}\vert \ge \vert C\vert -j+1\)。 於是呢，

\[ \begin{aligned} \sum_{j} z_{v_j} &= \sum_{j=1}^{\vert C\vert } \frac{\delta}{n^{\delta}} \left(\frac{1}{\vert C_{id(v_j)}\vert }\right)^{1-\delta} \\ &\le \frac{\delta}{n^{\delta}} \sum_{j=1}^{\vert C\vert } \left( \frac{1}{\vert C\vert -j+1}\right)^{1-\delta} \\ &\le \frac{\delta}{n^{\delta}} \int_{0}^{\vert C\vert } \frac{1}{x^{1-\delta}} {\mathrm{d}} x \\ &= \delta \left(\frac{\vert C\vert }{n}\right)^\delta \le 1 \end{aligned} \]

接著，我們只需要利用 \(nH(P) \le nH(z)\) 這個觀察，整理兩邊以後可以得到：

\[ \begin{aligned} nH(P) &\le nH(z) = -\sum_{i=1}^n \log z_i\\ & = -\sum_{i=1}^n \log \frac{\delta}{n} - (1-\delta)\sum_{i=1}^n \log \frac{n}{\vert C_{id(x_i)}\vert }\\ & = -\sum_{i=1}^n \log \frac{\delta}{n} - (1-\delta) T_{合併貪婪鏈} \\ & = n\log \frac{n}{\delta} - (1-\delta) T_{合併貪婪鏈} \end{aligned} \]

得證。 \(\square\)

明天我們來完成定理 29 的證明。

備註

在參考資料中，Cardinal 等人證明了引理 30 時，除了上述版本的證明方法以外，還證明了最扎實版本：\(2\log e(P) + nH(P) \ge n\log n\)，但是證明相對暴力了些；筆者比較喜歡本篇中的證明。 此外，引理 31 是筆者以 \(H(P)\) 的最長鏈角度重新寫過一遍的做法，在原作之中是直接引用同一批作者更早以前在最大獨立集上的結論。如果朋友們跳進去看原本那篇論文的話，可能在這部分會感受到混淆，還請多留意。

參考資料