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

**דגימה מהעתקה הופכית** או **דגימה מטרנספורמציה הופכית** (באנגלית: **Inverse transform sampling**, או בקיצור: **ITS**) היא שיטה לדגימה ממוחשבת של מספרים אקראיים מהתפלגות ידועה כלשהי, בהינתן שפונקציית ההתפלגות המצטברת שלה ידועה, ובהינתן שניתן לדגום מהתפלגות אחידה רציפה.

[ממוזער|280px|דגימה מהתפלגות הופכית עבור [התפלגות נורמלית]]
## תיאור השיטה
### פונקציה הופכית מוכללת
תהי F פונקציית ההתפלגות המצטברת (פה"מ) של ההתפלגות D ממנה אנו רוצים לדגום. נגדיר את "הפונקציה ההופכית המוכללת" של F, אותה נסמן ב F^-, באופן הבא:

F^-(p) = inf\{x : F(x) \geq p\}

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

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

F^-(p) = F^{-1}(p) = \{x : F(x) = p\}

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

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

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

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

## דוגמאות
### התפלגות מעריכית
[ממוזער|380px|דגימה מ[התפלגות מעריכית עם פרמטר \lambda = 2, באמצעות שיטת ITS. הנקודות  מייצגות 200 דגימות אקראיות, כשבציר ה-X מופיעים הערכים של הדגימה המקורית מהתפלגות אחידה בקטע (0,1), ובציר ה-Y הערכים ה"מתאימים" בהתפלגות המעריכית.  מצויר קו המייצג את הפונקציה ההופכית התאורטית.]]
נניח שאנו רוצים לדגום מספר מהתפלגות מעריכית עם פרמטר \lambda. הפה"מ הוא: F(x) = \ 1 - e^{-\lambda x}

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

F(x) = \ 1 - e^{-\lambda x} = u

e^{-\lambda x} = 1 - u

-\lambda x = ln(1 - u)

F^{-1}(u) = x = -\frac{ln(1 - u)}{\lambda}

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

### התפלגות אחידה בדידה
נניח שאנו רוצים לדגום מספר מהתפלגות אחידה בדידה בין a ל-b. הפה"מ הוא: F(x) = \frac{\lfloor x \rfloor -a + 1}{b-a+1}  לכל x בקטע [a,b].

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

F(x) = \frac{\lfloor x \rfloor -a + 1}{b-a+1} \geq u

\lfloor x \rfloor -a + 1 \geq u(b-a+1)

\lfloor x \rfloor \geq u(b-a+1) + a - 1

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

F^-(u) = x = \lceil u(b-a+1) + a - 1 \rceil

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

ניתן לראות שהתוצאה שקיבלנו היא הגיונית, שכן עבור u קרוב מאוד ל-1 נקבל F^-(1^-) = b ועבור u קרוב מאוד ל-0 נקבל F^-(0^+) = a.

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

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

F^-(p) = F^{-1}(p) = \{x : F(x) = p\}

ההוכחה במקרה זה היא יחסית פשוטה; פונקציית ההתפלגות של F^{-1}(U) (נסמן אותה ב-G) היא:
:G(x) = Pr\left(F^{-1}(U) \leq x\right)
נפעיל את F (שהיא פונקציה מונוטונית-עולה) על שני צידי האי-שוויון בתוך נוסחת ההסתברות, ונקבל:
:Pr\left(F^{-1}(U) \leq x\right) = Pr\left(F\left(F^{-1}(U)\right) \leq F(x)\right) = Pr\left(U \leq F(x)\right)
וכיוון ש-U הוא משתנה אחיד סטנדרטי:
:Pr\left(U \leq F(x)\right) = F(x)
משלושת השוויונות נובע:
:G(x) = F(x)
כלומר אכן הפה"מ של התפלגות של F^{-1}(U) זהה ל-F, ולכן התפלגות F^{-1}(U) זהה להתפלגות D.

### הוכחה עבור המקרה הכללי
#### שלב 1
לכל p \in (0,1) ולכל x \in F^-(0,1) הפונקציה ההופכית המוכללת מקיימת את 2 אי-השוויונות הבאים:

מכיוון ש-F^- מחזירה בהכרח ערך x המקיים F(x) \geq p, מתקיים בהכרח:
:**1.**  F\left(F^-(p)\right) \geq p
:שכן אחרת F(x) .

מכיוון ש-F^- מחזירה את האינפימום על פני כל ערכי x המקיימים F(x) \geq p, מתקיים בהכרח:
:**2.**  F^-\left(F(x)\right) \leq x
:שכן אחרת: F^-\left(F(x)\right) > x כלומר F^-\left(F(x)\right) היה גדול-ממש מ-x, וזה לא ייתכן כי הוא אינפימום על פני קבוצה המכילה את x.

#### שלב 2

משני האי-שוויונים לעיל נובע שקבוצת ה-x-ים וה-p-ים המקיימים F^-(p) \leq x זהה לקבוצת ה-x-ים וה-p-ים המקיימים F(x) \geq p, כלומר:
:\left\{ (p,x) | F(x) \geq p \right\} = \left\{ (p,x) | F^-(p) \leq x \right\}

**הוכחה:**
* אם יש (x,p) השייך לקבוצה הראשונה, כלומר מקיים F^-(p) \leq x, אז נפעיל את הפונקציה F (שהיא פונקציה מונוטונית-עולה) על שני הצדדים ונקבל: F\left(F^-(p)\right) \leq F(x), ולפי מה שהוכחנו למעלה: p \leq F\left(F^-(p)\right) \leq F(x), כלומר: p \leq F(x), כלומר (x,p) שייך גם לקבוצה השנייה.
* אם יש (x,p) השייך לקבוצה השנייה, כלומר מקיים F(x) \geq p, אז נפעיל את הפונקציה F^- (שהיא פונקציה מונוטונית-עולה) על שני הצדדים ונקבל: F^-\left(F(x)\right) \geq F^-(p), ולפי מה שהוכחנו למעלה: x \geq F^-\left(F(x)\right) \geq F^-(p), כלומר: x \geq F^-(p), כלומר (x,p) שייך גם לקבוצה הראשונה.

#### שלב 3
המטרה שלנו היא להוכיח שפונקציית ההתפלגות של F^-(U) זהה לפונקציית ההתפלגות F. פונקציית ההתפלגות של F^-(U) (נסמן אותה ב-G) היא:
:G(x) = Pr\left(F^-(U) \leq x\right)
לפי מה שהוכחנו בשלב הקודם, מתקיים בהכרח (נציב את U במקום p):
:Pr\left(F^-(U) \leq x\right) = Pr\left(U \leq F(x)\right)
וכיוון ש-U הוא משתנה אחיד סטנדרטי:
:Pr\left(U \leq F(x)\right) = F(x)
משלושת השוויונות נובע:
:G(x) = F(x)
כלומר אכן הפה"מ של התפלגות של F^-(U) זהה ל-F, ולכן התפלגות F^-(U) זהה להתפלגות D.

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

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