בעיית הטנק הגרמני

[ממוזער|250px|במהלך [מלחמת העולם השנייה, ייצור של טנקים גרמניים כדוגמת פנתר הוערך על ידי המודיעין של בעלות הברית באמצעות שיטות סטטיסטיות]]
באמידה, הבעיה של אמידת המקסימום של התפלגות אחידה בדידה ממדגם ללא החזרה ידועה באנגלית כ**בעיית הטנק הגרמני** (German tank problem), בשל השימוש בה בהקשר של מלחמת העולם השנייה על מנת להעריך את מספר הטנקים הגרמניים. בעיה זו מדגימה את ההבדל בין הסקה שכיחותנית (Frequentist) לבין הסקה בייסיאנית.

ממוזער|250px|טנקי פנתר נשלחים לקווי החזית, 1943

## הבעיה ההיסטורית
במהלך מלחמת העולם השנייה נעשו מאמצים ממושכים על ידי בעלות הברית כדי לקבוע את היקף הייצור הגרמני, וניסו לפתור זאת בשתי גישות: באמצעות איסוף מודיעין בצורה קונבנציונלית ובאמצעות אמידה סטטיסטית. במקרים רבים הניתוח הסטטיסטי עלה באיכותו על המודיעין הקונבנציונלי. במקרים מסוימים נעשה שימוש במודיעין קונבנציונלי בצירוף ניתוח סטטיסטי, כמו במקרה של הערכת ייצור טנקי הפנתר לפני הפלישה לנורמנדי.

הפיקוד של בעלות הברית סבר כי טנקי פנצר סימן 5 (פנתר) שנצפו באיטליה, שלהם מהירות גבוהה ותותחי 75 מ"מ/L70, הם טנקים כבדים נדירים במיוחד, ויהיו רק במספר קטן בצפון צרפת, באופן דומה לטנקי הטיגר I שנצפו בתוניסיה. צבא ארצות הברית היה משוכנע כי טנקי שרמן ימשיכו לתפקד היטב, כפי שתפקדו נגד טנקי פנצר סימן 3 ופנצר סימן 4 בצפון אפריקה ובסיציליה.

זמן קצר לפני הפלישה לנורמנדי הגיעו שמועות על כך שהגרמנים עושים שימוש במספר גדול של טנקים מסוג פנצר סימן 5. כדי לברר את נכונות השמועות, ניסו בעלות הברית להעריך את מספר הטנקים שיוצרו. הם ביססו את הערכותיהם על המספרים הסידוריים של טנקים שנתפסו או נהרסו. המספרים העיקריים ששימשו לניתוח זה היו מספרים סידוריים של תיבות ההילוכים, מאחר שאלו פוצחו על ידי בעלות הברית. מספרי השלדה והמנוע שימשו אף הם לניתוח, אך השימוש בהם היה מסובך יותר. מידע מרכיבים נוספים שימש לביסוס נוסף של הניתוח. ניתוח דומה נעשה גם על פי מספרים סידוריים של גלגלי מרכוב, שלהם ניתנו מספרים ברצף (1, 2, ...N).

ניתוח גלגלי הטנקים הניב ההערכה של מספר סוגי הגלגלים שהיו בשימוש. בדיקות שנעשו יחד עם מומחים בריטיים לייצור גלגלים העריכו את מספר הגלגלים שניתן היה לייצר מסוגים אלו, וכך את מספר הטנקים המיוצרים מדי חודש. ניתוח של גלגלים משני טנקים (בכל אחד מהם 32 גלגלים) הוביל להערכה של 270 טנקים שיוצרו בפברואר 1944.

ממסמכים גרמניים שנתפסו לאחר המלחמה התברר כי מספר הטנקים שיוצרו בפברואר 1944 היה 276 טנקים. הניתוח הסטטיסטי התברר כמוצלח יותר מהערכות המודיעין הקונבנציונליות, ו"בעיית הטנק הגרמני" הפך לשם שגור לתיאור בעיות מסוג זה.

השימוש במספרים סידוריים ובניתוחים סטטיסטים לא היה מוגבל רק להערכת מספר הטנקים, ושימש את בעלות הברית גם להערכת הייצור הגרמני באופן כללי, ובפרט מספר המפעלים וחשיבותם, אורך שרשרת האספקה (הזמן מהייצור ועד הכנסה לשימוש), שינויים בייצור ושימוש במשאבים כדוגמת גומי.

