ההסתברות של מספרים זרים ואיך פאי נכנס לתמונה

באחת מהתגובות בבלוג שאלו אותי שאלה פשוטה – נניח שאנחנו מגרילים באקראי שני מספרים טבעיים, מה ההסתברות שהם יהיו זרים, כלומר שלא יהיה מספר טבעי גדול מ-1 שמחלק את שניהם גם יחד? התשובה היא $latex \frac{6}{\pi^{2}}$, מה שנראה מוזר מאוד במבט ראשון – מה פאי עושה כאן, הרחק מכל מעגל אפשרי?

ותיקי הבלוג אולי מזהים את ה-$latex \frac{6}{\pi^{2}}$ הזה. באחד הפוסטים הקודמים הראיתי שמתקיים $latex \sum_{n=1}^{\infty}\frac{1}{n^{2}}=\frac{\pi^{2}}{6}$, וגם שלטור הזה יש סימון קצת יותר קומפקטי – $latex \zeta\left(2\right)$, פונקצית הזטא של רימן ב-2. הקשר אינו מקרי, כמובן, ובהוכחה נתבסס על הטענה הישנה ההיא ועל רעיונות שהצגתי כבר אז. קודם כל אציג את ההוכחה, ולאחר מכן, עבור אלו שעדיין יש להם כוח, נעבור לדבר על השאלה; מסתבר ש"מגרילים באקראי שני מספרים טבעיים" זו טענה שהיא די חסרת משמעות – לפחות המשמעות האינטואיטיבית שלה שגויה – וצריך לחדד קצת את השאלה כדי שתהיה משמעות לתשובת ה-$latex \frac{6}{\pi^{2}}$. אבל תשכחו מזה לעת עתה – ההוכחה שאציג כעת היא הרעיון המרכזי כאן. זו תהיה "הוכחה בסגנון אוילר" עם כמה הנחות לא מבוססות ואי דיוקים, אבל מרגע שהרעיון יהיה ברור באמצעותה, מי שירצה יוכל להבין גם איך מפרמלים אותה כמו שצריך.

ראשית, מתי שני מספרים הם זרים? כשאין להם גורם משותף; אבל למעשה, מספיק לומר שאין להם גורם ראשוני משותף, מכיוון שכל גורם שהוא של אותם שני מספרים מתחלק לפחות בראשוני אחד. אז השאלה שלנו היא למעשה – אם אנחנו בוחרים שני מספרים באקראי, מה ההסתברות שיהיה ראשוני $latex p$ שמחלק את שניהם?

מכיוון שהבחירה של שני המספרים נעשית באופן בלתי תלוי (הבחירה במספר אחד לא משפיעה על הבחירה במספר השני), ההסתברות ששניהם יתחלקו ב-$latex p$ היא מכפלת ההסתברויות עבור כל אחד מהם להתחלק ב-$latex p$. כעת, $latex p$ מחלק אחד מכל $latex p$ מספרים (2 מחלק כל מספר זוגי; 3 מחלק, ובכן, כל מספר שמתחלק ב-3, וכן הלאה) ולכן ההסתברות לכך שמספר אקראי יתחלק ב-$latex p$ היא $latex \frac{1}{p}$, ולכן ההסתברות ששני מספרים אקראיים יתחלקו שניהם ב-$latex p$ היא $latex \frac{1}{p^{2}}$.

כעת, אנחנו רוצים שלמספרים שלנו לא יהיה אף גורם משותף, כלומר שלכל ראשוני $latex p$, לא יתקיים ש-$latex p$ מחלק את שניהם. אם $latex \frac{1}{p^{2}}$ היא ההסתברות ש-$latex p$ כן יחלק את שני המספרים האקראיים, אז ההסתברות ה"משלימה", לכך שהוא לא יחלק את שניהם (כלומר, יחלק רק אחד מהם או לא יחלק אף אחד מהם) היא $latex 1-\frac{1}{p^{2}}$. ההסתברות שזה יקרה לכל הראשוניים הקיימים (בהנחה שאיני מוכיח כאן – כפי שתגובות רבות מעירות – שההסתברויות לראשוניים שונים הן בלתי תלויות) היא מכפלת ההסתברויות לכל הראשוניים; מה שמסומן במתמטית בתור $latex \prod_{p}\left(1-\frac{1}{p^{2}}\right)$ ($latex \Pi$ הוא סימן קיצור מוסכם לכפל, כמו ש-$latex \Sigma$ הוא סימן קיצור מוסכם לחיבור; ויש הסכמה על כך שה-$latex p$ למטה עובר רק על הראשוניים). המכפלה הזו נראית מוזרה במבט ראשון כי משתתפים בה אינסוף איברים, וצריך להגדיר לה מושג של התכנסות כפי שמוגדר כזה עבור סכום אינסופי, אבל כאמור – אנחנו עכשיו עושים הוכחה בסגנון אוילר.

