את הפתרון הזה ראיתי לפני שהספקתי לחשוב עליו לבד, ולא בטוח שהייתי מגיע אליו, כי הוא מסתמך על ייצוג מספרים שמעולם לא יצא לי להשתמש בו. הרעיון הוא, קודם כל, לנסח את הסיכוי הרצוי כמספר בין 0 ל-1 (למשל, סיכוי של 1 ל-6 הוא 0.16667), ואז לייצג את המספר הזה כסכום מכפלות של מקדמים בינאריים בסדרה של שברים הולכים-וקטנים, שמבוססים גם הם על חזקות של שתיים.
לא ברור, נכון? אז כדי להבהיר את העניין, השבר הראשון בסדרה הוא חצי (1/2), השני הוא חצי של חצי (1/4), השלישי חצי של הקודם (1/8) וכן הלאה, ואנחנו יכולים לכפול כל אחד מהם ב-0 או ב-1 עד שנגיע לסכום הכולל 0.16667, לפחות עד רמת הדיוק הרצויה לנו. אתם מוזמנים לבדוק עם נייר ועפרון, או באקסל כמו שאני עשיתי, ולראות שסדרת המקדמים (הביטים) שמייצגים את המספר הזה היא, משמאל לימין:
.0010101010101100110110011110…
ועכשיו מגיע הטריק. אני מתחיל להטיל את המטבע ההוגנת שוב ושוב, עד שאני מקבל "עץ". נניח שזה לקח N הטלות. אני מסתכל על הביט ה-N ברצף שלמעלה (מתחילים לספור מ-1), ואם הערך שלו 1 אני אכריז על התוצאה הסופית כ"הצלחה", אחרת כ"כשלון"!
כמו במספר בינארי "רגיל", בייצוג הזה של אחרי-הנקודה יש חשיבות גם לערך של כל ביט וגם למיקום שלו. הסיכוי לתוצאה "הצלחה" מגולם בתוך כל הביטים ברצף שהם "1", והטלת המטבע עד שמתקבל "עץ" מספקת לנו את המרכיב האקראי לבחירת ביט – תוך התחשבות במשקל שלו. הביט השמאלי, שמייצג את החלק הכי גדול ממרחב ההסתברות, הוא זה שגם יתקבל בסבירות הכי גבוהה (הרי חצי מההטלות במטבע ההוגנת הן "עץ"). השני משמאל, שמייצג רבע נוסף ממרחב ההסתברות, יתקבל בחצי מהמקרים הנותרים, וכן הלאה.
הפתרון הזה הוא גם יעיל יותר, כי מספר ההטלות הממוצע (תוחלת) הדרוש כדי להגיע לתשובה הוא 2 בלבד! אם כי, כמו תמיד בסטטיסטיקה, יכול להיות בתיאוריה מצב בו נטיל את המטבע גם 80 פעמים ברצף עד שנקבל את ה"עץ" המיוחל…
עד כאן זו הייתה חידה מתמטית בלבד: לפחות כרגע, אני לא רואה יתרון מעשי שלה במחשבים או במיקרו-בקרים שצריכים להגריל מספרים אקראיים. אבל צורת ההתייחסות שלה לביטים הזכירה לי טריק נחמד לקביעת בהירות נתפסת של לדים כאשר אין לנו מספיק ערוצי PWM פנויים בחומרה.
בטריק הזה, אנחנו מקדישים לכל לד (ליתר דיוק, לכל פין פלט ששולט בלד) בייט אחד, שמכיל את ערך הבהירות הרצוי – מ-0 עד 255. אנחנו גם מריצים טיימר כך שייתן לנו, במחזוריות, שמונה פרקי זמן שכל אחד מהם ממושך פי שניים מזה שלפניו – למשל 1, 2, 4, 8, 16, 32, 64 ו-128 מיליוניות השנייה. בכל פרק זמן כזה, אנחנו מדליקים את כל הלדים שהביט המקביל בבייט שלהם הוא 1, ומכבים את אלה שהביט המקביל הוא 0. לדוגמה, אם ערך הבהירות שבחרנו ללד מסוים הוא 1, בייצוג בינארי 00000001, אז הוא ידלוק רק במשך פרק הזמן הקצר ביותר, מיליונית שנייה אחת; ואם בחרנו 96 עשרוני, שזה 01100000 בבינארי, הלד ידלוק בפרקי הזמן השישי והשביעי, סה"כ 96 מיליוניות שנייה.
כל עוד פרקי הזמן ארוכים מספיק לביצוע החישובים הדרושים, מצד אחד, וקצרים מספיק כדי למנוע הבהוב נראה-לעין מצד שני, התוצאה הסופית היא שכל לד דולק בדיוק בחלק היחסי של ערך הבייט שלו מתוך 255!
הפתרון האחרון מאוד מגניב 😀
חידת המשך היא איך להפוך את ה"מטבע הלא מאוזן" שיש לנו ל"קוביה לא מאוזנת עם N פיאות", כלומר במקום להגריל תוצאה מבין 2 מאורעות, להגריל תוצאה מבין N מאורעות בהסתברויות שרירותיות כלשהן.
כבר יש לכם את כל הכלים שאתם צריכים 🙂
הפתרון הזה שקול לקירוב המאורע עם ההסתברות שאנחנו רוצים (נניח 1 ל-6 בדוגמה שלך) ע"י סכום של מאורעות בלתי תלויים עם הסתברות מהצורה 2 בחזקת (n-). למשל, אם רוצים לקבל מאורע כלשהו בהסתברות 0.6 אז ננסה לקרב אותו ע"י איחוד של מאורעות בלתי תלויים שסכום ההסתברויות שלהם הוא 0.6. נתחיל מהמאורע "סדרת ההטלות מתחילה ב-1" (אני מחליף פה את העץ והפלי ב-0 ו-1 בשביל הנוחות). ההסתברות למאורע הזה הוא 0.5, לכן אנחנו צרכים עכשיו למצוא עוד מאורעות שיתנו לנו הסתברות של 0.1. המאורע הבא שנותן לנו הסתברות קטנה או שווה ל0.1 הוא מאורע מהסגנון "סדרת ההטלות מתחילה ב-0001" שהיא גם… לקרוא עוד »
היה נראה לי משום מה שהתגובות הן פר עמוד.
הפתרון פה מתייחס לפתרון של החידה מעמוד 3.