בתשובה לעומר, 04/06/24 15:43
על מה יש להצטער 769234
יובל נוב • בתשובה לעומר יום ג', 4/6/2024, 19:28
הניחוש שלך נכון, זה הכיוון שחשבתי עליו. איך אפשר לשפר את הסיבוכיות?
על מה יש להצטער 769262
עומר • בתשובה ליובל נוב יום ד', 5/6/2024, 13:40
אלגוריתם אחד, שהוא בעיני לא פחות מיפהפה, מכונה בד"כ Alias Method והוא מבוסס על התבנית הרעיונית של rejection sampling - רק אלגנטי פי 100 ממה שבד"כ מקבלים מהכיוון הזה. חשוב מה היה קורה אילו היינו מגרילים מהתפלגות אחידה במקום מההתפלגות הנתונה: אז אברים שהסתברותם נמוכה מ-p=1\n היו נדגמים יותר מידי, ואיברים שהסתברותם גבוהה מכך היו נדגמים פחות מידי. אפשר לקוות לתקן זאת: אם הגרלנו איבר שהסתברותו נמוכה, אז נבצע הגרלה נוספת, ובהסתברות כלשהי(?) נחזיר אותו ואחרת... נחזיר איבר אחר כלשהו? כך שהכל יסתדר?

על פניו בכלל לא ברור ששטיק כזה יכול לעבוד, אבל מסתבר שהוא עובד מושלם: אפשר תמיד להתאים לכל איבר i שהסתברותו נמוכה (ולכן סובל מדגימת-יתר) "הסתברות דחייה" p_i ואיבר אלטרנטיבי קבוע j_i שהסתברותו גבוהה (ולכן סובל מדגימת-חסר) באופן כזה שבסופו של דבר כולם נדגמים בדיוק בהסתברות המתאימה להם. את הבנייה הזו אפשר לעשות באופן מחוכם למדי ב-o(n), ואח"כ כל דגימה מבוצעת טריוויאלית בסיבוכיות זמן של o(1). האלגוריתמיקה עצמה אלגנטית‏1, אבל החיבה הגדולה שלי לאלגוריתם הזה נובעת מכך שזה בכלל עובד. ולמרות שלא נורא קשה לראות (לפחות בדיעבד) למה הוא נכון, אישית אני עדיין לא משתחרר מהתחושה שמדובר בקסם‏2.

אלגוריתם אחר, עם סיבוכיות דומה אך trade-offs שונים, שגם לו מעלות אסתטיות רבות, מבוסס על בניית סדרה של lookup-tables בהתאם לבסיס-ספירה ודיוק-עשרוני שנבחרו מראש כמתאימים לייצוג ההסתברויות הנתונות והגרלה מתוכם. יהיה קשה לתאר את הפרטים בפורמט של האייל, אבל אני מתאר לעצמי שלא תתקשה למצוא רפרנס אם תתעניין.

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

‏1 ונמצאת על סיפה של מחילת ארנב מעניינת בפני עצמה, כי הבניה אינה יחידה, ומסתבר (אני מקווה שאני זוכר נכון...) שמציאת בנייה אופטימלית היא בעיית NP קשה.
‏2 יש להודות שחלק ניכר מהאהבה שלי למתמטיקה כנראה מוסבר ע"י טפשות שמפריעה לי להבין דברים עד הסוף, כך שאני נותר תמיד עם תחושה של עיסוק באיזושהי תורת סוד מיסטית במקום בדיסציפלינה האנליטית והמכניסטית מכולן.
‏3 משחקים בהם תפקיד מרכזי ולא תמיד צפוי גם האנטרופיה של ההסתברות, גם המימד של המרחב וגם פרטי הייצוג הנומרי של ההסתברויות עצמן.
על מה יש להצטער 769265
אח של אייל • בתשובה לעומר יום ד', 5/6/2024, 15:03
אם ההסתברויות הן: 0.1, 0.29 ,0.3, 0.31
אז איך האלגוריתם הראשון עובד?
על מה יש להצטער 769269
עומר • בתשובה לאח של אייל יום ד', 5/6/2024, 16:12
ההגרלה תעבוד כך: בחר אינדקס אקראי בין 0 ל-‏1.
* אם קיבלת 0: בהסתברות 0.4 החזר 0, ואחרת החזר 3.
* אם קיבלת 1: תמיד החזר 1.
* אם קיבלת 2: בהסתברות 0.84 החזר 2, אחרת החזר 1.
* אם קיבלת 3: בהתסברות 0.64 החזר 3, אחרת החזר 2.

נבדוק:
* ההסתברות לקבל 0: 0.4*0.25 = 0.1.
* ההסתברות לקבל 1: (1-0.84)*0.25+0.25 = 0.29
* ההסתברות לקבל 2: 0.84*0.25 + (1-0.64)*0.25 = 0.3
* ההסתברות לקבל 3: 0.64*0.25 + (1-0.4)*0.25 = 0.31

אם אתה רוצה לדעת איך קיבלתי את ההסתברויות והבחירות האלטרנטיביות האלה בסיבוכיות של o(n), ראה כאן.
על מה יש להצטער 769270
עומר • בתשובה לעומר יום ד', 5/6/2024, 16:14
(את האינדקס בחר, כמובן, בין 0 ל-‏3 - כולל).
על מה יש להצטער 769271
יובל נוב • בתשובה לעומר יום ד', 5/6/2024, 17:32
(אני מבין שהראש שלך עובד בפייתון / C, ולא ב-R / מטלאב.)

ותודה על האלגוריתם, לא הכרתי.
על מה יש להצטער 769272
אח של אייל • בתשובה לעומר יום ד', 5/6/2024, 17:45
תודה על ההסבר.

בתגובה המקורית דובר על כך שאיברים שקיבלו "יותר מדי" (למשל האיבר הראשון שקיבל 25 במקום 10) צריכים לתרום חלק למישהו אחר.

עכשיו אני רואה שלפעמים איברים שקיבלו "מעט מדי" (כמו האיבר השלישי שקיבל 25 במקום 30) צריך לתרום, אבל איכשהו זה מתקזז (האיבר השלישי תרם 4 וקיבל 9 וזה הביא את המאזן שלו ל 30).

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