德國坦克問題

統計學理論估計中,用不放回抽樣來估計離散型均勻分布最大值問題中著名的德國坦克問題(英語:German tank problem),它因在第二次世界大戰中用於估計德國坦克數量而得名。

第二次世界大戰期間,盟軍情報部門用統計學方法準確地估計了德國坦克的生產數量,如豹式坦克

這些分析說明了頻率推斷貝葉斯推斷之間的不同。

基於「單個」樣本估計的樣本總數各有不同,而在「多個」樣本的基礎上估計則是現實生活中一個很有意義的估計問題,它的答案很簡單,但並不那麼明顯。

範例

編輯

假設某個情報人員已經發現了k = 4輛坦克,其序列號分別為2、6、7、14,觀測到的最大的序列號為m = 14。坦克未知的總數設為N

按「頻率論」方法的估算公式,計算出坦克總數為:

 

而「貝葉斯」分析會給出一個估計坦克數量的概率質量函數,如下所示:

 

從中,我們可以估計坦克數量:

 

這個分布的偏度為正,因為其中有一個事實,即至少有14輛坦克。

歷史上的問題

編輯
 
豹式坦克被裝載運輸至前線,攝於1943年。

在戰爭的過程中,西方盟國一直在努力確定德國的生產速度,並以兩種主要方式得到這個數據:常規情報收集和統計估計。大部分情況下,統計估計的可信度很大程度上決定於常規情報收集。而有時常規情報收集會和統計估計一起結合使用,如在D日前夕估計豹式坦克的生產速度。

盟軍指揮機構已經注意到了出現在意大利的五號坦克(豹式坦克),速度快,裝備有75 mm/L70長管戰車砲,是很不尋常的重型坦克,但在法國北部編號就很小,就和虎I坦克在突尼斯那樣。由於謝爾曼坦克在對陣三號坦克四號坦克時表現良好,美國陸軍對它非常自信,以至於迫不及待地希望與他們相遇[N 1]。就在D日的不久前,有消息稱德國手中有大量的五號坦克。

為了確定這種說法的真實性,盟軍要嘗試估計正在生產坦克的數量。為此,他們要使用被繳獲或被摧毀的坦克的序列號。他們主要使用變速箱的號碼,因為其為兩個完整的序列。底盤和發動機號碼也有使用,但它們的編號規則比較複雜。各種其他的零件用來對分析結果進行交叉檢查。對輪胎也做了類似的分析,其上觀察到了順序編號(即1、2、3、……、N)。[2][a][3][4]

對坦克車輪的分析產生了對使用中的車輪模具數量的估計。在與英國車輪製造商討論過後,他們估計了這麼多的模具可以生產多少車輪,進而是每個月可生產的坦克數量。對兩輛坦克(每輛32個車輪,總計64個車輪)車輪的分析的結果是1944年2月的生產數量估計在270左右,大大超出此前預期。[5]

德國戰後公布的記錄顯示,1944年2月一個月的生產量是276輛[6][N 2]。統計方法結果的精確度是常規情報收集方法所遠遠不能達到的,而「德國坦克問題」這個詞也成為了這種統計分析問題的標誌。

估計產量並不是這種序列號分析的唯一應用。它也用於探查更多德國生產的信息,包括工廠數目、工廠的相對重要性、供應鏈長度(基於生產和使用之間的滯後程度)、生產工藝的改變、及對諸如橡膠等資源的使用。

具體數據

編輯

根據常規盟軍情報的估計,德國在1940年6月和1942年9月之間,每月大約能生產1,400輛坦克。將繳獲坦克的序列號代入下文的公式,可計算出每月246輛。戰後,從阿爾伯特·斯佩爾所管轄的部門繳獲的德國生產記錄顯示,實際數目是245輛[3]

某些特定月份的估計如下:[7][8]

月份 統計估計 情報估計 德國記錄
1940年6月 169 1,000 122
1941年6月 244 1,550 271
1942年8月 327 1,550 342

類似分析

編輯
 
統計方法精確地估計了V-2火箭的生產。

