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

שיטת דגימה מהתפלגות שהפה"מ שלה ידוע

דגימה מהעתקה הופכית או דגימה מטרנספורמציה הופכית (באנגלית: 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
דגימה מהתפלגות הופכית עבור התפלגות נורמלית

תיאור השיטה

עריכה

פונקציה הופכית מוכללת

עריכה

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

 

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


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

 

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

שיטת הדגימה

עריכה

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

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

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

דוגמאות

עריכה

התפלגות מעריכית

עריכה
 
דגימה מהתפלגות מעריכית עם פרמטר  , באמצעות שיטת 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):

 

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

 

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

 

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

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

עריכה