התפלגות טרייסי-וידום היא פונקציית התפלגות בתחום המטריצות אקראיות. ההתפלגות מתארת את הגודלו של הערך עצמי הגדול ביותר של סוגים מסוימים של מטריצות אקראיות כשהגודל שלהן שואף לאינסוף. ההתפלגות הוצגה לראשונה על ידי קרייג טרייסי (Craig Tracy) והארולד וידום (Harold Widom) בשנת 1993[1]. אחת התכונות יוצאות הדופן של התפלגות טרייסי-וידום היא האוניברסליות שלה. כלומר ההתפלגות מצליחה לתאר את גודלו של הערך העצמי הגדול ביותר עבור מגוון רחב של קבוצות מטריצות אקראיות (בתנאי שהמטריצות מקיימות תנאי סימטריה מסוימים). אוניברסליות זו הפכה את התפלגות טרייסי-וידום לאובייקט יסוד בתורת המטריצות האקראיות, ומצאה גם יישומים בתחומים שונים כגון פיזיקה סטטיסטית, תורת המספרים וקומבינטוריקה.
הגדרות
התפלגות טרייסי-וידום מסומנת ב כאשר מייצגת את סוג המטריצה עבורה תחושב התפלגותו של (נקראת גם "אינדקס דייסון").
קיימות שלוש צורות רווחות : מטריצה אורתוגונאלית (), מטריצה אוניטארית (), וסימפלקטית(אנ') ().
בפועל, יכולה להיות כל ערך טבעי.
הגדרה כגבול (חוק מספרים גדולים / משפט הגבול המרכזי)
ניתן להגדיר את , פונקציית התפלגות מצטברת של התפלגות טרייסי-וידום עבור נתונה, כגבול של התפלגויות, בדומה למשפט הגבול המרכזי.
עבור מטריצה אקראית בגודל , שמוגרלת מההתפלגות המתאימה (כתולת ב- שנבחרה), כאשר השונות של הערכים מחוץ לאלכסון היא .
נגדיר את להיות פונקציית ההתפלגות המצטברת של הערך העצמי המקסימלי. במילים אחרות . נגדיר את באמצעות הגבול:
כלומר
או במילים: ההפרש בין לבין מרכז ההתפלגות () שואף לקבוע בקצב של .
ההצגה הגבולית נותנת פירוש נוסף להתפלגות טרייס וידום: תיאור ה"תנודות" של על קטע צר בגודל פרופורציוני ל סביב .
הסטיה נובעת מהתפלגות חצי המעגל של ויגנר. הקובעת כי בגבול צפיפות הערכים העצמיים מתכנסת לחצי העיגול ברדיוס .
הכפלה בגורם משמשת לתיקון, כי סטיית התקן של ההתפלגות גדלה כמו (פותח לראשונה ב[2]).
נניח כי מייצגת פתרון של הטרנסצנדנטים של פנלבה (אנ') מסדר שני:עם חסם גבולי של [5]. כעת נגדיר כך שאז התפלגות (ההתפלגות המצטברת של טרייסי-וידום) תוגדר להיות[6]בעזרת אותה ניתן לתאר גם נוספות[7]:
תכונות גבוליות של ההתפלגות
כאמור, האוניברסליות של התפלגות טרייסי-וידום הביאה חוקרים לחקור את זנבותיה. חקר הזנבות מתבסס על הייצוג של ההתפלגות לפי משוואת פנילבה שהוזכרו לעיל.
פונקציית הצפיפות
תהי פונקציית הצפיפות אז[8]ניתן לראות כי ההתפלגות אכן בעלת זנב ימני. כלומר יותר סביר כי יהיה גדול מ . נזכור כי ההתפלגות הגבולית היא התפלגות חצי העיגול, ולכן ה"זנביות" נובעת מה"דחיה" ממרכז ההתפלגות, ולכן הסיכוי של להיות קטן יקטן.
עבור הזנב השמאלי קיים פיתוח סגור יותר[8]: עבור קבוע כלשהו התלוי ב .
דוגמה לקצב דעיכת הזנבות של
מהגדרה, הצפיפות של מוגדרת להיות אם כן, עבור חיובי גדול מספיק, נקבל (מהגדרות שהוזכרו לעיל) כי ולכן סך הכל . בעבור הזנב השמאלי, הוכח כבר[9] כי עבור שלילי מתקבל ואכן נקבל את המקרה הפרטי עבור כי הזנב השמאלי של מתנהג כמו .
בצורה כזו פונקציית ההתפלגות המצטברת ניתנת לניתוח לכל זנב בנפרד. למשל עבור :
רקע והיסטוריה
רקע
התפלגות של ערכים עצמיים
תהא מטריצה המוגדרת β-הרמיטית בגודל , נניח כי כלומר אוניטארית. כניסות המטריצה נדגמו מהתפלגות גיאוסיאנית קרי לכן פונקציית הצפיפות המשותפת של כל הערכים העצמיים (הבלתי תלויים, ללא סדר מסוים)[11]:כאשר הוא קבוע נרמול .
הרכיב הוא בעצם
הרכיב הוא אופרטור הגזירה .
מוטיבציה – התפלגות הערך העצמי המקסימלי ונקודות שיווי משקל
תהי מערכת המכילה בתוכה אובייקטים הנעים במרחב בצורה רנדומלית ובלתי תלויה לחלוטין. נרצה לחקור את התנועה במערכת (כוחות דוחפים\מושכים) – ובפרט לפתח את היכולת למצוא בה נקודות שיווי משקל. אם נדמיין את התנועה במרחב הרב-ממדי בתור וקטור הרי שנקודות שיווי המשקל \יציבות יתאפיינו על ידי (נק' סטציונאריות). לכן נתעניין בהסיאן של :כעת – הערכים העצמיים של המטריצה יקבעו את טבע התנועה במערכת (מינימום\מקסימום לוקאלי\גלובאלי ואוכף). למשל עבור יהיו שני ערכים עצמיים :אם כן, עבור נקודת מינימום נרצה שכל הערכים העצמיים יהיו שליליים .
נסמן ב את הערך העצמי המקסימלי ונקבל את השקילות .
במילים אחרות, הסיכוי ליציבות של המערכת (מינימום לוקאלי) תלויה בהתפלגותו של הערך העצמי המקסימלי של ההסיאן.
ניתן גם לפתח התפלגות לערכים העצמיים השני והשלישי בגודלם[12].
היסטוריה
אמצע המאה ה-20 – תוצאות ספקטרליות של מטריצות אקראיות
התפתחות ענף המטריצות האקראיות מתחיל באמצע המאה ה-20. הפיזיקאי יוג'ין ויגנר הציג את המטריצות האקראיות בפיזיקה בשנות ה-50, במקור על מנת לדמות את רמות האנרגיה של גרעיני אטומים כבדים[13]. בשנת 1951, ויגנר הציג את מה שנודע לאחר מכן כהתפלגות חצי המעגל של ויגנר, המתארת את ההתפלגות של ערכים עצמיים עבור מטריצות סימטריות אקראיות גדולות. עבודה זו היוותה את הבסיס לתורת המטריצות האקראיות, שמצאה יישומים בפיזיקה גרעינית, כאוס קוונטי ותחומים נוספים. ויגנר הראה כי עבור מטריצה אקראית פונקציית הצפיפות של הערכים העצמיים מתכנסת (בהתפלגות) לחצי העיגול סביב הטווח . ניתן להסיק מכך שפיזור של ערכים עצמיים על טווח זה יצור מרחק ממוצע בין ערכים עצמיים סמוכים פרופורציונלי ל . בנוסף, התפלגותו של הערך עצמי המקסימלי יהיה סביב .
בהמשך לתובנותיו של ויגנר, מתמטיקאים ופיזיקאים חקרו במהלך העשורים הבאים היבטים שונים של מטריצות אקראיות. התפתחות חשובה הגיעה בשנות ה-70 כאשר רוברט מיי (Robert May, Baron May of Oxford) יישם את מושגי המטריצות האקראיות בתחום האקולוגיה, תוך שימוש בהן כדי לנתח את היציבות של מערכות אקולוגיות מורכבות. מיי גילה ב"תאוריית האינטראקציה" שלו נקודה קריטית[14], שמעבר לה המערכת האקולוגית הופכת לבלתי יציבה. נקודת מפנה זו, כפי שהתברר מאוחר יותר, הייתה קשורה באופן הדוק להתפלגות טרייסי-וידום.
שנות ה-90 ועד ל-2005 – ארבע בעיות שונות – אותה ההתפלגות
בשנים אלו התגלה כי בעיות שונות שנחקרו בהרחבה חולקות את אותה פונקציית התפלגות – התפלגות טרייסי-וידום[15].
כאמור, 10 שנים מניסוח ההתפלגות, תחומי מחקר שונים לחלוטין מצאו בה שימוש יסודי בבעיות שלהם. אך לרוב (בדומה לגילוי הראשוני של רוברט מיי) השימוש היה בשיא ההתפלגות על מנת לתאר מעבר מיציבות של מערכת דינאמית לחוסר יציבות. גילויים אלה הניעו חוקרים לחקור דווקא את זנבות ההתפלגות.
בשנת 2006 פרופסור Satya Majumdar נחשף למחקרים שגרסו כי נקודות יציבות בתורת המיתרים מקבילות לתת-קבוצה של מטריצות אקראיות שהערכים העצמיים הגדולים ביותר שלהן הם שליליים – רחוק משמאל לערך הממוצע של בשיא עקומת טרייסי-וידום. הוא תהה עד כמה נדירות עשויות להיות נקודות יציבות אלו.
כדי לענות על השאלה, מג'ומדר ודייוויד דין[19], התחילו לחקור את הזנב הקיצוני השמאלי של התפלגות טרייסי-וידום, אזור בהתפלגות שטרם נחקר. בתוך שנה, הם פרסמו את מחקרם בכתב העת Physical Review Letters[20], שם טענו כי בצד השמאלי, קצב הדעיכה של ההתפלגות הוא כפונקציה של . בצד הימני, מג'ומדר ודין הופתעו לגלות שההתפלגות ירדה בקצב איטי יותר, כפונקציה של .
בשנת 2011, הצורה של הזנבות השמאלי והימני נתנה למג'ומדר וצוותו תובנה פתאומית: הם הבינו שהאוניברסליות של התפלגות טרייסי-וידום יכולה להיות קשורה לאוניברסליות של מעברי פאזה — אירועים כמו הקפאת מים לקרח, גרפיט שהופך ליהלום ומתכות רגילות שהופכות למוליכי-על[21].
”מכיוון שמעברי פאזה הם כל כך נפוצים – כל החומרים עוברים שינוי פאזה כאשר הם מוזנים או מורעבים מכמות מספקת של אנרגיה – ולוקחים רק קומץ של צורות מתמטיות, הם עבור הפיזיקאים הסטטיסטיים כמעט כמו דת” (מג'ומדר)
בשולי ההתפלגות המיניאטוריים של טרייסי-וידום, מג'ומדר, וצוותו זיהו צורות מתמטיות מוכרות: עקומות נפרדות המתארות שני קצבים שונים של שינוי בתכונות של מערכת, היורדות משני הצדדים של שיא מעבר פאזה. אלו היו סימני מעבר פאזה.
אמידה נומרית ושימוש בקוד
הערכה נומרית של ההתפלגות
על מנת לתת הערכה נומרית להתפלגות טרייסי-וידום, נדרשו טכניקות נומריות להשגת פתרונות נומריים למשוואות פנלבה מסוגים II ו-V. פתרונות אלה הוצגו לראשונה על ידי תבנית באמצעות MATLAB על ידי אנדלמן ופרסון[22].
טכניקות קירוב אלו קיבלו הצדקה אנליטית נוספת[23] ושימשו לצורך הערכה נומרית של התפלגויות באמצעות S-PLUS, באותה העבודה ההתפלגויות קובעו בטבלה בדיוק של עד 4 ספרות בקפיצות של 0.01 ביחד עם טבלת מובהקות (p-value).
בשנת 2010 נוסח אלגוריתם[24] מהיר לחישוב ערכי וערכי הצפיפות עבור . האלגוריתם מספק חישוב נומרי של הממוצע, השונות, צידוד והגבנוניותיתרה:
גבנוניות יתרה
צידוד
שונות
ממוצע
0.1652429384
0.29346452408
1.607781034581
−1.2065335745820
1
0.0934480876
0.224084203610
0.8131947928329
−1.771086807411
2
0.0491951565
0.16550949435
0.5177237207726
−2.306884893241
4
באמצעות אלו, פותח אלגוריתם[25] להתפלגות של הערך העצמי ה של האופרטור היכול לשמש לחישוב התפלגות טרייסי-וידום[26].
חבילות קוד קיימות
ב-R קיימת החבילה בשם 'RMTstat'[27], ב-MATLAB קיימת החבילה בשם 'RMLab'[28], ובפייתון קיימות מספר חבילות ביניהן scikit-rmt.
”תכונה בולטת של התיאוריה הקלאסית של ניתוח סטטיסטי רב-משתני היא שרוב הטכניקות הסטנדרטיות—רכיבים עיקריים, מתאמים קאנוניים, ניתוח שונות רב-משתני (MANOVA), ניתוח הבחנה וכדומה—מבוססות על ניתוח ערכים עצמיים של מטריצות השונות-המשותפת.”
הנחות המודל והבעיה
בידינו מטריצת נתונים המתארת דגימות מ משתנים (עמודה ב מתארת תצפית אחת מ משתנים). אנו מניחים כי ולשם הפשטות .
הבעיה שלפנינו היא להסיק את תכונות מתוך מטריצת השונות הנצפית , ממנה ניתנים לחילוץ – הערכים העצמיים הנצפים של .
נרצה לפתח סטטיסטי תחת ההנחה כי . תחת הנחה זו מצופה כי . על מנת לאמוד כמה "קיצוניים" ערכי כך שיצדיקו דחיה של השערת האפס נחקור את ההתפלגות שלהם תחת הנחה זו. התפלגות זו נחקרה ונקראת התפלגות וישארט (Wishart distribution) (התפלגות זו היא הרחבה של התפלגות חצי המעגל של ויגנר). כלומר נתעניין בכאשר הקשר בין התפלגות טרייסי וידום (הערך העצמי הגדול ביותר של ) להתפלגות וישארט היא תחת וכן מתקבל החסם[30]כלומר תחת ההשערה התפלגות הערך העצמי הגדול ביותר הנצפה קרובה בדיוק מסדר שני להתפלגות טרייסי-וידום.
ולכן התפלגות זו היא התפלגות הסטטיסטי המבוקש ובאמצעותה ניתן לבצע את בדיקת ההשערות.
כעת, נניח כי הערך העצמי הגבוהה ביותר הנצפה הוא . האם הוא קיצוני דיו עבורינו?
ראשית, נדרוש דיוק של 0.01 להתפלגות (התפלגות טרייסי וידום עם ), דיוק זה מתקבל בהסתברות לכל היותר . בהנחה ואנו מסופקים מהסתברות זו (אחרת, ניאלץ לשנות את הקבועים שלנו) – ניתן נומרית לפתח את התפלגות לערכים נבחרים:
ערכי עבור ההסתברות כאשר
.09
אם כן, מובהקות התוצאה היא .
ניתוח מדגמים רועשים (BBP Phase Transition)
דוגמה נוספת לשימוש בהתפלגות טרייסי וידום הוא שילוב בדיקת ההשערות בניתוח מדגמים רועשים. לעיתים רוצים לזהות האם יש "אות" בתוך הרעש. לדוגמה, במקרה בו יש לנו מטריצת מתאם או שונות משותפת שמתארת נתונים, השאלה היא אם קיימת סטייה משמעותית שיכולה להעיד על מידע משמעותי (אות) או שהמדגם כולו מבוסס על רעש אקראי בלבד. במילים אחרות, מטריצת השונות היא מהצורה והמטרה היא למצוא כי מדובר בערך העצמי ה .
ה-BBP Transition (נקרא על שמם של החוקרים Baik, Ben Arous, ו-Péché שגילו אותו לראשונה בשנת 2005[31] ) מתאר את הנקודה שבה האות נהיה חזק דיו כדי לגרום לערך העצמי הגדול ביותר לחרוג ממשטר של רעש אקראי. נקודה זו נקראת "spike",זהו מעבר חד (כמו "מעבר פאזה" בפיזיקה, שבו המערכת עוברת ממשטר אחד לאחר).
נציין, כי במצב כזה המטריצה אינה מקיימת . מחקרים שונים פתרו את הבעיה למקרים פרטיים שונים. למשל, במקרה "הפשוט" בו מתקיים עבור . במצב כזה ניתן למשל לפתח את – התפלגות של הערך העצמי ה- בגודלו המתאים ל כאשר .
נשים לב כי הערך העצמי ה במודל ה"ספייק" קטן סטוכסטית מהערך העצמי הגדול ביותר במודל עם משתנים[32]. ולכן נותר לבצע מבחן השערות (לא אסימפטוטי) באמצעות – התפלגות הערך העצמי הגדול ביותר לאחר ש"ניקינו" את הערכים העצמיים הגודלים. אם כן, הערך העצמי ה במטריצה החדשה בעל התפלגות טרייסי וידום, כלומר שקולה נומרית ל על ידיומכאן ניתן לבצע את בדיקת ההשערות כפי שהוצגה לעיל.
לקריאה נוספת
מגבלות גבוליות: מסתבר כי הדיוק מסדר שני שהתקבל יחסית מדויק גם עבור יחסית קטנים ואף שלא מקיימים את ההנחה . ג'ונסטון במאמרו[33] בחן את דיוקו של הקירוב לצורכי חישוב מובהקות בעזרת טבלאות נומריות של התפלגות [34].
^נקרא לראשונה כ "הפתרון של הייסטינג-מקליאוד".
על ידי Hastings, S.P, McLeod, J.B ב
A boundary value problem associated with the second Painlevé" "transcendent and the Korteweg-de Vries equation.
Arch. Ration. Mech. Anal. 73, 31–51 (1980)
^ 12Majumdar, Satya N; Schehr, Grégory (2014-01-31), Top eigenvalue of a random matrix: large deviations and third order phase transition, Journal of Statistical Mechanics: Theory and Experiment, 31 January 2014 doi: 10.1088/1742-5468/2014/01/P01012
^ראו רשימות הרצאה של Satya N. Majumdar בנושא Random Matrices, the Ulam Problem, Directed Polymers & Growth Models, and Sequence Matching ב־https://arxiv.org/abs/cond-mat/0701193
^Andrei Bejan, [chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http://users.stat.umn.edu/~jiang040/downloadpapers/largesteigen/largesteigen.pdf Largest eigenvalues and sample covariance matrices], Tracy–Widom and Painleve II: computational aspects and realization in S-Plus with applications. Mathematics Subject Classification 1991, 2005
^William W. Chen, [chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/https://www.irs.gov/pub/irs-soi/chen.pdf SOME NEW TABLES OF THE LARGEST ROOT OF A MATRIX IN MULTIVARIATE ANALYSIS: A COMPUTER APPROACH FROM 2 TO 6], American Statistical Association, 2002