השוואת תהליכים גאוסיים

קובץ:Asche transparent background.png

ערך זה דורש ידע מוקדם. אם אתם מתקשים להבין את הערך מומלץ לעיין ב:

תהליך סטוכסטי, תהליך גאוסי, תהליך וינר, תנועה בראונית

השוואת תהליכים גאוסיים (Gaussian processes comparison) הוא אוסף של כלים אנליטיים (בעיקר אי-שוויונות) הקושרים בין התנהגותם של שני תהליכים גאוסיים באמצעות השוואת מבני השונות המשותפת שלהם. כלים אלה מאפשרים להעריך גדלים קשים לחישוב – למשל תוחלת הסופרימום או הסתברויות זנב של תהליך אחד – על-ידי השוואתם לאלו של תהליך אחר, פשוט יותר לניתוח.

אי־שוויונות מרכזיים

הלמה של סלפיאן

יהיו <math>(X_t)_{t\in T}</math>, ו-<math>(Y_t)_{t\in T}</math> תהליכים גאוסיים בעלי תוחלת 0. נניח בנוסף:

• שונויות זהות לכל <math>t \in T</math> מתקיים:<math> \mathbb{E}X_t^2=\mathbb{E}Y_t^2</math>
• דומיננטיות של אינקרמנטים לכל <math>t ,s\in T</math> מתקיים:<math> \mathbb{E}(X_t-X_s)^2\le \mathbb{E}(Y_t-Y_s)^2 </math>

אזי לכל <math>\tau\in\mathbb{R}</math>:

<math>\mathbb{P}\bigg(\sup_{t\in T}X_t\ge \tau\bigg)\le\mathbb{P}\bigg(\sup_{t\in T}Y_t\ge \tau\bigg)</math>

ולכן: <math>\mathbb{E}\sup_{t\in T}X_t\le\mathbb{E}\sup_{t\in T}Y_t</math>.

אי-שוויון סודקוב–פרניקה

אי השוויון של סודקוב–פרניקה "חזק" יותר מאי-שוויון סלפיאן נבחינה זו שהוא מאפשר לנו לקבל את אותה תוצאה כמו בלמה של סלפיאן אך ללא הדרישה על שוויון השונויות:

יהיו <math>(X_t)_{t\in T}</math> ו-<math>(Y_t)_{t\in T}</math> תהליכים גאוסיים בעלי תוחלת 0.

נניח בנוסף כי לכל <math>t ,s\in T</math>, מתקיים:<math>\mathbb{E}(X_t-X_s)^2\le \mathbb{E}(Y_t-Y_s)^2 </math>

אזי: <math>\mathbb{E}\sup_{t\in T}X_t\le\mathbb{E}\sup_{t\in T}Y_t</math>

אי-שוויון גורדון

אי-שוויון גורדון הוא הרחבה של הלמה של סלפיאן, ומתייחס לפונקציונלים מורכבים מסוג מינימום–מקסימום:

יהיו <math>T</math> ו-<math>U</math> קבוצות אינדקס, ויהיו <math>(X_{u,t})_{u\in U,t\in T}</math>, <math>(Y_{u,t})_{u\in U,t\in T}</math> תהליכים גאוסיים בעלי תוחלת אפס על מרחב המכפלה <math>U \times T</math>. נניח בנוסף כי:

• לכל <math>u\in U; t,s\in T</math>, מתקיים:<math> \mathbb{E}X_{ut}^2=\mathbb{E}Y_{ut}^2\quad \mathbb{E}(X_{ut}-X_{us})^2\le \mathbb{E}(Y_{ut}-Y_{us})^2

</math>

• לכל <math>u\neq v; t,s\in T</math>, מתקיים:<math>\mathbb{E}(X_{ut}-X_{vs})^2\ge \mathbb{E}(Y_{ut}-Y_{vs})^2</math>

אזי לכל <math>\tau \ge 0</math> מתקיים: <math>\mathbb{P}\bigg(\inf_{u\in U}\sup_{t\in T}X_{ut}\ge \tau\bigg)\le\mathbb{P}\bigg(\inf_{u\in U}\sup_{t\in T}Y_{ut}\ge \tau\bigg)</math>,

ולכן: <math>\mathbb{E}\inf_{u\in U}\sup_{t\in T}X_{ut}\le\mathbb{E}\inf_{u\in U}\sup_{t\in T}Y_{ut}</math>.

הערות:

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

2. ניתן לקבל תוצאה דומה עבור הסדר ההפוך של האינפימום-סופרמום אם ניישם את אי שוויון גורדון על התהליכים <math>(-X_{u,t},-Y_{u,t})</math>.