בשלב הזה אני שולף מהבוידם את התעלול של אוילר שהצגתי כבר בבלוג בעבר: אוילר מראה כי $latex \zeta\left(s\right)$, הערך של פונקצית הזטא של רימן בנקודה $latex s$ עבור $latex s>1$ ממשי, שמוגדר כ-$latex \sum_{n=1}^{\infty}\frac{1}{n^{s}}$, מקיים $latex \zeta\left(s\right)=\prod_{p}\left(\frac{1}{1-p^{-s}}\right)$. הרעיון הכללי כאן הוא ש-$latex \frac{1}{1-p^{-s}}$ זו בעצם דרך אחרת לכתוב $latex 1+p^{-s}+p^{-2s}+p^{-3s}+\dots$, ומכיוון שהכפל רץ על כל הראשוניים ובשל הפירוק היחיד לראשוניים של המספרים הטבעיים, כשמבצעים פתיחת סוגריים מקבלים את כל האיברים מהצורה $latex n^{-s}$, לכל $latex n$ אפשרי. זהו מעין אפיון אנליטי של המשפט היסודי של האריתמטיקה, ותוצאה יפהפה בכל קנה מידה אפשרי לטעמי.

הביטוי שלנו די דומה: השוו את $latex \prod_{p}\left(1-\frac{1}{p^{2}}\right)$ עם $latex \prod_{p}\left(\frac{1}{1-p^{-2}}\right)$. איך עוברים מאחד לשני? ובכן:

$latex \prod_{p}\left(1-\frac{1}{p^{2}}\right)=\prod_{p}\left(1-p^{-2}\right)=\prod_{p}\left(\frac{1}{1-p^{-2}}\right)^{-1}=\left[\prod_{p}\left(\frac{1}{1-p^{-2}}\right)\right]^{-1}=\zeta\left(2\right)^{-1}=\frac{6}{\pi^{2}}$

וזה סוף הסיפור.

למה הסיפור בכל זאת לא נגמר כאן? כי כאמור, קצת רימיתי בהתחלה. כשאני אומר ש"מספר טבעי נבחר באקראי", מה זה אומר? אם רוצים לדבר פורמלית צריך להסביר מהי ההסתברות שיש לכל מספר טבעי להיבחר, וההנחה הסמויה כאן היא שההסתברות של כל מספר טבעי היא שווה. נאמר, $latex a$, כש-$latex a$ הוא מספר גדול מ-0 וקטן מ-1. מייד אנחנו רואים שיש כאן בעיה כי אחרי $latex \frac{1}{a}$ מספרים, ההסתברות שאחד מהם יצא תהיה גדולה כבר מ-1…

לדוגמה, אם אני אומר שכל מספר טבעי נבחר באותה הסתברות – $latex \frac{1}{5}$ – אז אני אומר שגם 1, וגם 2, וכדומה עד 6 – כולם נבחרים בהסתברות $latex \frac{1}{5}$. אז ההסתברות שאחד מהם ייבחר היא $latex \frac{1}{5}+\dots+\frac{1}{5}=\frac{6}{5}$, ומספר זה כבר גדול מ-1. זה פשוט לא עובד. אין התפלגות אחידה על כל הטבעיים.

אפשר כמובן להגדיר התפלגויות לא אחידות (למשל, המספר $latex n$ נבחר בהסתברות $latex \frac{1}{2^{n}}$) אבל אז כל הניתוח ההסתברותי שעשינו למעלה והניח שלכל מספר טבעי אותה הסתברות להיבחר יורד לטמיון. אז מה עושים?

