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

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

טרנספורמציה מדגימה מהתפלגות אחידה לדגימה מהתפלגות נורמלית

${\displaystyle u}$	${\displaystyle F^{-1}(u)}$
${\displaystyle 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
${\displaystyle 1-2^{-52}}$	8.12589

דגימה מהתפלגות הופכית עבור התפלגות נורמלית

תיאור השיטה

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

תהי ${\displaystyle F}$ פונקציית ההתפלגות המצטברת (פה"מ) של ההתפלגות ${\displaystyle D}$ ממנה אנו רוצים לדגום. נגדיר את "הפונקציה ההופכית המוכללת" של ${\displaystyle F}$, אותה נסמן ב ${\displaystyle F^{-}}$, באופן הבא:

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

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

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

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

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

שיטת הדגימה

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

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

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

דוגמאות

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

דגימה מהתפלגות מעריכית עם פרמטר ${\displaystyle \lambda =2}$, באמצעות שיטת ITS. הנקודות בצבע כחול מייצגות 200 דגימות אקראיות, כשבציר ה-X מופיעים הערכים של הדגימה המקורית מהתפלגות אחידה בקטע (0,1), ובציר ה-Y הערכים ה"מתאימים" בהתפלגות המעריכית. בצבע אדום מצויר קו המייצג את הפונקציה ההופכית התאורטית.

נניח שאנו רוצים לדגום מספר מהתפלגות מעריכית עם פרמטר ${\displaystyle \lambda }$. הפה"מ הוא: ${\displaystyle F(x)=\ 1-e^{-\lambda x}}$

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

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

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

${\displaystyle -\lambda x=ln(1-u)}$

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

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

התפלגות אחידה בדידה

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

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

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

${\displaystyle \lfloor x\rfloor -a+1\geq u(b-a+1)}$

${\displaystyle \lfloor x\rfloor \geq u(b-a+1)+a-1}$

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

${\displaystyle F^{-}(u)=x=\lceil u(b-a+1)+a-1\rceil }$

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

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

הוכחת נכונות השיטה

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

הוכחה עבור התפלגות רציפה

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

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

ההוכחה במקרה זה היא יחסית פשוטה; פונקציית ההתפלגות של ${\displaystyle F^{-1}(U)}$ (נסמן אותה ב-${\displaystyle G}$) היא:

${\displaystyle G(x)=Pr\left(F^{-1}(U)\leq x\right)}$

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

${\displaystyle 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)}$

וכיוון ש-${\displaystyle U}$ הוא משתנה אחיד סטנדרטי:

${\displaystyle Pr\left(U\leq F(x)\right)=F(x)}$

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

${\displaystyle G(x)=F(x)}$

כלומר אכן הפה"מ של התפלגות של ${\displaystyle F^{-1}(U)}$ זהה ל-${\displaystyle F}$, ולכן התפלגות ${\displaystyle F^{-1}(U)}$ זהה להתפלגות ${\displaystyle D}$.

הוכחה עבור המקרה הכללי

שלב 1

לכל ${\displaystyle p\in (0,1)}$ ולכל ${\displaystyle x\in F^{-}(0,1)}$ הפונקציה ההופכית המוכללת מקיימת את 2 אי-השוויונות הבאים:

מכיוון ש-${\displaystyle F^{-}}$ מחזירה בהכרח ערך x המקיים ${\displaystyle F(x)\geq p}$, מתקיים בהכרח:

1.     ${\displaystyle F\left(F^{-}(p)\right)\geq p}$

שכן אחרת ${\displaystyle F(x)<p}$.

מכיוון ש-${\displaystyle F^{-}}$ מחזירה את האינפימום על פני כל ערכי x המקיימים ${\displaystyle F(x)\geq p}$, מתקיים בהכרח:

2.     ${\displaystyle F^{-}\left(F(x)\right)\leq x}$

שכן אחרת: ${\displaystyle F^{-}\left(F(x)\right)>x}$ כלומר ${\displaystyle F^{-}\left(F(x)\right)}$ היה גדול-ממש מ-x, וזה לא ייתכן כי הוא אינפימום על פני קבוצה המכילה את x.

שלב 2

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

${\displaystyle \left\{(p,x)|F(x)\geq p\right\}=\left\{(p,x)|F^{-}(p)\leq x\right\}}$

הוכחה:

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

שלב 3

המטרה שלנו היא להוכיח שפונקציית ההתפלגות של ${\displaystyle F^{-}(U)}$ זהה לפונקציית ההתפלגות ${\displaystyle F}$. פונקציית ההתפלגות של ${\displaystyle F^{-}(U)}$ (נסמן אותה ב-${\displaystyle G}$) היא:

${\displaystyle G(x)=Pr\left(F^{-}(U)\leq x\right)}$

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

${\displaystyle Pr\left(F^{-}(U)\leq x\right)=Pr\left(U\leq F(x)\right)}$

וכיוון ש-${\displaystyle U}$ הוא משתנה אחיד סטנדרטי:

${\displaystyle Pr\left(U\leq F(x)\right)=F(x)}$

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

${\displaystyle G(x)=F(x)}$

כלומר אכן הפה"מ של התפלגות של ${\displaystyle F^{-}(U)}$ זהה ל-${\displaystyle F}$, ולכן התפלגות ${\displaystyle F^{-}(U)}$ זהה להתפלגות ${\displaystyle D}$.

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

• The Inverse Transform Method, באתר אוניברסיטת קיימברידג'