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

דגימה מהעתקה הופכית או דגימה מטרנספורמציה הופכית (באנגלית: Inverse transform sampling, או בקיצור: ITS) היא שיטה לדגימה ממוחשבת של מספרים אקראיים מהתפלגות ידועה כלשהי, בהינתן שאנו יודעים את פונקציית ההתפלגות המצטברת שלה, ובהינתן שאנו יודעים לדגום מהתפלגות אחידה רציפה.
{| class="wikitable floatleft"
|+ טרנספורמציה מדגימה מהתפלגות אחידה לדגימה מהתפלגות נורמלית
|-
! <math>u</math> !! <math>F^{-1}(u)</math>
|-
| <math>2^{-52}</math> || 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
|-
| <math>1-2^{-52}</math> || 8.12589
|}
דגימה מהתפלגות הופכית עבור [[התפלגות נורמלית]]
== תיאור השיטה ==
=== פונקציה הופכית מוכללת ===
תהי <math>F</math> פונקציית ההתפלגות המצטברת (פה"מ) של ההתפלגות <math>D</math> ממנה אנו רוצים לדגום. נגדיר את "הפונקציה ההופכית המוכללת" של <math>F</math>, אותה נסמן ב <math>F^-</math>, באופן הבא:

<math>F^-(p) = inf\{x : F(x) \geq p\}</math>

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

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

<math>F^-(p) = F^{-1}(p) = \{x : F(x) = p\}</math>

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

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

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

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

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

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

<math>F(x) = \ 1 - e^{-\lambda x} = u</math>

<math>e^{-\lambda x} = 1 - u</math>

<math>-\lambda x = ln(1 - u)</math>

<math>F^{-1}(u) = x = -\frac{ln(1 - u)}{\lambda}</math>

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

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

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

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

<math>\lfloor x \rfloor -a + 1 \geq u(b-a+1)</math>

<math>\lfloor x \rfloor \geq u(b-a+1) + a - 1</math>

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

<math>F^-(u) = x = \lceil u(b-a+1) + a - 1 \rceil</math>

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

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

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

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

<math>F^-(p) = F^{-1}(p) = \{x : F(x) = p\}</math>

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

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

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

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

====שלב 2====

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

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

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

== קישורים חיצוניים ==
* [http://www3.eng.cam.ac.uk/~ss248/G12-M01/Week1/ITM.pdf The Inverse Transform Method], באתר אוניברסיטת קיימברידג'

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