### נתוני הייצור והערכות
על פי הערכות המודיעין הקונבנציונלי של בעלות הברית, ייצרו הגרמנים בסביבות 1,400 טנקים מדי חודש בין יוני 1940 לספטמבר 1942. אבל תוך שימוש בניתוח הסטטיסטי שיוצג להלן, הוערך מספר הטנקים שיוצרו ב-246 מדי חודש בלבד. לאחר המלחמה, מסמכים עם פרטי הייצור שנתפסו ממשרדו של אלברט שפר הראו כי המספר האמיתי היה 245.

הערכות עבור מספר חודשים מוצגות להלן:

### אנליזות דומות
ניתוחים סטטיסטיים דומים נעשו על פי מספרים סידוריים גם בהקשר לציוד צבאי אחר במלחמת העולם השנייה, ובפרט לטילי V-2. במהלך מלחמת העולם השנייה העריך הצבא הגרמני את היקף הייצור הצבאי הסובייטי, ובמהלך מלחמת קוריאה, נעשה ניתוח של מספרים סידוריים של ציוד סובייטי. גם ברית המועצות העריכה את ייצור הטנקים הגרמניים באופן דומה במהלך מלחמת העולם השנייה.

בשנות ה-80 מספר אמריקאים קיבלו גישה לקווי הייצור של טנקי מרכבה. היקף הייצור סודי, אך לטנקים היו מספרים סידוריים, שאפשרו להעריך את היקף הייצור שלהם.

### אמצעי הגנה
על מנת להגן מפני ניתוח המבוסס על מספרים סידוריים ניתן להימנע מציונם, או להעניק מספרי ייצור מוצפנים או כאלו שאינם קשורים למספרים המיוצרים בפועל.

## ניתוח שכיחותי

### אינטואיציה
אינטואיטיבית האומד הוא המקסימום במדגם ועוד ההפרש הממוצע בין התצפיות במדגם. המקסימום במדגם נבחר כאומד ראשוני מאחר שהוא אומד נראות מקסימלית, והוספת ההפרש מפצה על ההטיה מטה של המקסימום במדגם לעומת המקסימום באוכלוסייה כולה. 

אם  *m* הוא המקסימום במדגם, ו-*k* הוא מספר הדגימות, הנוסחה תהיה:
:\hat{N} = m + \frac{m - k}{k}

ניתן להמחיש זאת בכך שהדוגמאות נמצאות בהפרש קבוע ביניהן בתוך הטווח, ודוגמאות נוספות נמצאות ממש מעבר לטווח של 0 ו *N*+1. אם מתחילם בהפרש ראשוני של בין 0 למינימום במדגם הפרש הממוצע בין הדוגמאות הוא (m - k)/k; ההחסרה של -k נעשית משום שהדוגמאות עצמן אינן נספרות בהפרש בין הדוגמאות.

הרעיון שבבסיס תיאור זה מנוסחות בצורה פורמלית באמצעות אמידת רווח מקסימלי (maximum spacing estimation).

### אומד חסר הטיה בעל שונות מינימלית
פיתוח של הנוסחה:

\hat{N} = m + \frac{m - k}{k}= m + mk^{-1} - 1 = m\left(1 + k^{-1}\right) - 1

:

עבור אמידה נקודתית (אמידת נקודה יחידה מסה"כ \hat{N}), אומד חסר הטיה בעל שונות מינימלית (minimum-variance unbiased estimator; MVUE) ניתן באמצעות:
\hat{N} = m\left(1 + k^{-1}\right) - 1
כאשר *m* הוא המספר הסידורי הגבוה ביותר שנצפה ו-*k* הוא מספר התצפיות. כאשר מרגע שנצפה מספר סידורי מסוים, הוא לא יצפה בשנית. לכך יש שונות:
 \operatorname{var}(\hat{N}) = \frac{1}{k}\frac{(N-k)(N+1)}{(k+2)} \approx \frac{N^2}{k^2} \text{ for small samples } k \ll N

כך שסטיית התקן היא בערך *N*/*k*, הגודל הממוצע (של האוכלוסייה) של ההפרש בין הדוגמאות; בהשוואה ל *m*/*k* לעיל.

### גזירה
ההסתברות שהמקסימום במדגם הוא *m* ניתנת באמצעות \tbinom{m - 1}{k - 1}\big/\tbinom Nk; כאשר \tbinom \cdot\cdot הוא המקדם הבינומי. בהינתן גודל אוכלוסייה *N* וגודל מדגם *k* התוחלת של המקסימום במדגם היא:
\begin{align}
 \mu &= \sum_{m=k}^N m\frac{\tbinom{m - 1}{k - 1}}{\tbinom Nk} = \frac{k(N + 1)}{k + 1} 
\end{align}

מערך לא ידוע זה ניתן לבטא את N מתוחלת וגודל המדגם: \begin{align}
 N &= \mu\left(1 + k^{-1}\right) - 1
\end{align}

מליניאריות התוחלת מקבלים: \begin{align}
 \mu\left(1 + k^{-1}\right) - 1 &= E\left[m\left(1 + k^{-1}\right) - 1\right] 
\end{align}

ולכן האומד הבלתי מוטה של *N* ניתן באמצעות החלפת התוחלת במדגם ומכאן:
\begin{align}
 \hat{N} &= m\left(1 + k^{-1}\right) - 1.
\end{align}

על מנת להראות שזה אומד שונות מינימלית:
*מראים כי המקסימום במדגם הוא סטטיסטי מספיק עבור המקסימום באוכלוסייה
*שנית מראים כי הוא סטטיסט מלא
* באמצעות משפט להמן-שיף (Lehmann–Scheffé) מראים כי המקסימום במדגם עם תיקון להטיה כמוצג לעיל הוא אומד שונות מינימלית

## ניתוח בייסיאני
הגישה הבייסיאנית לבעיית הטנק הגרמני היא לבחון את ההסתברות של \scriptstyle (N=n\mid M=m, K=k) כך שמספר הטנקים של האויב N שווה ל־n, מספר הטנקים שנצפו K שווה ל־k והמספר הסידורי הגבוה ביותר שנצפה M הוא m. לשם הקיצור נשתמש ב־\scriptstyle (n\mid m,k) לציון \scriptstyle (N=n\mid M=m,K=k).

מכללים של הסתברות מותנת מקבלים: (n\mid m,k) = (m\mid n,k)\frac {(n\mid k)}{(m\mid k)}

הנוסחה \scriptstyle (m\mid n,k)=(M=m\mid N=n,K=k) היא ההסתברות המותנית שהמספר הסידורי הגבוה ביותר שנצפה הוא \scriptstyle m כאשר ידוע שמספר הטנקים של האויב הוא \scriptstyle n ו־\scriptstyle k טנקים נצפו:

 (m\mid n,k) =
 \begin{cases}
 \frac{\binom{m - 1}{k - 1}}{\binom{n}{k}} &\text{if } k \le m \le n\\
 0 &\text{otherwise}
 \end{cases}

כאשר המקדם הבינומי \scriptstyle \binom n k הוא מספר הקבוצות של דוגמאות בגודל \scriptstyle k מאוכלוסייה של \scriptstyle n.

הביטוי \scriptstyle (m\mid k)=(M=m\mid K=k) הוא ההסתברות שהמספר הסידורי המרבי הוא *m* כאשר *k* טנקים נצפו, אך לפני שנצפו המספרים הסידוריים. את \scriptstyle (m\mid k) ניתן לכתוב מחדש במונחים של יתר הנתונים באמצעות סכימה באמצעות האפשרויות השונות של \scriptstyle n:
 (m\mid k)=(m\mid k)\cdot 1 =(m\mid k){\sum_{n=0}^\infty(n\mid m,k)} =(m\mid k){\sum_{n=0}^\infty(m\mid n,k)\frac {(n\mid k)}{(m\mid k)}} =\sum_{n=0}^\infty(m\mid n,k)(n\mid k)

הביטוי \scriptstyle (n\mid k)=(N=n\mid K=k) מתאר את ההסתברות לכך שמספר הטנקים הכולל הוא *n* כאשר *k* טנקים נצפו אך לפני צפייה במספרים הסידוריים. בהנחה שההתפלגות היא התפלגות אחידה (בדידה):

 (n\mid k) = 
 \begin{cases}
 \frac 1{\Omega - k} &\text{if } k \le n 

החסם העליון \Omega חייב להיות סופי כיוון שהפונקציה:  f(n)=\lim_{\Omega\rarr\infty} \begin{cases}
 \frac 1{\Omega - k} &\text{if } k \le n  תקבל \scriptstyle f(n)=0 ואינה פונקציית הסתברות. לכן:

 (n\mid m,k) = 
 \begin{cases}
 \frac{(m\mid n,k)}{\sum_{n=m}^{\Omega - 1} (m\mid n,k)} &\text{if } m \le n 

אם \scriptstyle \sum_{n=m}^\infty(m\mid n,k) אז המשתנה \scriptstyle \Omega מוסר מהנוסחה.


 (n\mid m,k) =
 \begin{cases}
 0 &\text{if } n 

עבור k\geq 1 השכיח של ההתפלגות של מספר הטנקים של האויב הוא *m*.

עבור k\geq 2 ההסתברות שמספר הטנקים שווה ל־n היא: 
 (N=n\mid M=m\ge k,K=k\ge 2) =
 \begin{cases}
 0 &\text{if } n 

וההסתברות שמספר הטנקים של האויב, \scriptstyle N, הוא גדול מ־\scriptstyle n, היא: 
 (N > n\mid M = m \ge k , K = k \ge 2) = 
 \begin{cases}
 1 &\text{if } n 

עבור k\geq 3, מספר הטנקים N הוא בעל ערך תוחלת סופי: \frac{(m - 1)(k - 1)}{k - 2}

עבור k\geq 4, מספר הטנקים \scriptstyle N הוא בעל סטיית תקן סופית של: \sqrt{\frac{(m - 1)(k - 1)(m + 1 - k)}{(k - 2)^2(k - 3)}}

נוסחאות אלו מפותחות להלן.

### נוסחת סכום
הזהות הבאה של המקדם הבינומי תשמש להלן לפישוט סדרות הקשורות לבעיית הטנק הגרמני:
:\sum_{n=m}^\infty \frac 1 {\binom n k} = \frac k{k - 1}\frac 1 {\binom{m - 1}{k - 1}}

סכום זה אנלוגי במידת מה לאינטגרל הבאה:
:\int_{n=m}^\infty \frac {dn}{n^k} = \frac 1{k - 1}\frac 1{m^{k - 1}}

נוסחאות אלו תקפות עבור k > 1.

### טנק יחיד
תצפית בטנק יחיד באקראי מתוך אוכלוסייה של *n* טנקים, ולו מספר סידורי *m* בהסתברות של \frac{1}{n} עבור m \leq n ובהסתברות של אפס עבור m > n. 
. באמצעות שימוש בסוגרי אייברסון ניתן לכתוב זאת:
:(M=m\mid N=n,K=1) = (m\mid n) = \frac{[m \le n]}{n}

זו פונקציית הסתברות מותנית של\scriptstyle m.

כאשר מתייחסים לכך כפונקציה *n* עבור מספר קבוע *m* זו פונקציית נראות:\mathcal{L}(n) = \frac{[n\ge m]}{n}

האומד נראות מקסימלית למספר הטנקים הכולל הוא N_0 = m.

הנראות הכוללת היא אין סוף כזנב של הסדרה ההרמונית:\sum_n \mathcal{L}(n) = \sum_{n=m}^\infty \frac{1}{n} = \infty

אבל, כאשר H_n הוא מספר הרמוני:
:\begin{align}
 \sum_n \mathcal{L}(n)[n 

פונקציית ההסתברות אשר תלויה בהגבלה \scriptstyle \Omega הניתנת כידע מוקדם:
:\begin{align}
 &(N=n\mid M=m,K=1) \\
 = {} &(n\mid m) = \frac{[m\le n]}{n} \frac{[n

התוחלת של \scriptstyle N היא:
:\begin{align}
 \sum_n n\cdot(n\mid m) &= \sum_{n=m}^{\Omega - 1} \frac{1}{H_{\Omega - 1} - H_{m - 1}} \\
 &= \frac{\Omega - m}{H_{\Omega - 1} - H_{m - 1}} \\
 &\approx \frac{\Omega - m}{\log\left(\frac{\Omega - 1}{m - 1}\right)}
\end{align}

### שני טנקים
אם נצפים שני טנקים, אז ההסתברות שזה עם המספר הסידורי הגדול יותר שווה ל־*m*, היא

:(M=m\mid N=n,K=2) = (m\mid n) = [m \le n]\frac{m - 1}{\binom{n}{2}}

כאשר מתייחסים לכך כפונקציה של *n* עבור *m* קבוע זו פונקציית נראות:
:\mathcal{L}(n) = [n \ge m]\frac{m - 1}{\binom{n}{2}}

הנראות הכוללת היא:
:\begin{align}
 \sum_{n}\mathcal{L}(n) &= \frac{m - 1}{1} \sum_{n=m}^\infty \frac{1}{\binom n 2} \\
 &= \frac{m - 1}{1} \cdot \frac{2}{2 - 1} \cdot \frac{1}{\binom {m - 1}{2 - 1}} \\
 &= 2
\end{align}

ופונקציית ההסתברות של מספר הטנקים הכולל N כתלות בתצפית במספר הסידורי הגדול m ובצפייה בשני טנקים היא:

:\begin{align}
 &(N=n\mid M=m,K=2) \\
 = {} &(n\mid m) \\
 = {} &\frac{\mathcal{L}(n)}{\sum_n \mathcal{L}(n)} \\
 = {} &[n \ge m]\frac{m - 1}{n(n - 1)}
\end{align}

החציון \scriptstyle \tilde{N} מקיים: \sum_n [n \ge \tilde{N}](n\mid m) = \frac{1}{2}

ולכן: \frac{m - 1}{\tilde N - 1} = \frac{1}{2}. מכאן שערך החציון הוא: \tilde{N} = 2m - 1

אך התוחלת של *N* היא אינסופית: \mu = \sum_n n \cdot (n\mid m) = \frac{m - 1}1\sum_{n=m}^\infty \frac{1}{n - 1} = \infty

### טנקים רבים
ההסתברות המותנית שהערך הגדול מבין *k* תצפיות של מספרים סידוריים {1,...,*n*}, שווה ל־*m*, היא:
:\begin{align}
 &(M=m\mid N=n,K=k\ge 2) \\
 = {} &(m\mid n,k) \\
 = {} &[m\le n]\frac{\binom{m - 1}{k - 1}}{\binom{n}{k}}
\end{align}

פונקציית הנראות של *n* היא:
:\mathcal{L}(n) = [n \ge m]\frac{\binom{m - 1}{k - 1}}{\binom{n}{k}}

הנראות הכוללת היא סופית עבור k \geq 2:
:\begin{align}
 \sum_n \mathcal{L}(n)
 &= \frac{\binom{m - 1}{k - 1}}{1} \sum_{n=m}^\infty {1 \over \binom n k} \\
 &= \frac{\binom{m - 1}{k - 1}}{1} \cdot \frac{k}{k-1} \cdot \frac{1}{\binom{m - 1}{k - 1}} \\
 &= \frac k{k - 1}
\end{align}

פונקציית ההסתברות של מספר הטנקים הכולל N כתלות בתצפית עם הערך הגדול ביותר m מ-k תצפיות היא:
:\begin{align}
 &(N=n\mid M=m,K=k \ge 2) = (n\mid m,k) \\
 = {} &\frac{\mathcal{L}(n)}{\sum_n \mathcal{L}(n)} \\
 = {} &[n\ge m]\frac{k-1}{k} \frac{\binom{m - 1}{k - 1}}{\binom n k} \\
 = {} &[n\ge m]\frac{m-1}{n} \frac{\binom{m - 2}{k - 2}}{\binom{n - 1}{k - 1}} \\
 = {} &[n\ge m]\frac{m-1}{n} \frac{m - 2}{n - 1} \frac{k - 1}{k - 2} \frac{\binom{m - 3}{k - 3}}{\binom{n-2}{k-2}}
\end{align}

התפלגות הזנב (המשלים לפונקציית הצטברות) עבור N > x:
:\begin{align}
 &(N>x\mid M=m,K=k) \\
 = {} &\begin{cases}
 1 &\text{if }x 

פונקציית ההצטברות עבור N \leq x:
:\begin{align}
 &(N\le x\mid M=m,K=k) \\
 = {} &1 - (N>x\mid M=m,K=k) \\
 = {} &[x \ge m]\left(1 - \frac{\binom{m - 1}{k - 1}}{\binom{x}{k - 1}}\right)
\end{align}

## דוגמה
נניח כי קצין מודיעין צפה בארבעה טנקים בעלי מספרים סידוריים 2, 6, 7 ו-14. נסמן את מספר הטנקים בהם צפה ב-k=4 ואת המספר הסידורי המרבי שנצפה ב-m=14. מספר הטנקים של האויב, שאותו נסמן ב-N, אינו ידוע ואותו רוצים להעריך על פי תצפיות אלו.

הערכה למספר הטנקים של האויב על פי הגישה השכיחותית:
:N \approx m + \frac{m}{k} - 1 = 16.5

לעומת זאת הערכה בייסיאנית של מספר הטנקים:
:\Pr(N=n) = \begin{cases}
 0 &\text{if } n 

ועל פי ההערכה זו נוכל לאמוד את מספר הטנקים כך:

:\begin{align}
 N &\approx \mu \pm \sigma = 19.5 \pm 10 \\
 \mu &= (m - 1)\frac{k - 1}{k - 2} \\
 \sigma &= \sqrt{\frac{(k-1)(m-1)(m-k+1)}{(k-3)(k-2)^2}}
\end{align}

להתפלגות זו צידוד חיובי, הקשור לכך שמספר הטנקים אינו קטן מ-14.

## לקריאה נוספת

* 


## הערות שוליים

קטגוריה:מתמטיקה שימושית
קטגוריה:התפלגויות
קטגוריה:בעיות נודעות בהסתברות