在二戰期間,類似的序列號分析也在其他軍事裝備上應用過,其中最成功的屬V-2火箭[9]

二戰期間,德國情報部門分析了蘇聯軍事裝備工廠,朝鮮戰爭期間蘇聯裝備工廠也被分析過。蘇聯在二戰期間也估計過德國坦克的生產數。[10]

20世紀80年代,一些美國人被獲准進入以色列的梅卡瓦坦克的生產線。生產編號是分類過的,但水箱上有序列號,可以用來估計生產量。[11]

該公式在非軍事中也有使用,如估計Commodore 64計算機的總數,其結果(1.25億)與官方數字相當匹配。[12]

應對措施

編輯

為了防止序列號分析,可以不使用序列號,或者減少可用的輔助信息。此外可以使用抗密碼分析的序列號,最有效的方法是從比生產物品數量大得多的列表中隨機選擇一個號碼,之後就不再使用(一次性密碼本),或產生隨機數後檢查是否在已分配編號列表上;編號可能會發生碰撞,除非編號可能的位數數目在生產物品數字位數的兩倍以上(其中序列號可以以任何數為底);參見生日問題[b]。對此可使用密碼學安全偽隨機數生成器。要想從序列號中反推生產訂單,對所有這些方法都需要一個查找表(或破解加密器),其使序列號變得複雜:如對於加密器,不能一次反推一串序列號,每個號碼都必須單獨查找,或者是一張生成列表。

另外,還可以對連續的序列號進行加密,同時方便解碼,但這會帶來潛在的已知明文攻擊:即使從任意數開始,明文都會具有特定模式(即數字是有序的)。一個例子是在肯·福勒特的小說《代碼為零》中,木星-C火箭的序列號加密規則為:

H U N T S V I L E X
1 2 3 4 5 6 7 8 9 0

此處的代碼字為Huntsville(省略重複字母),用以獲得一張10字的鍵值表。因此,13號火箭編為「HN」,而24號火箭則是「UT」。

頻率論分析

編輯

最小方差無偏估計

編輯

對於點估計(估算出單個總體( )值),最小方差無偏估計(MVUE,或UMVU估計)由下式給出:[c]

 

