動機
設有人給出三個方陣,並聲稱前兩個的乘積等於第三個。用初等方法計算整個乘積需要立方時間。如果我們願意接受一個可控的概率,即可能漏掉一個錯誤的斷言,那麼驗證的成本可以更低。
關鍵在於用一個隨機向量來檢驗所聲稱的等式。矩陣與向量的乘法只需二次數量的算術運算,因此少數幾次獨立檢驗可以比完整的初等乘積便宜得多。我們將精確證明:錯誤概率的含義是甚麼,為甚麼正確的斷言絕不會被拒絕,以及分析需要哪些關於固定輸入和算術的假設。
定義
定義 6.4.1
(矩陣乘積的隨機向量檢驗)
設 為一個域,設 ,並設 。 中的算術是精確的。需要驗證的斷言是 。抽樣 ,其各座標互相獨立,且每個座標都從兩個不同的域元素 和 中均勻選取。計算 ,再計算 ,並獨立地計算 。若 則接受該次試驗,否則拒絕。
一次檢驗使用三次矩陣與向量的乘法和一次向量比較。實現時不需要計算 ,也不需要構造差矩陣 。對於稠密矩陣,一次試驗需要 次域運算,並且除輸入矩陣之外只需要 個額外的域元素。在同一次試驗的三個乘積中,必須使用同一個向量。
定理
定理 6.4.2
(單側驗證錯誤)
若 ,則每次試驗都接受。若 ,且這些矩陣在隨機向量被抽樣之前已經固定,則一次試驗接受的概率至多為 。
定理 6.4.3
(獨立重複)
對於整數 ,用互相獨立的全新向量進行 次試驗,並且僅當所有試驗都接受時才接受。正確的乘積總是被接受;不正確的固定乘積被接受的概率至多為 。稠密運算的成本為 次域運算。
這裏的概率是針對一個固定的矩陣三元組,就驗證者的隨機選擇而言的。該定理並不是說,對某個特定向量而言,至多有一半的錯誤矩陣能夠蒙混過關。
證明
一個非零行就足夠了
證明
(一個非零行限制接受概率)
記 。試驗接受當且僅當 。若 ,則該等式對每個向量都成立,這就證明了完美完備性。現設 。則 的某一行在第 列含有非零係數 。固定 中除 之外所有座標的任意取值。在該行中,方程 變為
因為 是域且 ,這個方程關於 至多有一個解。在兩個可能的取值 和 中,至多有一個能滿足它。在對其餘座標取條件之後,剩下的那個座標仍然是獨立的公平選擇,因此該行為零的條件概率至多為 。對其餘座標取平均,可得無條件下同樣的上界。事件 包含於這一行為零的事件之中,因此它的概率同樣至多為 。
該證明在每個域中都成立,包括特徵為二的域: 與 仍然不同,並且乘以非零元素仍然是單射。證明不要求 的各項互相獨立或隨機。它也不要求我們知道哪一行是非零的;這一行只在分析中使用。
證明透視
固定其餘所有座標,只留一個
關鍵一步把矩陣恆等式化為一條純量方程: 迫使 的每一行在 處為零,所以只需界定某個單一非零行為零的概率。固定除 之外的所有座標(其中 ),該行方程化為 ,而 只依賴其餘座標。由於 是域, 可逆,方程至多有一個解,所以 兩個值中至多一個可行。這裏用到兩個假設,且只在這裏用到: 中 ,使抽樣集合有兩個元素;以及 可逆。各座標相互獨立,使得在條件於其餘座標之後, 仍是公平的選擇。選取哪一行、哪一個座標只屬於分析,驗證者無須知道它們是甚麼。
證明
(獨立重複)
對於重複試驗,輸入三元組以及 都不變,而隨機向量互相獨立。對於不正確的固定三元組,每次試驗的接受概率至多為 ,所以 次試驗全部接受的概率至多為 。若某次試驗拒絕,立即停止既保持正確性,又可以節省運算。該上界所計的是所有試驗都被執行的最壞情況。
更大的抽樣集合
同樣的論證適用於由 個不同元素組成的有限集合 。每個座標獨立且均勻地從 中抽樣。在固定所有其他座標之後, 個取值中至多有一個滿足所選取的非零行方程。因此一次試驗漏掉不正確乘積的概率至多為 ,而 次獨立試驗漏掉它的概率至多為 。
對於有限域 ,從整個域中均勻抽樣即可得到這一上界。更一般地,該子集不必對加法或乘法封閉:只有其元素互不相同以及均勻獨立抽樣才是要緊的。由公平位元構造精確的均勻樣本可能有單獨的成本,特別是當 不是 的冪時。上述域運算次數的計算把抽樣視為可得的,並把算術運算單獨計費。
失敗概率的上界可以事先選定。對於二元向量,當 時,取 可使接受一個固定的不正確乘積的機會至多為 。若驗證者檢驗 個固定的斷言,並希望任何不正確接受的概率至多為 ,則可以給每個斷言分配失敗概率 ,並應用聯集界。最後這個聯集界並不要求不同斷言之間互相獨立,但每個斷言各自的重複試驗必須滿足其個別誤差估計所用的獨立性假設。
當域為有限域時:秩的作用
若 ,且整個向量在 上均勻分佈,則一次試驗的實際錯誤概率有一個有用的精確描述。設 。由秩–零度定理,核的維數為 ,所以在等可能的 個向量中,核含有 個。因此
非零的差矩陣的秩至少為一,從而得到前面的 上界。秩為一的差矩陣可以達到該上界,而滿秩的差矩陣僅在零向量上被漏掉,其錯誤概率為 。驗證者不需要計算秩:這樣做會增加工作量,而對每個非零差矩陣都適用的一致最壞情況保證已經足夠。
這一精確的秩公式依賴於從整個有限域中均勻抽樣。對於較大域中的二元向量,它不能自動適用,因為這些向量只在子集 上均勻分佈。單座標論證對該子集仍然有效,並且仍然給出 的上界。區分精確概率與最壞情況上界,可以避免對試驗預算作出無根據的削減。
概念視角組合
數方體上被接受的頂點
二元向量就是 維方體的 個頂點,同一個上界也可以透過計數得到。取 中一行,其第 個係數 ,把每個 的頂點 與只在第 個座標上不同的頂點 配成一對。此時 ,而 在所選那一行的分量是 。因此該行不可能在一對頂點上同時為零,每一對至多有一個頂點被接受,所以 個頂點中至多 個被接受。
高概率的結論還取決於實例是何時選定的。對於維數至少為二的任何已知非零測試向量 ,存在一個與它正交的非零行向量,而以該行為一行的非零矩陣可以使 化為零。如果允許惡意的證明者在得知驗證者的向量之後再選擇差矩陣,則不能照原樣援引固定輸入的定理。在所述的實驗中,矩陣先被固定,然後驗證者再抽樣私有的全新隨機數。
證書的含義
若某次試驗拒絕,則 。向量 是所聲稱等式為假的一個簡短證書:另一個人可以重新計算兩邊並加以比較。相反,一個被接受的向量並不證明等式成立;非零的差矩陣可以使某些向量化為零。重複被接受的試驗按已證明的上界提高信心,但並不會把接受變成確定性的證明。
單側一詞指出了哪一種結果可能出錯。在精確的域算術下,拒絕總是可靠的。對於不相等的乘積,接受則可能是錯的。當必須以高概率發現錯誤、而又不能容忍對正確計算的誤報時,這種保證很有用。應用時應當根據漏掉錯誤的後果來選擇試驗次數,而不應把有限次被接受的檢驗說成絕對的確定性。
反例模式
固定的向量可能漏掉錯誤
設 ,。則 非零,但向量 被該差矩陣變為零。檢驗這個特定的向量會接受一個不正確的乘積。隨機抽樣限制了固定輸入下這一事件發生的機會,但並不使每個單獨的向量都成為證書。
例題詳解
例題 6.4.4
(一個被漏掉的錯誤與一個被發現的錯誤)
對於 和 ,試驗接受恰好當 的第二個座標為零。在四個等可能的二元向量中, 和 接受,而 和 拒絕。錯誤概率恰為 ,這說明一般的二元上界可以是緊的。
例題 6.4.5
(正確的乘積總能通過)
在實數上,取 ,。它們的乘積為 。對於 ,計算得 ,。這個等式並非該向量所特有:由結合律,對每個向量都有 。
例題 6.4.6
(三元素抽樣)
在 上,取 和 。若每個座標在 中均勻取值,則差矩陣使 化為零恰好當其第二個座標為零。一次試驗漏掉該錯誤的概率為 ;四次獨立試驗漏掉它的概率為 。
例題 6.4.7
(選擇試驗預算)
若要用獨立的二元向量把錯誤概率限制在 以內,選擇 ,因為 。對於一千個固定的斷言(無論其正確與否),取 的聯集界給出任何不正確接受的概率至多為 。這個聯集界不需要假設各個斷言互相獨立。
常見錯誤
常見錯誤
(對每次重複都沿用同一個向量)
只抽樣一個向量並在每次重複中都使用它,並不會使錯誤概率相乘。在第一個例子中,若第二個座標為零,則同一個壞向量會通過每一次重複檢驗。全新的獨立向量才是指數下降的機制。每次試驗的全新向量還必須與命題中固定的矩陣互相獨立。
常見錯誤
(未經論證就取質數模)
把整數矩陣對某個質數取模會改變問題,除非這一約化有正當理由。若一個整數差矩陣的所有元素都是該質數的倍數,則它在模該質數下成為零矩陣,並通過該域中的每一次檢驗。例如,一個等於 的整數差矩陣元素在模 下為零。域上的定理驗證的是在所選域中的相等;要推出整數上的相等,還需要另外的論證。
常見錯誤
(把浮點運算當作精確運算)
最後,浮點捨入並不是精確的域算術。捨入可能使正確的乘積看起來不相等,也可能掩蓋微小的誤差,所以單側保證不能自動推廣到一般的浮點計算。數值驗證器需要一個適合其算術模型的誤差分析。
總結
隨機向量把矩陣乘積恆等式化為三次二次時間的矩陣與向量乘法。對於一個固定的不正確乘積,一個非零行把二元座標情況下未被發現錯誤的概率限制在二分之一。獨立重複使該概率指數下降,而在精確的域算術下正確的乘積總能通過。該結果依賴於抽樣、固定輸入和域這幾方面的假設。
練習
快速檢查
(設 ,。列出被接受的二元向量及其概率。)
解答 · 答案
差矩陣為 ,所以試驗接受恰好當第一個座標為零。被接受的向量為 和 ,概率為 。
快速檢查
(在 上,每個座標從整個域中均勻抽樣。給出三次獨立試驗都接受一個固定的錯誤乘積的概率上界。)
解答 · 答案
一次試驗的錯誤概率至多為 ,由獨立性,三次都接受的概率至多為 。某些特定的錯誤矩陣可能有更小的概率。
快速檢查
(解釋為甚麼對十次重複試驗使用同一個二元向量,未必能給出 的錯誤概率。)
解答 · 答案
對於 和 ,檢驗接受恰好當所抽樣的第二個座標為零。把同一個向量重複使用十次,接受的概率仍為 ,而不是 。
快速檢查
(給出整數 矩陣,使其乘積不等於所聲稱的整數值,但在模 下與之相等。解釋 上的驗證者看到了甚麼。)
解答 · 答案
取 ,。整數值 與 不同,但兩者模七後都化為 。 上的驗證者看到的是一個正確的域恆等式,並接受每一個向量;這並不是其域層面保證的錯誤。