3. כמו במקרה של אי-שוויון סודקוב–פרניקה, ניתן לקבל את אותה תוצאה גם אם לא נדרוש את שוויון השונות.

יישומים

חסמים של מטריצות אקראיות אנליזה ספקטרלית

נוכל לקבל חסם על הנורמה של מטריצות אקראיות או של ערכיה הסינגולריים. ניתן לתאר ערכים שונים אלו כסופרמום של תהליך גאוסי ואז להשתמש באי שוויונות סלפיאן או סודקוב-פרינקה כדי לקבל על ערכים אלו חסם.

לדוגמה, תהי <math>A\in\mathbb{R}^{m\times n}</math> בעל כניסות בלתי-תלויות <math>\mathcal{N}(0,1)</math> . נגדיר את הערך הסינגולרי הגדול ביותר: <math> s_{\max}(A)=sup_{|u|_2=1}||Au||_2=sup_{|u|_2=1,|u|_2=1}\langle Au,v\rangle:=sup_{|u|_2=1,|u|_2=1}X_{u,v}</math>. כאשר <math>X_{u,v}</math> תהליך גאוסי על הספֵירה היחידה <math>\mathcal S^{n-1}</math>. ניתן להשוות אותו לתהליך גאוסי פשוט יותר ולקבל עם סלפיאן/סודקוב–פרניקה: <math>\mathbb{E}||A|| =S_{\max}(A)\le \sqrt m+\sqrt n</math>.

באופן דומה ניתן לקבל חסמים לערכים נוספים, כמו הערך הסינגולרי הקטן ביותר (<math>S_{\min}(A)\ge \sqrt m-\sqrt n</math>) על ידי שימוש באי-שוויון גורדון.

מספר כיסוי במרחב האוקלידי

ניתן לקבל הערכה על מספר הכיסוי של איזושהי קבוצה גאומטרית במרחב האוקלידי.

נניח <math>T\subset\mathbb{R}^n</math>. נגדיר את התהליך הגאוסי הקנוני <math>X_t=\langle g,t\rangle</math>, עם <math>g\sim\mathcal{N}(0,I_n)</math>. עבור תהליך זה מרחק האינקרמנטים הוא בדיוק המרחק האוקלידי: <math>||t-s||_2</math>. נוכל להראות, לפי אי-שוויון סודקוב–פרניקה, שלכל <math>\varepsilon>0</math> מתקיים:

<math>\mathbb{E}\sup_{t\in T} \langle g,t\rangle \ge c\varepsilon\sqrt{\log N(T,\varepsilon)} </math>. כאשר <math>N(T,\varepsilon)</math> הוא מספר הכדורים האוקלידיים ברדיוס <math>\varepsilon</math> הדרוש לכיסוי <math>T\subset\mathbb{R}^n</math> (מספר הכיסוי).

רקע היסטורי

התוצאה המרכזית הראשונה של תחום "השוואות תהליכים גאוסיים" היא הלמה של סלפיאן שהוכחה לראשונה על ידי דיוויד סלפיאן ב-1962 וזכתה להוכחות נוספות בדרכים שונות. מאז שימשה כלי משמעותי בדיספלינות שונות- בהנדסה, סטטיסטיקה ותורת ההסתברות. כעשר שנים אחר כך, באמצע שנות ה-70, הוכח אי השוויון של סודקוב–פרניקה. ב-1985, הוכיח המתמטיקאי הישראלי יהורם גורדון את ההרחבה של הלמה של סלפיאן מתוך מוטיבציה להעריך טוב יותר בעיות גאומטריות.

ראו גם

• משפט דבורצקי

לקריאה נוספת

• Vershynin, Roman (2018). High-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge University Press.
• Huffer, F. "Slepian's inequality via the central limit theorem", Canadian Journal of Statistics (1986), pp 367–370.
• Ledoux, M., Talagrand, M. "Probability in Banach Spaces", Springer Verlag, Berlin 1991, pp 75.
• Sudakov, V.N. (1971). Gaussian random processes and measures of solid angles in Hilbert space.Dokl. Akad. Nauk. SSR 197, 4345.; English translation in Soviet Math. Dokl. (1971) 12, 412–415.
• Sudakov, V.N. (1976). Geometric Problems in the Theory of Infinite-Dimensional Probability * Distributions. Trud. Mat. Inst. Steklov 141. English translation in Proc.Steklov.Inst. Math 2, Amer. Math.Soc.
• Sudakov, V.N. (1971). Gaussian random processes and measures of solid angles in Hilbert space.Dokl. Akad. Nauk. SSR 197, 4345.; English translation in Soviet Math. Dokl. (1971) 12, 412–415.