其中m是所觀察到的最大序號(樣本最大值),而k是觀察到的坦克數目(樣本容量[11][13][14]。注意,一旦觀察到一個序列號,它就不再在樣本池中,也不會被再次觀察到。

其方差為[11]

 

因而標準差約為N/k,即樣本間距的(總體)平均大小;注意與前文中的m/k相比。

直觀

編輯

公式可以直觀地理解為樣本最大值加上樣本中觀測值之間的平均間距,由於是最大似然估計,樣本最大值被用作初始估計值[d],再加上間距以補償樣本最大值的負偏差,以此作為總體最大值的一個估計[e],因而可寫成:

 

可以想象樣品在整個區間內均勻分布,而更多的樣本就在0至N + 1的區間之外。 如果在0和編號最小樣本(樣本最小值)之間選一個初始間距,那麼樣本間的平均間距是 ;有 是因為樣本本身在計算樣本間距時不應算入。[f]

這一理念確立並推廣了最大間距估計的方法。

推導

編輯

樣本最大值等於m的概率為 ,其中 二項式係數

樣本最大值的期望值為

 

因而

 

N無偏估計

為了表明這是UMVU估計:

  • 首先表明樣本最大值是總體最大值的充分統計,使用類似於在充分性:均勻分布中具體闡述的方法(但對於德國坦克問題,我們必須排除在樣本中出現兩次序列號的結果);
  • 接着表明這是一個完整統計
  • 那麼根據萊曼–薛費定理,如上糾正過偏差的樣本最大值是無偏的,也就是UMVU估計。

置信區間

編輯

此外,或者補充來說,對於「點」估計可以進行「區間」估計,如置信區間。基於k個樣本落在覆蓋全範圍p(0 ≤ p ≤ 1)的區間的概率為pk,可以很容易地計算出這些結果(在此段中假設取樣後「放回」以簡化計算,如果取樣後不放回則會誇大概率,區間也將過於保守)。

因此,樣本最大值的分位數的抽樣分布曲線是x1/k在0到1上的圖像:樣本最大值m的第p到第q個分位數是區間[p1/kN, q1/kN]。反轉這個結果就產生總體最大值的相應置信區間[m/q1/k, m/p1/k]。下界非常接近m,所以取p = 5%到100%得到的非對稱置信區間更有意義;k = 5時會產生 ,所以區間為[m, 1.82m]。

例如,對k = 5,取對稱的95%區間,即令p = 2.5%,q = 97.5%,可得   ,所以置信區間大約為 

更一般地,(下偏)95%置信區間為 。對於一系列的k,附上UMVU的點估計值(加1以便於閱讀)以便參考,可得:

k 點估計值 置信區間
1    
2    
5    
10    
20    

從中可發現:

  • 對於較小的樣本容量,置信區間很寬,反映了其估計值具有很大的不確定性。
  • 範圍迅速縮小,反映了「所有」樣品遠低於最大值的概率呈指數衰減。
  • 置信區間呈正偏態,因為N永遠不可能低於樣本最大值,但卻可能比它任意大。

注意,m/k不能天真地用作(或者更確切地說,是(m + m/k − 1)/k標準差SE的估計值,因為標準差的估計值基於「總體」最大值(一個參數),在這裡用估計值來估計誤差會造成循環論證

在某些領域,尤其是在未來學中,以這種方式基於單個樣本估計置信區間——考慮到它是一個隨機取樣的分位數(根據平庸原理)——稱為哥白尼原則。這一點特別適用於基於目前的年齡來估計壽命,尤其是末日論將其用於估計人類的預期存活時間。

貝葉斯分析

編輯

在德國坦克問題中,貝葉斯方法要考慮當觀察到的坦克總數 等於數 、序列號最大值 等於數 時敵方坦克總數 等於數 的可信度 

為了簡便起見,以下將 寫成 

條件概率的法則會給出

 

表達式 是當敵方坦克總數等於已知的 、且觀察到了 輛敵方坦克時,所觀察到的序列號最大值等於 的條件概率。其為

 

其中二項式係數 是從總數為 的總體中取 個樣本的方法數。

表達式 是在真正觀測前,假設觀察了k輛坦克後,最大序號等於m的概率。通過合併所有可能的  可以改寫為其它形式。

 

表達式 為當已觀察到k輛坦克、但序列號尚未統計前坦克總數等於n的可信度。假定它是某種離散均勻分布

 

上限 必須是有限的,因為該函數

 

的結果為: ,而這不是一個概率質量函數。

因而

 

如果 ,那麼不受歡迎的變量 就能從表達式中消失。

 

k ≥ 1時,敵方坦克數量分布的眾數m

k ≥ 2時,敵方坦克數量「等於」 的可信度為

 

而敵方坦克數量 「大於」 的可信度為

 

k ≥ 3時, 均值有限:

 

k ≥ 4時, 標準差有限:

 

這些公式將在下面推導。

求和公式

編輯

下面的等式用二項式係數表示法來簡化德國坦克問題中的級數

 

這個求和公式有點類似於積分公式

 

這些公式在k > 1時適用。

一輛坦克

編輯

n輛坦克的總體中隨機觀察一輛坦克,當mn時,其序列號為m的概率為1/n,而當m > n時概率是零。用艾弗森括號表示法可寫成

 

這是 的條件概率質量分布函數。

m為定值時,這是一個n似然函數

 

最大似然估計的坦克總數為N0 = m

總概率為無窮大,因為尾部為一個調和級數數列。

 

 

其中 調和數

可信度質量分布函數依賴於先前的限制 

 

 的均值為

 

兩輛坦克

編輯

如果觀察到了兩輛坦克,而不是一輛,那麼所觀察到的兩個序列號中較大值為m的概率為

 

m為定值時,這是一個n似然函數

 

總概率為

 

可信度質量分布函數為

 

中位數 滿足

 

所以

 

因而中位數為

 

N的均值為無窮大

 

多輛坦克

編輯

可信度質量分布函數

編輯

在序列號{1,...,n}中觀測到的最大值為k的條件概率m

 

n的似然函數表達式與此相同

 

k ≥ 2的總概率為一個有限值:

 

可信度質量分布函數為

 

互補累積分布函數N > x的可信度

 

累積分布函數Nx的可信度

 

數量級

編輯

敵方坦克數目的數量級為

 

統計不確定度

編輯

統計的不確定度用標準差σ表示,其滿足等式

 

所以

 

 

方差均值比則為

 

參見

編輯

其他對估計的討論

編輯

參考

編輯
注釋
  1. ^ 一份1943年11月的裝甲地面部隊政策條款中這麼說:「不同意讓有限數量的坦克攜帶90毫米戰車砲(M3戰車砲),原因如下:M4坦克被廣泛譽為當今戰場上最好的坦克……在面對德國六號坦克(虎式坦克)時沒有必要擔心我們的部隊。T26坦克可能就沒有這個基礎,除了坦克與坦克對決——而這既不合理,也沒必要。」[1]
  2. ^ 拉格爾斯與布羅迪的論文很大程度上是對實際問題分析和總結,而不是數學——估計問題只在第82頁的腳註3中提到,其中他們估計最大值的方法是「樣本最大值+平均間距」。
  1. ^ 編號的下界未知,但為了簡化討論通常省略這個細節,而設下界為已知的1。
  2. ^ 如在生日攻擊中論述的那樣,如果從H的可能輸出中選擇,在1.25√H次後預期就會發生一次碰撞。平方根對應一半的數字位數。例如,一個100位的數字平方根大致是一個50位的數,無論在何種進制當中。
  3. ^ 在連續分布中,沒有−1這個術語。
  4. ^ 給定一組特定的觀測結果,那麼總體最大值最可能是樣本最大值,而不是其它更大的值(不可能更小)。
  5. ^ 樣本最大值不會超過總體最大值,但可以更小,因此它是一個有偏估計:它往往會「低估」總體最大值。
  6. ^ 例如,2和7的間距為(7 − 2) − 1 = 4,即3、4、5、6。
引用
  1. ^ AGF policy statement. Chief of staff AGF. November 1943. MHI
  2. ^ Ruggles & Brodie 1947,第?頁.
  3. ^ 3.0 3.1 Gavyn Davies does the maths - How a statistical formula won the war, 衛報, 20 July 2006 [6 July 2014], (原始內容存檔於2013-07-26) 
  4. ^ Matthews, Robert, Data sleuths go to war, sidebar in feature 'Hidden truths', 新科學人, 23 May 1998, (原始內容存檔於2001年4月18日) 
  5. ^ Bob Carruthers. Panther V in Combat. Coda Books Ltd. : 94– [2014-07-07]. ISBN 978-1-908538-15-4. (原始內容存檔於2014-07-18). 
  6. ^ Ruggles & Brodie 1947,第82–83頁.
  7. ^ Ruggles & Brodie 1947,第89頁.
  8. ^ Order Statistics. The University of Alabama in Huntsville. Virtual Laboratories in Probability and Statistics. [8 July 2014]. (原始內容存檔於2014-07-14).  外部連結存在於|publisher= (幫助)
  9. ^ Ruggles & Brodie 1947,第90–91頁.
  10. ^ Volz 2008.
  11. ^ 11.0 11.1 11.2 Johnson 1994.
  12. ^ How many Commodore 64 computers were really sold?. pagetable.com. 1 February 2011 [6 July 2014]. (原始內容存檔於2016-03-06). ,但不充分。
  13. ^ Johnson, Roger, Estimating the Size of a Population (PDF), Getting the Best from Teaching Statistics, 2006, (原始內容存檔於2008-11-20) 
  14. ^ Joyce, Smart. German Tank Problem. 羅根高中. [8 July 2014]. (原始內容存檔於2012-04-24). 
文獻