דגימה מהעתקה הופכית

דגימה מהעתקה הופכית או דגימה מטרנספורמציה הופכית (באנגלית: Inverse transform sampling, או בקיצור: ITS) היא שיטה לדגימה ממוחשבת של מספרים אקראיים מהתפלגות ידועה כלשהי, בהינתן שפונקציית ההתפלגות המצטברת שלה ידועה, ובהינתן שניתן לדגום מהתפלגות אחידה רציפה.
+ טרנספורמציה מדגימה מהתפלגות אחידה לדגימה מהתפלגות נורמלית      8.12589- 0.000001  4.75342- 0.005  2.5758- 0.025  1.95996- 0.5  0 0.975  1.95996 0.995  2.5758 0.999999  4.75342   8.12589
ממוזער|280px|דגימה מהתפלגות הופכית עבור התפלגות נורמלית
 תיאור השיטה 
 פונקציה הופכית מוכללת 
תהי  פונקציית ההתפלגות המצטברת (פה"מ) של ההתפלגות  ממנה אנו רוצים לדגום. נגדיר את "הפונקציה ההופכית המוכללת" של , אותה נסמן ב , באופן הבא:

או במילים: הערך של  עבור p הוא ה-x הקטן ביותר (אינפימום) עבורו  גדול-שווה ל-p.

אם  היא התפלגות רציפה, אז ההופכית המוכללת  היא בדיוק הפונקציה ההופכית של , כלומר:

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

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

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

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

 דוגמאות 
 התפלגות מעריכית 
ממוזער|380px|דגימה מהתפלגות מעריכית עם פרמטר , באמצעות שיטת ITS. הנקודות  מייצגות 200 דגימות אקראיות, כשבציר ה-X מופיעים הערכים של הדגימה המקורית מהתפלגות אחידה בקטע (0,1), ובציר ה-Y הערכים ה"מתאימים" בהתפלגות המעריכית.  מצויר קו המייצג את הפונקציה ההופכית התאורטית.
נניח שאנו רוצים לדגום מספר מהתפלגות מעריכית עם פרמטר . הפה"מ הוא: 

נמצא את הפונקציה ההופכית:

כלומר, נדגום מספר u מהתפלגות אחידה בקטע (0,1), ואז  יהיה מספר אקראי מהתפלגות מעריכית עם פרמטר .

 התפלגות אחידה בדידה 
נניח שאנו רוצים לדגום מספר מהתפלגות אחידה בדידה בין a ל-b. הפה"מ הוא:  לכל x בקטע [a,b].

נמצא את הפונקציה ההופכית המוכללת, עבור x בקטע [a,b]:

ה- הקטן ביותר (האינפימום) המקיים אי-שוויון זה, הוא המספר השלם הקטן ביותר שאינו-קטן מ-, כלומר:

כלומר, נדגום מספר u מהתפלגות אחידה בקטע (0,1), ואז  יהיה מספר אקראי מהתפלגות אחידה בדידה בין a ל-b.

ניתן לראות שהתוצאה שקיבלנו היא הגיונית, שכן עבור u קרוב מאוד ל-1 נקבל  ועבור u קרוב מאוד ל-0 נקבל .

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

 הוכחה עבור התפלגות רציפה 
אם  היא התפלגות רציפה, אז ההופכית המוכללת  היא בדיוק הפונקציה ההופכית של , כלומר:

ההוכחה במקרה זה היא יחסית פשוטה; פונקציית ההתפלגות של  (נסמן אותה ב-) היא:

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

וכיוון ש- הוא משתנה אחיד סטנדרטי:

משלושת השוויונות נובע:

כלומר אכן הפה"מ של התפלגות של  זהה ל-, ולכן התפלגות  זהה להתפלגות .

 הוכחה עבור המקרה הכללי 
שלב 1
לכל  ולכל  הפונקציה ההופכית המוכללת מקיימת את 2 אי-השוויונות הבאים:

מכיוון ש- מחזירה בהכרח ערך x המקיים , מתקיים בהכרח:
1.  
שכן אחרת .

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

שלב 2

משני האי-שוויונים לעיל נובע שקבוצת ה-x-ים וה-p-ים המקיימים  זהה לקבוצת ה-x-ים וה-p-ים המקיימים , כלומר:

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

שלב 3
המטרה שלנו היא להוכיח שפונקציית ההתפלגות של  זהה לפונקציית ההתפלגות . פונקציית ההתפלגות של  (נסמן אותה ב-) היא:

לפי מה שהוכחנו בשלב הקודם, מתקיים בהכרח (נציב את U במקום p):

וכיוון ש- הוא משתנה אחיד סטנדרטי:

משלושת השוויונות נובע:

כלומר אכן הפה"מ של התפלגות של  זהה ל-, ולכן התפלגות  זהה להתפלגות .

 קישורים חיצוניים 
 The Inverse Transform Method, באתר אוניברסיטת קיימברידג'

קטגוריה:יצירת מספרים אקראיים