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

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

טרנספורמציה מדגימה מהתפלגות אחידה לדגימה מהתפלגות נורמלית
$u$	$F^{-1}(u)$
$2^{-52}$	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
$1-2^{-52}$	8.12589

תיאור השיטה

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

תהי $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$ ידועה לנו.

דוגמאות

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

נניח שאנו רוצים לדגום מספר מהתפלגות מעריכית עם פרמטר $\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)<p

.

מכיוון ש- $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) שייך גם לקבוצה הראשונה.