שאלה בהסתברות (נובעת מתרגיל בקריפטוגרפיה)

[fudge]

אפשר לתאר את הבעיה כ-N^2 וילונות, שמאחורי N מהם יש משהו שאני צריך. השאלה היא - כמה וילונות צריך לפתוח, כדי שההסתברות ליפול על וילון "נכון" תהיה גדולה מחצי?

[Flying Python]

יש לי כמה שאלות: (אני אסמן ב-http://www.codecogs.com/gif.latex?n את מספר הוילונות שאתה פותח בפועל.)

1. אפשר להניח ש-http://www.codecogs.com/gif.latex?N גדול ממש יחסית ל-http://www.codecogs.com/gif.latex?n?

2. מה התכוונת לחשב? אפשרויות א'/ב': פותחים בכל מקרה http://www.codecogs.com/gif.latex?n וילונות, ורוצים שההסתברות שנפלנו על וילון "נכון" (אחד או יותר/בדיוק אחד) תהיה גדולה מחצי.

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

[radagast]

סביר להניח שאני מחטיא פה את הכוונה, אבל בוא נראה:

 

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

אם כן, אז מדובר במספר האפשרויות לבחור ב-M וילונות מתוך N^2-N וילונות (כלומר N^2-N בחר M), חלקי N^2 בחר M - כל האפשרויות לבחור M וילונות.

ההסתברות המבוקשת היא 1 פחות זה.

הבעיה היא שמכאן אתה צריך לנחש עבור איזה M ההסתברות תעבור את 0.5, או לפתח ביטוי אנליטי סביר ולפתור.

[fudge]

Flying Python, התכוונתי לאפשרות ג'. לא חושב שאפשר להניח את מה שאמרת, לכל היותר אולי ש-n קטן יחסית ל-N^2.

 

radagast, הגעתי לביטוי הזה אבל אני לא כ"כ יודע איך מנתחים אותו..

[Flying Python]

זה לא קצת סותר? radagast אאל"ט התייחס לאפשרות א'.

 

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

אחרת (אפשרויות א', ב' וג', ובלי הנחות על http://www.codecogs.com/gif.latex?N), קיבלתי ביטויים שדי קשה לנתח אנליטית (אלא אם כן פספספתי משהו).

(אבל אולי אפשר לקרב אותם.)

[radagast]

אתה יכול להשתמש, אולי, בקירוב סטירלינג*, אבל גם אז כנראה שיהיה לך יותר טוב אם תניח כל מיני תנאים על M ביחס ל-N...

 

 

* http://en.wikipedia.org/wiki/Stirling%27s_approximation

 

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

[username]

בוא תחשב תחילה את ההסתברות להיכשל בk ניסויים (כפל של k ליטרלים כאשר i נע בין 1 ל-k(: 

    N

 -------   -1

 N^2-i

כל איבר כזה אתה יכול לחסום מלמעלה ע"י א"ש הבא:

exp(-x) > 1 -x.

מפה עם קצת ארימטיקה תגיע לביטוי שתוכל לחסום ע"י 1/2 ומשם לחלץ את K. 

[fudge]

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

[radagast]

כיוון ש-N גדול מאוד, ומניחים/מקווים למספר בחירות מסדר N, ו - N^2>>N,

 

Why didn't you list that among our assets?

 

http://thehouseholderspath.files.wordpress.com/2012/09/princess-bride.jpg

[fudge]

:-)

 

Python שאל אם אפשר להניח ש-N גדול ממש מ-n ואת זה בפירוש אי אפשר היה להניח, אבל הייתי צריך לציין לגבי N^2