שיטת זיגורט

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

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

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

השיטה

הסבר גרפי על מימוש השיטה

הבסיס של השיטה הוא שמגרילים מספרים וזורקים את המספרים שלא מתאימים לתנאים שלנו ושומרים את האחרים כך שהמספרים שאנו שומרים יוצרים את ההתפלגות הרצויה. כדי ליישם את השיטה נדרש לחלק את ההתפלגות הרצויה ל-N רמות של y, כאשר בכל הרמות השטחים ששייכים להתפלגות זהים. ככל שה-N יהיה גדול יותר כך התוצאה שתתקבל תשאף להתפלגות. בכל רמה יוצרים מלבן כך שהמלבן מוגבל ברמה הנוכחית וזו שמעליה, בציר ה-y ובערך של פונקציית ההתפלגות של הרמה הנוכחית וזו שמעליה ז"א שפינות המלבן של רמה 2, בהנחה שפונקציית ההתפלגות היא f, יהיו ((x1,f(x2) ו-((x3,f(x3). בדרך זו נוצרו N-1 מלבנים כאשר הרמה הנמוכה ביותר (נקרא לה רמה 0) נשאר הזנב של ההתפלגות שבדרך כלל לא ניתן לחסום אותו במלבן ולכן הטיפול בו יהיה שונה. כל הרמות יחד מכסות את כל שטח פונקציית ההתפלגות. בשיטה זו בוחרים מספר אקראי אחד שנותן את מספר הרמה ולאחר מכן מגרילים מספר אקראי נוסף בגבולות של המלבן באותה רמה. את המספר שהתקבל בודקים אם הוא נמצא מתחת לפונקציית ההתפלגות או לא, כאשר הבדיקה נעשית לקירוב לקו ליניארי של פונקציית ההתפלגות בקטע זה.

האלגוריתם לשמירת המספר שהתקבל בכל ברמות לא כולל רמה 0

1. בוחרים מספר רמה בין 0 ל-N.
2. אם הרמה היא 0, עוברים לאלגוריתם שבהמשך.
3. מגרילים מספר $U_{0}=Unif[0,x_{i}]$.
4. אם $x<x_{i+1}$ מחזירים x.
5. אם לא, מגרילים מספר אקראי נוסף $U_{1}=Unif[0,1]$ ומחשבים $Y=Y_{i}+U_{1}*(Y_{i+1}-Y_{i})$
6. אם $Y<f(x)$ מחזירים x.
7. אחרת, חוזרים לשלב 1.

הערה: האלגוריתם מתאים גם להסתברות לא סמטרית אך נדרש להתאים את גבולות המשתנים האקראיים וכן את התנאים.

האלגוריתם לזנב

האלגוריתם לכל הרמות מלבד הזנב מהיר מאוד, מלבד ברמה 0 בה האלגוריתם מסובך יותר ולא תמיד ניתן לחישוב בדרך ישירה ופשוטה. החישוב לזנב תלוי בהתפלגות. למשל עבור התפלגות מעריכית ניתן להשתמש בלוגריתם של המספר האקראי U1 ולתת ל-x להיות $x=x_{1}-ln(U1)$. אפשרות אחרת היא להוסיף לכל ה-x את x1.

להתפלגות נורמלית, מרסגליה הציע להשתמש באלגוריתם הבא:

1. נבחר משתנה אקראי U1 כמו בכל רמה ונחשב $x=-ln(U_{1})/x_{1}$
2. נבחר משתנה אקראי U2 כמו בכל רמה ונחשב $y=-ln(U_{2})$
3. אם $2y>x^{2}$, תחזיר x+x1. אחרת, חזור לשלב 1.

בחלוקות רגילות (N=128) ‏, $x_{0}\approx 3.5$ ולכן התנאי השלישי כמעט תמיד נכון.

קישורים חיצוניים

מדיה וקבצים בנושא שיטת זיגורט בוויקישיתוף

• שימוש באלגוריתם זיגורט ב-MATLAB
• מאמר שמתאר את שיטת הזיגורט מאת ג'רג' מרסגליה וואי ואן טסאנג