הפתרון הוא כזה: קובעים $latex N$ גדול כלשהו, ומגרילים רק מספרים בין 1 ל-$latex N$, כשכל אחד מהם נבחר בהסתברות $latex \frac{1}{N}$. כעת חוזרים על ההוכחה שלמעלה; לצורך נוחות טכנית אפשר לבחור את $latex N$ תמיד להיות כפולה של כל הראשוניים עד לראשוני מסויים, ואז רק הם משתתפים במשחק ואף ראשוני אחר לא. מה שנקבל בסוף הוא את המכפלה $latex \prod_{p}\left(1-\frac{1}{p^{2}}\right)$ כשהיא אינה נלקחת על כל הראשוניים אלא רק עד גבול מסויים; אבל ככל שנגדיל את $latex N$ כך המכפלה הזו תשאף לערך של המכפלה האינסופית, שהוא $latex \frac{6}{\pi^{2}}$ המבוקש. לכן הניסוח המדויק של השאלה מתחילת הפוסט הוא זה "כאשר בוחרים מספרים טבעיים באקראי מתחום גדול מאוד, מה בערך ההסתברות שהם יהיו זרים?" ולמי שזה לא מספיק פורמלי עבורו, "לאן שואפת ההסתברות ששני מספרים טבעיים שנבחרו בהתפלגות אחידה מתוך $latex \left[1,\dots,N\right]$ יהיו זרים כאשר $latex N$ שואף לאינסוף"?

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

19 תגובות בנושא “ההסתברות של מספרים זרים ואיך פאי נכנס לתמונה”

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

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

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

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

    חשבתי ש"התעלול של אוילר" הוא באמת תוצאה יפה ביותר.

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

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

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

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

    אני משתמש בהצלחה רבה בשיטה הנ"ל, (ובטכניקות דומות לה), כתחליף לחיי מין.

  6. אני לא רואה איך בחירה של N כמכפלת ראשוניים עוזר לנו. עדיין יש ראשוניים קטנים מ-N שאינם מחלקים אותו והחישוב שלך מתעלם מהם.

  7. ווריאציה קצת אחרת לפרדוקס הכובע, שמבלבלת גם מתמטיקאים, ומדגימה את הבעיתיות של המושג "מספר אקראי":
    מוצגות לך שתי מעטפות. באחת סכום כסף כפול מהשניה.
    אתה בוחר אחת מהן באקראי ומצאת בפנים 100 ש"ח. כעת ניתנת לך האפשרות להחליף את המעטפה.
    מכיוון שבחרת מעטפה באקראיות מוחלטת, 50% שיש במעטפה השניה 200 ש"ח ו-50% שיש בה 50 ש"ח. התוחלת היא 125 ש"ח, ולכן כדאי להחליף.
    כמובן שהשיקול הזה נכון תמיד: לגבי כל סכום של X שקלים במעטפה השניה יש בתוחלת 1.25X.
    המסקנה היא שאתה לא צריך אפילו לפתוח את המעטפה כדי לדעת שמשתלם להחליף אותה.
    ובצורה מפורשת יותר: אם תבחר מעטפה ומיד תחליף אותה, תקבל, בממוצע, יותר כסף.

  8. דניאל, אתה צודק, גם כאן אני משקר 🙂

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

    עידו, יש פוסט על פרדוקס המעטפות:

    http://www.gadial.net/?p=146

  9. בשביל להכפיל הסתברויות לא צריך שמאורעות יהיו זרים?

    מכפילים את ההסתברות ש2 לא יהיה גורם משותף
    בהסתברות ששלוש לא יהיה גורם משותף

    אבל אלו לא מאורעות זרים

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

  10. זהו, בלתי תלויים – לזה התכוונתי.
    כלומר אם 2 הוא לא גורם משותף אזי 6,12 הם כבר לא זוג אפשרי (לדוגמא)
    וזה משפיע על ההסתברות ששלוש הוא לא גורם משותף.

    או שלא, כי בטח אפשר להראות שההסתברות לא השתנתה לאחר הורדת כל הזוגות ששתיים הוא הגורם המשותף בהם.
    זו ההשמטה המדוברת?
    או שאני מפספסת?

  11. גדי אני חושב שבשורה האחרונה בתגובתך התכוונת לכתוב "בלתי-תלויים" ולא "זרים".

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

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

  13. פוסט יפה מאוד, מעניין ומושקע.

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

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

כתיבת תגובה

האימייל לא יוצג באתר. שדות החובה מסומנים *