tomron87/hebrew-wikipedia-sentences-corpus huggingface dataset:
2. קשר לשונות בין עותקים בלתי תלויים:
נזכיר כי ו-, כאשר הוא עותק בלתי תלוי של , ובלתי תלוי גם בכל שאר ה--ים ().
כאשר אנו מתנים ב-, המשתנים קבועים.
המשתנים המקריים היחידים שנותרו הם (ב-) ו- (ב-).
מכיוון ש- ו- הם שווי התפלגות ובלתי תלויים (גם בתנאי ), נובע כי המשתנים המקריים ו- הם שווי התפלגות ובלתי תלויים בתנאי .
עבור שני משתנים מקריים שהם שווי התפלגות ובלתי תלויים, מתקיימת הזהות היסודית:
נפעיל זהות זו בתנאי על המשתנים ו-:
נשלב את התוצאות מסעיפים 1 ו-2:
כעת נציב תוצאה זו בחזרה במשפט העזר ():
הכללה למערך דו-ממדי של משתנים מקריים
אי-שוויון אפרון–שטיין ניתן להכללה גם למקרים בהם הקלט לפונקציה הוא מטריצה אקראית, כלומר מטריצה שכל אחד מרכיביה הוא משתנה מקרי.
הרחבה זו מאפשרת לנתח את השונות של פונקציות מורכבות הפועלות על נתונים דו-ממדיים או רב-ממדיים, והיא שימושית במיוחד בתחומים כגון למידת מכונה, סטטיסטיקה רב-ממדית, עיבוד אותות, עיבוד תמונה ועיבוד שפה טבעית.
יהי מטריצה אקראית, כלומר מטריצה בגודל שכל רכיב בה, המסומן , הוא משתנה מקרי ממשי.
נניח כי היא פונקציה סקלרית של .
אשר מחזירה ערך סקלרי, וקטור או מטריצה – בהתאם להקשר.
במקרה שבו הפונקציה היא סקלרית, מתקיים:
כאשר היא המטריצה הנוצרת מהחלפת הרכיב בערך חדש , בלתי תלוי סטטיסטית אך בעל אותה התפלגות כמו , בעוד שכל שאר הרכיבים נותרים ללא שינוי.
במקרה בו מחזירה מטריצה או וקטור, ניתן להגדיר את השונות על ידי נורמות מטריציוניות, כגון נורמת פרובניוס:
או נורמות אחרות בהקשר הרלוונטי.
הוכחת אי-שוויון אפרון-שטיין עבור פונקציות של מטריצות אקראיות עם כניסות בלתי תלויות
אי-שוויון זה הוא מקרה פרטי של אי-שוויון אפרון-שטיין הכללי, המיושם כאשר האובייקט האקראי הוא מטריצה בגודל , וההנחה המרכזית היא שכל הכניסות של המטריצה, עבור , הן משתנים מקריים בלתי תלויים הדדית.
תהי מטריצה אקראית בגודל .
נסמן את הכניסה בשורה ועמודה ב-.
נניח כי אוסף הכניסות מורכב מ- משתנים מקריים בלתי תלויים (לא בהכרח שווי התפלגות).
תהי פונקציה מדידה הממפה מטריצות בגודל למספרים ממשיים (פונקציה סקלרית).
לכל זוג אינדקסים כאשר :
יהי עותק בלתי תלוי של (כלומר, בעל אותה התפלגות כמו ובלתי תלוי בכל שאר הכניסות וגם ב- עצמו).
נגדיר את המטריצה האקראית כמטריצה הזהה ל- בכל הכניסות, פרט לכניסה שבה היא שווה ל-.
אי-שוויון אפרון-שטיין (לכניסות מטריצה בלתי תלויות): בתנאים אלו, השונות של הפונקציה הסקלרית מקיימת:
הוכחהההוכחה היא יישום ישיר של אי-שוויון אפרון-שטיין הכללי על אוסף המשתנים המקריים הבלתי תלויים .
נתייחס לאוסף הכניסות כאל וקטור ארוך של משתנים מקריים בלתי תלויים.
נסדר אותם בסדר כלשהו, למשל לפי שורות: .
הפונקציה יכולה להיכתב כפונקציה של המשתנים הללו:
2. יישום אי-שוויון אפרון-שטיין הכללי:
אי-שוויון אפרון-שטיין הכללי קובע כי עבור פונקציה של משתנים מקריים בלתי תלויים , מתקיים:
כאשר , ו- הוא עותק בלתי תלוי של .
כל אינדקס בטווח עד מתאים באופן ייחודי לזוג אינדקסים (), כך ש-.
הסכום הוא למעשה סכום על כל זוגות האינדקסים האפשריים : .
כאשר אנו מחליפים את המשתנה בעותק בלתי תלוי שלו , אנו למעשה יוצרים את המטריצה שהוגדרה קודם.
לכן, המשתנה מהנוסחה הכללית הוא בדיוק:
כאשר הוא האינדקס המתאים ל-.
נציב את הזיהויים הללו בנוסחת אפרון-שטיין הכללית:
נחליף את הסכום בסכום הכפול .
נקבל בדיוק את האי-שוויון המבוקש:
חשוב מאוד לזכור שהוכחה זו והנוסחה הספציפית הזו נכונות רק תחת ההנחה שכל הכניסות של המטריצה הן בלתי תלויות הדדית.
ההנחה הזו מתקיימת באנסמבלים מסוימים של מטריצות אקראיות (כגון מטריצות עם כניסות i.i.d גאוסיות או ברנוליות), אך אינה מתקיימת באנסמבלים חשובים אחרים (כמו אנסמבלים אורתוגונליים או אוניטריים (GOE, GUE) שבהם יש תלות הנובעת מהסימטריה/הרמיטיות).
משמעות ושימושים (בנוגע להכללה למטריצות)
אי-שוויון זה מספק חסם על השונות של פונקציה של מטריצה אקראית במונחים של הרגישות הפונקציה לשינוי כל רכיב בודד במטריצה.
למידה חישובית – ניתוח יציבות של אלגוריתמים מטריציוניים אקראיים.
ניתוח יציבות של PCA אקראי, דחיסת מטריצות, ומודלים סטטיסטיים המאומנים על נתונים מטריציוניים רועשים.
עיבוד אותות ותמונה – הערכת השונות של סטטיסטיקות המוגדרות על מטריצות נתונים, הערכת שונות של תהליכי סינון, דחיסה ושיפור איכות.
תורת המטריצות האקראיות: הוכחת תכונות ריכוז עבור נורמות מטריצות, ערכים עצמיים ודטרמיננטות.
סטטיסטיקה רב-ממדית: חסימת שונות של אומדנים כמו מטריצות קו-וריאנס.
עיבוד שפה טבעית: ניתוח רגישות של ייצוגים מטריציוניים של מילים ומשפטים.
ההנחה בדבר אי-תלות בין רכיבי המטריצה קריטית לתוקפו של אי-השוויון בצורה זו, אך קיימות גם גרסאות מורכבות יותר המתירות תלות מסוימת.
לשם הדגמה של אי-שוויון אפרון–שטיין עבור מטריצות אקראיות, נערוך ניסוי סימולציה בפייתון.
בניסוי זה נוצרו 100 מטריצות אקראיות בגודל 10×10, כאשר כל איבר במטריצות נבחר לפי התפלגות נורמלית עם תוחלת אפס ושונות אחת.
סכום המטריצות סומן ב-, והנורמה האופרטורית שלו חושבה.
הגרף שהתקבל מציג את התפלגות ערכי הנורמה שנמדדו לאורך 500 הרצות של הסימולציה.
על גבי ההיסטוגרמה צוינו הקו המקווקו הכחול, אשר מייצג את הממוצע של ערכי הנורמה, ואזור הצללה כחולה סביבו, המייצג סטיית תקן אחת מהתוחלת – ייצוג גרפי של שונות הדגימה.
ככל שהרצועה הזו רחבה יותר, כך השונות גבוהה יותר.
הקו האופקי המקווקו בצבע אדום כהה מדגים חסם הסתברותי הנגזר מאי-שוויון אפרון–שטיין – בהנחה של צפיפות נורמלית בקירוב, חסם עליון לסיכון שסטיית $||S||$ מהממוצע תהיה גדולה.
חסם זה מבוסס על השונות האמפירית של נורמת האופרטור, והוא ממחיש כיצד ניתן להשתמש באי-שוויון אפרון–שטיין כדי להעריך הסתברויות של סטיות קיצוניות במדדים מורכבים.
מהגרף ניתן לראות כי רוב ערכי הנורמה מרוכזים סביב הממוצע, אך קיימת שונות מסוימת שנלקחת בחשבון במסגרת החסם.
הגרף מדגים כיצד אי-שוויון אפרון–שטיין מספק חסם על ההסתברות לסטייה מהתוחלת, תוך שימוש בהשפעה של שינוי רכיב אחד בלבד (במקרה זה, החלפת מטריצה בודדת מתוך הסכום).
בכך הוא מציג כלי שימושי להערכת ריכוז סביב תוחלת גם בפונקציות מורכבות כמו נורמה של מטריצות.
ניתוח השפעה של שינוי רכיב בודד
במטרה לאמוד את השונות של הפונקציה S בעקבות שינוי של רכיב יחיד בסכום, חושב לכל סימולציה ההפרש בין ערך הפונקציה לפני ואחרי החלפת אחת מהמטריצות במטריצה אקראית חדשה.
ערך זה ריבועי חושב עבור כל אחד מ-100 הרכיבים בכל אחת מ-500 הרצות, וכתוצאה התקבלו 50,000 ערכים.
ההיסטוגרמה שהתקבלה מציגה את הפיזור של ערכים אלו.
מרבית הערכים קטנים וקרובים לאפס, מה שמעיד על כך שבדרך כלל שינוי מטריצה אחת אינו משפיע באופן משמעותי על ערך הנורמה הכוללת.
עם זאת, קיימים גם ערכים גדולים יותר בזנב ההתפלגות, המייצגים מקרים חריגים שבהם השפעת ההחלפה גבוהה יותר.
קו ממוצע מקווקו נוסף להמחשת ערך הציפייה של השונות המקומית.
לצד ההיסטוגרמה הוצג גם גרף קופסה (boxplot), שמציג את התפלגות הנתונים על פי חציון, רבעונים וערכי קצה, תוך הדגשת ערכים חריגים (outliers).
ניתוח זה מדגיש את העובדה שאף על פי שהשפעת שינוי בודד לרוב קטנה, יש לשקול את כל טווח השונות האפשרית בעת שימוש באי-שוויון אפרון–שטיין.
חשוב להבחין בין אי-שוויון אפרון-שטיין, המתמקד בשונות של פונקציה של משתנים בלתי תלויים, לבין שיטת שטיין אשר משמשת בעיקר כדי להעריך את המרחק בין התפלגות של משתנה מקרי להתפלגות נורמלית.
שיטה זו מובילה למגוון של אי-שוויונות הקרויים אי-שוויונות שטיין.
אי-שוויון שטיין הקלאסי מתייחס לקרבה להתפלגות הנורמלית הסטנדרטית .
אם ו- הוא משתנה מקרי כלשהו בעל פונקציית צפיפות , ונניח שקיימת פונקציה המקיימת את המשוואה הדיפרנציאלית של שטיין עבור פונקציה חסומה :
אזי, עבור פונקציה גזירה (בתנאים מתאימים של גזירות וחסמות), מתקיים:
אי-שוויון שטיין (הרגיל) אינו חוסם ישירות את הערך של ההפרש בין התוחלות, אלא משתמש במשוואה הדיפרנציאלית של שטיין כדי לקשר את ההפרש הזה לתוחלת של פונקציה אחרת ().
המטרה היא לבחור פונקציה מתאימה כך שההפרש ייתן מדד למרחק בין ההתפלגויות של ו- (למשל, מרחק קולמוגורוב-סמירנוב או מרחק ליפשיץ).
על ידי חסימת ניתן לקבל חסם על מרחק ההתפלגויות.
הניסוח המדויק של אי-שוויונות שטיין משתנה בהתאם למדד המרחק בין ההתפלגויות שרוצים לחסום ולתכונות של ההתפלגות של .
השימוש העיקרי בשיטת שטיין הוא במציאת חסמים על מרחקים אלה, ולא בניסוח אי-שוויון יחיד ופשוט כמו אי-שוויונות ריכוז סטנדרטיים (כמו הופדינג או צ'בישב).
לסיכום, אי-שוויון אפרון-שטיין ושיטת שטיין (המובילה לאי-שוויונות שטיין) הם כלים שונים עם מטרות שונות בהסתברות.
הרחבות אי-שוויון אפרון–שטיין המטריציוני: פולינומיים ולוגריתמיים
יהי זוג החלפה מטריציוני מסוג Kernel Stein Pair המוגדר על ידי פונקציה של משתנים מקריים בלתי תלויים .
כאשר היא נורמת שדנכט (Schatten p-norm).
אי-שוויון זה מאפשר לשלוט במומנטים פולינומיים של נורמת האופרטור של על ידי בקרת המומנטים של משתני התנאי, שהם לרוב קלים יותר לחישוב או הערכה.
אי-שוויון אקספוננציאלי (לוגריתמי) למטריצות אקראיות (Exponential Efron–Stein Inequality)
בהנחה ש־ חסומה (כלומר, נורמת האופרטור של מוגבלת), ולכל המקיים עבור פרמטר המתאים, מתקיים:
הוא משתנה התנאי (variance proxy).
ללא ההנחה על חסימות הנורמה, מתקיים גרסה מרוככת:
אי-שוויון זה מהווה הכללה מטריציונית חזקה של אי-שוויון אפרון–שטיין הקלאסי, ומאפשר להפיק גבולות ריכוז חדים ומנורמלים למטריצות אקראיות מורכבות.
שילוב אי-שוויונות אלה עם טכניקות כמו Matrix Laplace Transform method מוביל לאי-שוויונות זנב, גבולות על הערך המקסימלי של המטריצה ועוד.
הפרמטר תלוי בתכונות של ובפרמטרי ההחלפה.
פונקציית המומנט הגנרטיבי של המטריצה נשלטת באמצעות זו של משתנה התנאי , המאפשר הוכחות של גבולות זנב ופיזור.
שני האי-שוויונות מהווים הרחבות מטריציוניות לאי-שוויונות הקלאסיים של אפרון–שטיין, תוך שימוש בטכניקות מתקדמות של שיטת החלפות וניתוח מטריציוני.
פירוט ההוכחה המלא מופיע במאמר של טרופ.
אי-שוויון ברנשטיין למטריצות הוא אי-שוויון מרכזי בתורת ההסתברות ובתורת המטריצות האקראיות.
הוא מספק חסם הסתברותי על הסטייה של סכום של מטריצות הרמיטיות אקראיות ובלתי תלויות מתוחלת.
אי-השוויון מהווה הרחבה טבעית של אי-שוויון ברנשטיין הקלאסי, העוסק בסכום של משתנים מקריים סקלריים.
אי-השוויון שימושי במיוחד במצבים שבהם המטריצות בסכום עשויות להיות בעלות נורמה גדולה, אך השונות המצרפית שלהן (שנמדדת על ידי הנורמה של סכום תוחלות הריבועים) קטנה יחסית.
אי-השוויון במתכונתו המודרנית הופיע לראשונה בעבודתם של רודולף אלסווד (Rudolf Ahlswede) ואנדריאס וינטר (Andreas Winter) משנת 2002. הם השתמשו בו בהקשר של תורת האינפורמציה הקוונטית, ספציפית לחקר שיעורי התכנסות חזקים (strong converse rates) בערוצים קוונטיים.
מאז, אי-השוויון זכה לתשומת לב רבה, וגרסאות שונות, הכללות ושיפורים פותחו.
תרומה משמעותית במיוחד ניתנה על ידי ג'ואל טרופ (Joel A.
Tropp) במאמרו משנת 2012, שהציג הוכחה נגישה יותר וניסוח "ידידותי למשתמש" של אי-השוויון, ותרם רבות להפצתו ולהפיכתו לכלי סטנדרטי בתחומים רבים.
יהיו סדרה סופית של מטריצות אקראיות בלתי תלויות מממד , אשר כל אחת מהן היא הרמיטית.
נניח כי כל המטריצות הן ממוקדות, כלומר (מטריצת האפס) לכל .
נניח שקיים קבוע כך שהנורמה של כל מטריצה חסומה כמעט בוודאות: לכל כאשר היא הנורמה אופרטורית (הידועה גם כנורמה ספקטרלית), השווה לערך הסינגולרי הגדול ביותר של המטריצה (או הערך העצמי הגדול ביותר בערכו המוחלט, עבור מטריצות הרמיטיות).
נגדיר את "פרמטר השונות המטריציוני" (matrix variance parameter) של הסכום על ידי: כאן, היא תוחלת המטריצה .
מכיוון שכל היא הרמיטית, היא מטריצה חיובית (positive semidefinite), וכך גם תוחלתה .
לפיכך, הסכום הוא מטריצה חיובית, והנורמה האופרטורית שלו היא פשוט הערך העצמי הגדול ביותר של מטריצת השונות המצטברת הזו.
אזי, לכל , מתקיים אי-שוויון ברנשטיין למטריצות:
הערה: הקבוע במכנה האקספוננט עשוי להשתנות מעט בין גרסאות שונות של אי-השוויון בספרות, בהתאם לחסמים הספציפיים שבהם משתמשים בהוכחה.
אי-שוויון ברנשטיין למטריצות מספק חסם על ההסתברות שהנורמה (הספקטרלית) של סכום המטריצות האקראיות תסטה באופן משמעותי מתוחלתו (שהיא אפס).
החסם מציג התנהגות דואלית המזכירה את אי-שוויון ברנשטיין הסקלרי:
הקבלה לאי-שוויון ברנשטיין הסקלרי: באי-השוויון הסקלרי, חסם הזנב תלוי בשונות הכוללת ובחסם העליון על גודל המשתנים הבודדים.
באופן מקביל, אי-שוויון המטריצות תלוי בפרמטר השונות המטריציוני (שמכמת את השונות המצטברת של המטריצות) ובחסם העליון על הנורמה של המטריצות הבודדות.
אי-שוויון ברנשטיין למטריצות הוא הכללה של אי-שוויון ברנשטיין עבור משתנים מקריים סקלריים.
כאשר ממד המטריצות הוא 1 (d=1), הנורמה האופרטורית מתכווצת לערך המוחלט, והאי-שוויון הופך לאי-שוויון ברנשטיין הסטנדרטי עבור סכום של משתנים מקריים חסומים .
משמעות האיברים במכנה האקספוננט: המכנה משלב שני משטרים:
מקרה תת-גאוסיאני (Sub-Gaussian regime): כאשר קטן יחסית (ובאופן גס, ), האיבר הדומיננטי במכנה הוא .
החסם דומה להתנהגות זנב גאוסיאני, .
התנהגות זו אופיינית לסטיות קטנות הנשלטות על ידי השונות המצטברת, ברוח משפט הגבול המרכזי.
מקרה תת-אקספוננציאלי (Sub-exponential regime): כאשר גדול (), האיבר הדומיננטי במכנה הוא .
החסם דומה להתנהגות זנב פואסוני או תת-אקספוננציאלי, (עד כדי פקטורים קבועים).
התנהגות זו אופיינית לסטיות גדולות, הנשלטות על ידי הערכים הקיצוניים האפשריים של המטריצות (הנורמה המקסימלית ).
תפקיד הממד : הפקטור המופיע לפני האקספוננט הוא ההבדל הבולט ביותר בהשוואה לאי-השוויון הסקלרי (שם המקדם הוא 2).
הוא נובע מהמעבר למרחב מטריצות, ובאופן טכני, מהשימוש בעקבה (trace) של אקספוננט מטריציוני בהוכחה, והחסם עבור מטריצות חיוביות.
ניתן לחשוב על פקטור זה כמחיר שמשלמים על חוסר הקומוטטיביות של כפל מטריצות ועל העובדה שהנורמה של המטריצה מושפעת מ- ערכים עצמיים פוטנציאליים.
במקרים רבים, כאשר למטריצות יש מבנה נוסף (למשל, דרגה נמוכה), ניתן לשפר פקטור זה ולהחליפו ב"ממד אפקטיבי" הקטן מ-.
שימושיות: אי-השוויון יעיל במיוחד כאשר השונות המצטברת קטנה משמעותית מהשונות שהייתה מתקבלת אם היינו משתמשים בחסם הגס בלבד (למשל, כאשר ).
במצבים אלו, הוא מספק חסמים הדוקים יותר מאשר אי-שוויון הופדינג למטריצות, שאינו מתחשב במבנה השונות.
ההוכחה המודרנית הנפוצה, כפי שהוצגה על ידי טרופ, מתבססת על שיטת פונקציה יוצרת מומנטים (או טרנספורם לפלס) למטריצות, בשילוב עם אי-שוויונות יסודיים מתורת המטריצות.
מטרתנו היא לחסום את .
1. פירוק הנורמה: מכיוון ש- היא מטריצה הרמיטית, הנורמה האופרטורית שלה היא הערך המוחלט של הערך העצמי הקיצוני ביותר:
כאשר ו- הם הערכים העצמיים המקסימלי והמינימלי של , בהתאמה.
לכן, על ידי אי-שוויון האיחוד:
נשים לב ש- שקול ל-.
מכיוון שהסכום מורכב גם הוא ממטריצות הרמיטיות בלתי תלויות וממורכזות, עם אותו חסם נורמה ואותו פרמטר שונות , החסם על זהה לחסם על .
לכן, מספיק לחסום את ולהכפיל את התוצאה ב-2.
2. שימוש בחסם צ'רנוף ובעקבה: עבור (פרמטר שייבחר בהמשך), נשתמש בחסם צ'רנוף:
לפי אי-שוויון מרקוב, ההסתברות חסומה על ידי:
כעת משתמשים בקשר היסודי בין הערך העצמי המקסימלי לעקבה של אקספוננט מטריציוני.
לכל מטריצה הרמיטית , מתקיים הוא לוגריתם של הרדיוס הספקטרלי של המטריצה החיובית .
כמו כן, הרדיוס הספקטרלי של מטריצה חיובית חסום על ידי העקבה שלה:
מכאן מקבלים את החסם המבוסס על תוחלת העקבה:
3. חסם על תוחלת עקבת האקספוננט: זהו השלב המרכזי והטכני ביותר.
בשל אי-קומוטטיביות המטריצות, אינו מתפרק למכפלת אקספוננטים.
משתמשים בתוצאה עמוקה מתורת המטריצות, הנובעת ממשפט ליב (Lieb's theorem on trace convexity/concavity) או תוצאות קשורות כמו אי-שוויון גולדן-תומפסון.
תוצאה מרכזית (למשל, Tropp, Theorem 3.6) מאפשרת לחסום את תוחלת העקבה באופן איטרטיבי או ישיר:
4. חסם על הלוגריתם של תוחלת האקספוננט הבודד: השלב הבא הוא לחסום כל .
כאן משתמשים בתכונות של (הרמיטית, ממורכזת, חסומה בנורמה על ידי ).
ניתן להראות, על ידי הכללה של טכניקות מאי-שוויון ברנשטיין הסקלרי, כי מתקיים האי-שוויון המטריציוני (בסדר ליוונר, פירושו חיובית):
(הסימן מציין אי-שוויון בסדר ליוונר.
חסם זה תקף בתנאי ש- קטן מספיק, למשל ).
נסמן את הפקטור הסקלרי .
5. הרכבת החסמים: בהצבת החסם על בחזרה ושימוש בתכונות המונוטוניות של אקספוננט ועקבת מטריצות (ובפרט, העובדה ש- גורר עבור הרמיטיות), מקבלים:
נשתמש שוב בתכונת העקבה .
מכיוון ש- היא מטריצה חיובית ו-, נקבל:
6. אופטימיזציה של : מציבים את החסם על בחזרה לחסם צ'רנוף:
מבצעים אופטימיזציה על (בדומה לאי-שוויון ברנשטיין הסקלרי).
הבחירה האופטימלית (או קרוב לאופטימלית) של היא .
הצבת ערך זה של במעריך (לאחר חישוב אלגברי) נותנת:
7. התוצאה הסופית: לאחר הכפלה בפקטור 2 (כפי שהוסבר בשלב 1), מתקבל אי-השוויון המוצהר:
קיימות מספר גרסאות והרחבות לאי-שוויון ברנשטיין למטריצות:
מטריצות מלבניות: ניתן להכליל את אי-השוויון למקרה שבו הן מטריצות אקראיות מממד , כאשר אינן בהכרח הרמיטיות.
במקרה זה, הנורמה היא עדיין הנורמה האופרטורית, וההגדרות של משתנות מעט (לרוב מערבות את ו-).
מטריצות סימטריות: אם המטריצות Xi הן סימטריות, ניתן לקבל חסם דומה עם פקטור 1 במקום 2 לפני d.
תלות בממד אפקטיבי: הפקטור יכול להיות פסימי מדי אם למטריצות יש מבנה פנימי, כגון דרגה נמוכה.
ניתן להראות שבתנאים מסוימים, יכול להיות מוחלף ב"ממד אפקטיבי" או "דרגה יציבה" (stable rank), שיכול להיות קטן משמעותית מ-.
הרפיית תנאי אי-התלות: קיימות גרסאות של אי-השוויון עבור סדרות תלויות של מטריצות, למשל, סדרות המהוות מרטינגל (תורת ההסתברות) מטריציוני (Matrix Martingale).
גרסאות אלו דומות לאי-שוויון אזומה-הופדינג למטריצות.
גרסאות עם קבועים שונים: כאמור, קיימות גרסאות עם קבועים מעט שונים במכנה האקספוננט, הנובעות משימוש בחסמים שונים בהוכחה.
אי-שוויון ברנשטיין למטריצות הפך לכלי בסיסי וחשוב בתחומים רבים, ביניהם:
תורת המטריצות האקראיות: ניתוח התנהגות ספקטרלית של סכומי מטריצות אקראיות, חסימת ריכוז של מטריצות קווריאנציה אמפיריות סביב תוחלתן.
ניתוח אלגוריתמים של אמידה סטטיסטית בממדים גבוהים.
ריכוז של מטריצות גרעין (Kernel matrices).
ניתוח ניתוח גורמים ראשיים (PCA) אקראי ואלגוריתמי הורדת ממדים.
בניית אמדי קווריאנציה רובוסטיים וקביעת גבולות על שגיאות.
ניתוח של שיטות למידה מקוונת (online learning).
ניתוח של אלגוריתמים אקראיים, במיוחד אלגוריתמים על גרפים (למשל, חסימת ההפרש בין לפלסיאן של גרף אקראי לתוחלתו), ניתוח ספקטרלי של מטריצות סמיכויות של גרפים.
בנייה וניתוח של אלגוריתמי קירוב, למשל בבעיות כיסוי.
שיטות של ספרסיפיקציה ספקטרלית (spectral sparsification) של גרפים.
תורת האינפורמציה הקוונטית : כפי שצוין, האי-שוויון שימש במקור לחקר ערוצים קוונטיים ויכולת הבחנה בין מצבים קוונטיים.
עיבוד אותות: ניתוח שיטות שחזור ודגימה, למשל בחישה דחוסה (Compressed Sensing).
ניתוח רשתות מורכבות: חקר תכונות ספקטרליות של מטריצות שכנות (adjacency matrices) ומטריצות לפלסיאן של רשתות אקראיות.
דוגמה חישובית עבור מטריצה בגודל 2×2
כדי להמחיש את אי-שוויון ברנשטיין למטריצות, נבחן את המקרה הפשוט של שתי מטריצות מקריות סימטריות בגודל :
כאשר הם משתנים מקריים בלתי תלויים עם תוחלת אפס:
ונניח כי קיימת קבועה כך ש- כמעט תמיד.
עבור , הערכים העצמיים הם , ולכן:
לפי אי-שוויון ברנשטיין למטריצות, עבור ועבור כל :
כלומר, ההסתברות שהנורמה הספקטרלית של סכום המטריצות תחרוג מהערך דועכת אקספוננציאלית בקצב התלוי בפרמטרים ו-.
המחשה אמפירית של אי-שוויון ברנשטיין למקרה של מטריצה בגודל 2x2 - סימולציה נומריתהגרף מציג הדגמה אמפירית של אי-שוויון ברנשטיין למטריצות אקראיות, במקרה של סכום שתי מטריצות סימטריות בגודל 2×2.
הופעל ניסוי חישובי הכולל 10,000 דגימות.
בכל דגימה חושבו שתי מטריצות מקריות:
מטריצה שנייה: X2 = [[c, 0], [0, -c]] כאשר c נבחר גם הוא באותו טווח באופן בלתי תלוי
בכל הרצה חושבה הנורמה הספקטרלית (נורמת האופרטור) של סכום המטריצות: X1 + X2
העמודות הכחולות: ההתפלגות האמפירית של ערכי הנורמה הספקטרלית מתוך סימולציה של 10,000 דגימות.
הקו האדום: החסם התאורטי שניתן על ידי אי-שוויון ברנשטיין למטריצות.
הקו הירוק המקווקו: התוחלת האמפירית (הממוצע) של ערכי הנורמה כפי שנמדדו בניסוי.
ההצללה האדומה: תחום הריכוז הגבוה – אזור שבו הסיכוי לחריגה מערכי התוחלת קטן באופן אקספוננציאלי לפי הגבול התאורטי.
החסם שמספק אי-שוויון ברנשטיין במקרה זה הוא:
– גבול על הווריאנס הכולל.
– חסם על נורמת האופרטור של כל מטריצה.
הגרף מדגים כיצד ההתפלגות האמפירית מתכנסת סביב ערך ממוצע, ואת ההשפעה של הגבול התאורטי על סיכוי לסטיות קיצוניות.
הגרף ממחיש את האפקטיביות של אי-שוויון ברנשטיין: אף שהתפלגות הנורמה אינה ידועה מראש, החסם מצליח להקיף את הזנב של ההתפלגות בפועל.
ניתן לראות שההסתברות לחריגה משמעותית מהתוחלת נמוכה ומתאימה בקירוב לחסם התאורטי.
החסם מצליח "לכפות" גבול סביר מעל ערכי הקצה.
כלומר, חריגות גדולות מתרחשות לעיתים נדירות, בהתאם למה שהאי-שוויון קובע.
סימולציה נומרית עבור אי-שוויון ברנשטיין
כדי להמחיש את אי-שוויון ברנשטיין למטריצות ואת אופיו כחסם, ניתן לבצע סימולציה נומרית.
התמונה משמאל מציגה תוצאות של סימולציה כזו.
בסימולציה זו, נקבעו הפרמטרים הבאים:
חסם עליון על הנורמה של כל מטריצה:
מספר הניסויים (חזרות) בסימולציה: 5000
בכל אחד מ-5000 הניסויים הבלתי תלויים:
נוצרה סדרה של מטריצות אקראיות מממד .
כל מטריצה נבנתה כך שתקיים את תנאי אי-השוויון:
(דרך נפוצה להשיג זאת היא ליצור מטריצות עם רכיבים אקראיים ממשיים או מרוכבים בעלי תוחלת אפס ושונות קבועה, לבצע הרמטיזציה (למשל, אם היא מטריצת רכיבים גאוסיאניים), ואז לנרמל את המטריצה אם הנורמה שלה חורגת מהחסם ).
חושב הסכום של המטריצות: .
חושבה הנורמה אופרטורית של הסכום: .
לאחר 5000 חזרות, התקבלו 5000 ערכים של , המהווים מדגם אמפירי להתפלגות הנורמה של הסכום.
הגרף השמאלי מציג היסטוגרמה של 5000 ערכי שהתקבלו בסימולציה.
ציר ה-x מייצג את ערך הנורמה האופרטורית , וציר ה-y מייצג את צפיפות ההסתברות האמפירית.
ניתן לראות שהתפלגות הנורמה מרוכזת סביב ערכים מסוימים (באזור 6-8 במקרה זה).
למרות שתוחלת הסכום היא מטריצת האפס (), הנורמה שלו היא תמיד ערך אי-שלילי המודד את "גודל" הסטייה של ממטריצת האפס.
הריכוז שנצפה בהיסטוגרמה מדגים את העובדה שהסתברות לקבל ערכי נורמה גדולים מאוד היא נמוכה.
הסתברות זנב אמפירית מול חסם ברנשטיין (גרף ימין)
הגרף הימני משווה בין הסתברות הזנב האמפירית לבין החסם התאורטי של ברנשטיין:
ציר ה-x: ערך הסף .
ציר ה-y: הסתברות (בסולם לוגריתמי).
הסולם הלוגריתמי מדגיש התנהגות של דעיכה מעריכית.
הקו הכחול (רציף): מייצג את ההסתברות האמפירית , כפי שנמדדה בסימולציה.
ערך זה עבור נתון הוא פשוט שיעור הניסויים (מתוך 5000) שבהם הנורמה הייתה גדולה או שווה ל-.
הקו האדום (מקווקו): מייצג את החסם העליון התאורטי שמספק אי-שוויון ברנשטיין למטריצות: .
כדי לצייר גרף זה, יש צורך לחשב או לאמוד את פרמטר השונות עבור המטריצות הספציפיות שנוצרו בסימולציה (או להשתמש בחסם עליון עבורו).
מהגרפים ניתן ללמוד מספר דברים המדגימים את תכונות אי-שוויון ברנשטיין למטריצות:
החסם אכן מתקיים: הקו הכחול (ההסתברות האמיתית, כפי שנצפתה בסימולציה) נמצא תמיד מתחת או על הקו האדום המקווקו (החסם התאורטי).
זה מאשר את נכונות אי-השוויון עבור המקרה שנבדק – החסם אכן מהווה חסם עליון להסתברות הזנב.
החסם אינו בהכרח הדוק: קיים פער (gap) בין החסם האדום לבין ההסתברות האמיתית הכחולה.
הפער יכול להיות משמעותי, במיוחד עבור ערכי נמוכים.
הדבר נובע מאופיו הכללי של אי-השוויון, שנועד להיות נכון עבור כל התפלגות מטריצות המקיימת את התנאים (הרמיטיות, תוחלת אפס, נורמה חסומה, ושונות נתונה), ולכן הוא מהווה חסם "במקרה הגרוע" (worst-case bound) ואינו מותאם ספציפית להתפלגות הגאוסית (או אחרת) ששימשה בסימולציה.
לכידת הדעיכה המעריכית: למרות הפער, החסם של ברנשטיין (הקו האדום) מצליח ללכוד את קצב הדעיכה המהיר (המעריכי) של הסתברות הזנב, כפי שמשתקף בשיפוע הירידה הדומה של שני הקווים בציר הלוגריתמי.
ככל ש- גדל, ההסתברות לסטייה גדולה כזו יורדת במהירות, והחסם משקף נכונה התנהגות זו.
לסיכום, הסימולציה והגרפים מדגימים באופן ויזואלי כיצד אי-שוויון ברנשטיין למטריצות מספק חסם עליון על הסתברות לסטייה גדולה של נורמת סכום מטריצות אקראיות מתוחלתו (שהיא אפס, אך הנורמה חיובית), וכי חסם זה לוכד את הדעיכה המעריכית של הסתברות זו, גם אם אינו הדוק בכל נקודה.
אי-שוויונות ברנשטיין: הגרסה הסקלרית הקלאסית, שאי-שוויון המטריצות מכליל.
אי-שוויון צ'רנוף למטריצות (Matrix Chernoff Inequality): חסם ריכוז דומה, אך מיועד ספציפית לסכום של מטריצות חיוביות (PSD) אקראיות ובלתי תלויות.
לרוב נותן חסמים הדוקים יותר מברנשטיין במקרה זה, והתנאים מנוסחים במונחי הערכים העצמיים המקסימליים של המטריצות הבודדות.
אי-שוויון הופדינג למטריצות (Matrix Hoeffding Inequality): גרסה פשוטה יותר של אי-שוויון ריכוז למטריצות.
הוא מניח רק חסימות על הנורמה של המטריצות הבודדות () ולא משתמש במידע על השונות .
החסם המתקבל תלוי רק בסכום ריבועי החסמים .
הוא פחות הדוק מברנשטיין כאשר קטן משמעותית מסכום ריבועי הנורמות המקסימליות, אך פשוט יותר לשימוש כאשר מידע על השונות אינו זמין.
אי-שוויון אזומה-הופדינג למטריצות (Matrix Azuma-Hoeffding Inequality): הרחבה של אי-שוויון הופדינג למטריצות לסדרות תלויות של מטריצות המהוות מרטינגל (תורת ההסתברות) מטריציוני.
הוא מספק חסם על הסטייה של המרטינגל מערכו ההתחלתי.
בתורת ההסתברות, אי-שוויון בנט מספק חסם עליון על ההסתברות שסכום של משתנים מקריים בלתי-תלויים חורג מהתוחלת שלו ביותר מקבוע נתון.
אי-השוויון תקף עבור סכום של משתנים מקריים שהם חסומים כמעט בכל מקום ובעלי שונות סופית.
אי-השוויון הכי דומה באופיו לאי-שוויונות ברנשטיין, ואף מהווה שיפור לראשון שבהם.
אי-השוויון הוכח על ידי ג'ורג' בנט מאוניברסיטת ניו סאות' ויילס בשנת 1962.
משתנים מקריים בלתי-תלויים עם שונות סופית, ונניח שקיים כך שלכל מתקיים המאורע כמעט בוודאות.
הוכחה אפשרית מתבססת על אי-שוויון מרקוב ואי-התלות של המשתנים המקריים כדי לקבל לכל :
נסמן ונגדיר את הפונקציה המונוטונית העולה:
כאשר: ממזערת את אגף ימין, ועל ידי הצבה של ערך זה מתקבל אי-שוויון בנט.
אי-שוויון בנט דומה לאי-שוויונות ברנשטיין, וספציפית לראשון שבהם, שדורש שהמשתנים המקריים יהיו חסומים כמעט תמיד.
בחלק מהגרסאות של אי-שוויון ברנשטיין יש דרישות חלשות יותר מקיום של חסם על המשתנים המקריים ובהן לא ניתן להשתמש באי-שוויון בנט.
תחת התנאים של אי-שוויון בנט מתקבל חסם הדוק יותר מזה שמתקבל על ידי אי-השוויון הראשון של ברנשטיין שתקף למשתנים מקריים חסומים, בשל העובדה שלכל מתקיים: ועל ידי הצבה באי-שוויון בנט מקבלים: כאשר אגף ימין זה בדיוק הביטוי שמופיע באי-שוויון ברנשטיין הראשון עבור משתנים מקריים חסומים.
יהיו משתנים מקריים בלתי-תלויים עם התפלגות ברנולי.
מתקיים: ו-לכן לפי אי-שוויון בנט לכל :
ולפי אי-שוויון הופדינג לכל :
עבור: החסם שמתקבל מאי-שוויון בנט הוא:
כך שעבור אי-שוויון בנט נותן חסם הרבה יותר הדוק מזה שמתקבל מאי-שוויון הופדינג עבור ערכים קטנים של (למשל ) כפי שממחיש האיור.
לאי-שוויון בנט קיימות הכללות גם לאובייקטים מתמטיים שאינם משתנים מקריים בלתי תלויים, למשל:
קיימת גרסה למרטינגלים, בעזרתה ניתן לחסום הסתברות שקשורה לסכום של סדרת הפרשים בעזרת ביטוי שמכיל את הפונקציה והסתברות שקשורה לתוחלת המותנית של ריבוע המשתנים המקריים.
קיימת גרסה לאנליזה פונקציונלית, בעזרתה ניתן לחסום הסתברות שקשורה לסופרמום על פני משפחה של פונקציות מדידות שמקיימות תנאים מסוימים שמערב סכימה ביחס להרכבה עם משתנים מקריים שווי-התפלגות, בעזרת ביטוי שמכיל את הפונקציה והשונויות.
אי-שוויון גרותנדיק (GT) הוא תוצאה יסודית באנליזה פונקציונלית ובתורת האופרטורים.
הוא קובע כי עבור שדה קיים קבוע אוניברסלי (הנקרא קבוע גרותנדיק) כך שלכל מטריצה בגודל מעל , לכל מרחב הילברט מעל ואוסף וקטורים ו- בכדור היחידה של , מתקיים:
הקבוע הוא הקבוע המינימלי שמקיים את הגדרה זו, והוא שונה עבור השדות ו-.
ערכו המדויק של אינו ידוע עד היום.
עבור המקרה הממשי, , מעריכים כי .
אי-השוויון הוצג לראשונה על ידי אלכסנדר גרותנדיק בשנת 1953, במסגרת מאמרו על מכפלות טנזוריות.
גרותנדיק התעניין בהתנהגות פונקציונלים ליניאריים על מרחבי מכפלה, ואי-השוויון שגילה סיפק חסם חד שהיה מרכזי לפיתוח התאוריה.
לאחר מספר שנים, עיבדו יורם לינדנשטראוס ואלכסנדר פלצ'ינסקי את הניסוח לצורה מטריציונית, ובכך זכה אי השוויון לחשיפה מוגברת.
אי השוויון זכה לניסוחים שקולים בתחומים שונים במתמטיקה.
בין היתר הוצג כמשפט על צורות ביליניאריות חסומות, נורמות של מכפלות טנזוריות, אופרטורים בין מרחבי בנך, ואופרטורים בין המרחבים ו-.
כל אחד מהנוסחים מדגיש היבט אחר של אותה תופעה מתמטית.
אי-שוויון גרותנדיק חוצה תחומים ויש לו השלכות רבות מחוץ לאנליזה פונקציונלית.
לדוגמה, במדעי המחשב הוא מהווה בסיס לפיתוח אלגוריתם קירוב לבעיות NP-קשות.
בעזרת אי-השוויון ניתן להחליף בעיה קומבינטורית קשה בבעיה קמורה (SDP), תוך שמירה על פער קירוב חסום על ידי בין הפתרונות.
בתחום מידע קוונטי מופיע אי-השוויון במחקר אי-שוויוני בל, ובפרט בבעיית ההפרה המקסימלית האפשרית של גבולות קלאסיים (כגון חסם צירלסון).
כאן משקף את גודל ההפרה האפשרית על ידי מערכות קוונטיות.
אי-השוויון אף היווה השראה לפיתוח גרסאות מורחבות שלו (נקראות לעיתים "אי-שוויוני גרותנדיק מסוגים שונים"), אשר חלות על אופרטורים לא ליניאריים, מכפלות מולטילינאריות, גרפים, ועוד.
מאז פרסום מאמרו המקורי של גרותנדיק, מתמטיקאים שונים ניסו לפשט ולשפר את ההוכחה של אי-השוויון, וכן להשיג חסמים טובים יותר עבור קבוע גרותנדיק.
עבור המקרה המרוכב, הראה וכן .
לינדנשטראוס ופלצ'ינסקי (1968): הציגו את הניסוח המטריציוני של אי-השוויון ופישטו את הוכחתו של גרותנדיק למקרה הממשי, אך לא שיפרו את החסמים.
קריבין (1977): השיג את החסם העליון הממשי הטוב ביותר הידוע עד היום (שאינו אסימפטוטי): .
האגרופ (1981, 1987): הרחיב את שיטת קריבין למקרה המרוכב והשיג .
דייווי (1984): סיפק את החסמים התחתונים הטובים ביותר הידועים לזמנו: וכן .
בראברמן, מקריצ'ב, מקריצ'ב ונאור (2011): הראו באופן לא קונסטרוקטיבי שמתקיים , כלומר החסם של קריבין אינו הדוק.
עם זאת, טרם נמצא חסם עליון קונסטרוקטיבי טוב יותר.
נניח שיש לנו מטריצה של מספרים ממשיים.
אנו שואפים למקסם את הביטוי
כאשר ו- נבחרים מתוך .
אפשר לתאר זאת כבעיה קומבינטורית שבה אנו מקצים סימנים לקשתות של גרף ממושקל במטרה להגדיל את סכום המשקולות.
ערך הסופרמום של ביטוי זה הוא .
כעת, נרפה את ההגבלה - נאפשר ל- ו- להיות וקטורי יחידה במרחב הילברט כלשהו, ונבחן את הביטוי
הערך המקסימלי של ביטוי זה על פני כל מרחבי הילברט וכל בחירות וקטורי היחידה יסומן .
אינטואיטיבית אולי נצפה שככל שמאפשרים גמישות רבה יותר (בחירת וקטורים במקום סקלרים עם ערך מוחלט 1, או סימנים בלבד), הערך המקסימלי יכול לגדול.
אי-שוויון גרותנדיק קובע כי היתרון שמתקבל מהמעבר למקרה הווקטורי מוגבל על ידי קבוע אוניברסלי .
פורמולציה באמצעות הנורמה של אופרטור
ניתן לחשוב על אי-שוויון גרותנדיק גם מהפרספקטיבה של אופרטורים ליניאריים חסומים.
המטריצה מייצגת אופרטור ליניארי .
אם נגדיר נורמות בהתאמה לכל אחד מהמרחבים הווקטוריים האלו, ניתן לשאול - עד כמה עשוי האופרטור להגדיל את הנורמה של וקטור שהוא פועל עליו?
הנורמה האופרטורית המושרית עונה על שאלה זו: באופן שקול ניתן להגדיר:כאשר מתייחס למרחב הדואלי.
בחירה נפוצה של נורמה למרחב היא נורמת .
אם באותו האופן נבחר למרחב את הנורמה , אז הנורמה האופרטורית המתקבלת עבור היא:נורמה זו מקסימלית כאשר נבחר :אי שוויון גרותנדיק מכליל את הביטוי הזה.
אכן, ולכן נוכל להרחיב את ההגדרה למרחב הילברט כללי :נגדיר את "נורמת" גרותנדיק של המטריצה , כסופרימום של הביטוי הזה על כל מרחבי הילברט מעל :
אז, אי שוויון גרותנדיק גורס כי קיים קבוע אוניברסלי עבורו לכל מטריצה סופית מעל השדה :
במילים, הנורמה האופרטורית המקסימלית שמושרית מהמרחבים הנורמיים , לא יכולה לסטות יותר מדי מהנורמה האופרטורית המקסימלית שמושרית ממרחבי הילברט.
סקיצת הוכחה עבור המקרה הממשי
אלמנט מפתיע באי-שוויון גרותנדיק הוא קיומו של קבוע אוניברסלי עבור כל מרחבי הילברט מעל השדה .
אפשרות אחרת להסתכל על כך היא באמצעות הפורמולציה באמצעות הנורמה של אופרטור.
מהפרספקטיבה הזו, אי-השוויון מציג קשר בין קבוצת המרחבים הנורמיים לבין קבוצת כל מרחבי הילברט מעל .
דרך אחת להבחין מדוע קבוע כזה קיים, היא לשים לב שניתן לשכן וקטורים ממרחבי הילברט שונים כמשתנים מקריים במרחב הילברט עבור מרחב הסתברות .
כלומר, אם השיכון של הוא בהתאמה, נדרש .
מציאת שיכון שכזה היא טריוויאלית.
על ידי בחירת בסיסים אורתונורמליים למרחב ו- למרחב (לשם הנוחות נניח שהמרחבים ספרביליים וגם שהמרחב מממד אינסופי), נוכל לבחור שיכון:
כפי שנראה, אי-שוויון גרותנדיק נובע מקיומו של שיכון בעל תכונה נוספת - שהמשתנים המקריים שייכים גם ל- עבור כלשהו, והנורמות שלהם ב- חסומות באופן אחיד.
בחירות שונות של שיכונים כאלו יובילו לקבועי גרותנדיק שונים (שאינם בהכרח הדוקים).
נשים לב שמבין כל מרחבי , המרחב הוא מרחב הילברט היחיד.
מונוטוניות הנורמות על מרחבי משחקת תפקיד מפתח בפיתוח הקשר בין הנורמות שמופיעות באי-השוויון.
ניסוח תנאי מספק לקיום אי-שוויון גרותנדיק
ראשית, ניווכח שקיומו של שיכון מתאים גורר את אי שוויון גרותנדיק:טענה: תנאי מספק לקיום אי-שוויון גרותנדיק
יהי , ונניח כי קיים קבוע כך שלכל מרחב הילברט , ולכל בחירת וקטורים בכדור היחידה של , קיים מרחב הסתברות ושיכון כמשתנים מקריים , עבורם:
אז אי שוויון גרותנדיק מתקיים עם קבוע התלוי ב- וב-.הערה: למעשה, התנאי הנוסף על השיכון שלנו הוא קיומו של קבוע כך שהמומנט ה- של המשתנים המקריים חסום באופן אחיד.
אינטואיטיבית, ניתן לחשוב על תנאי זה כדרישה שהמשתנים המקריים יהיו "שטוחים דיו", כפי שיתבטא בהוכחה.
איך ניתן למצוא שיכון שכזה?
דוגמה אחת לבסיס מתאים היא מערכת ראדמאכר - סדרה של משתנים מקריים בלתי תלויים שלוקחים את הערכים בהסתברות כל אחד:
בהתאם לכך נבנה את השיכון:ובאותו האופן עבור .
נותר להוכיח את החסם על המומנט ה-, כאשר נזכור :טענה: חסם אחיד על המומנט הרביעי של מערכת ראדמאכר:
עבור כאשר , מתקיים:אם כן, מערכת ראדמאכר מהווה בסיס מתאים לשיכון שחיפשנו, וקיומה מוכיח את אי שוויון גרותנדיק!
היות ש-, מההוכחה שלנו מעלה נובע (עם , , ):בעוד שידוע .
למעשה, ניתן להגיע לחסם של קריבין בדרך דומה אך עם שיכון מתוחכם יותר.
אומדן נורמת החיתוך (Cut Norm)
בהינתן מטריצה ממשית בגודל , נורמת החיתוך שלה מוגדרת על ידי:
נורמת החיתוך קשורה לבעיית חתך מרבי (Max-Cut) בגרפים ומופיעה באלגוריתמי קירוב.
אי-שוויון גרותנדיק מספק קשר בין נורמת החיתוך, ו-.
עבור קבוע אוניברסלי (למשל, עבור מטריצות כלליות).
מאי-שוויון גרותנדיק אנו יודעים (ראה פורמולציה באמצעות הנורמה של אופרטור):
שילוב אי-שוויונות אלו מראה שניתן לקרב את באמצעות , ואת באמצעות :
בעוד שחישוב מדויק של (או ) הוא בעיה NP-קשה, ניתן לחשב את (או לקרב אותו) ביעילות עד לכל דיוק באמצעות תכנות SDP בזמן פולינומי בגודל המטריצה וב-.
לכן, אי-שוויון גרותנדיק מאפשר לקרב את נורמת החיתוך עד כדי פקטור (או ).
למת הרגולריות של סמרדי היא תוצאה בתורת הגרפים המאפשרת, בהינתן כל גרף (לא משנה כמה גדול הוא), לקרב אותו על ידי גרף בגודל קבוע, כשגודלו של הגרף המקרב נקבע רק על פי איכות הקירוב.
יישום נוסף של אי-השוויון של גרותנדיק הוא מציאת קירוב כזה עבור גרף נתון, באמצעות אלגוריתם קירוב לנורמת החיתוך (cut norm), בזמן פולינומי שאינו תלוי במספר הקודקודים בגרף.
מתברר כי "צוואר-הבקבוק" העיקרי בבניית חלוקה רגולרית של סמרדי בזמן פולינומי הוא לקבוע, גם כן בזמן פולינומי, האם זוג נתון של קבוצות קודקודים זרות קרוב להיות -רגולרי.
כאשר הוא מספר הקשתות בין הקבוצות ובאותו האופן עבור .
ניתן להראות שעבור מטריצה מתאימה, אם , הזוג הוא -רגולרי.
כאמור, ניתן לקרב את נורמת החיתוך באמצעות ואי-שוויון גרותנדיק.
בשנת 1935, אלברט איינשטיין, בוריס פודולסקי ונתן רוזן (EPR) פרסמו מאמר בו טענו שמכניקת הקוונטים אינה תאוריה שלמה של המציאות הפיזיקלית, ורמזו לקיומם של "משתנים חבויים" שיכולים להסביר את התוצאות הסטוכסטיות של מדידות קוונטיות באופן דטרמיניסטי (הפרדוקס של איינשטיין-פודולסקי-רוזן).
בשנת 1964, ג'ון סטיוארט בל הראה שכל תאוריית משתנים חבויים מקומית גוררת אי-שוויונות מסוימים (אי-שוויוני בל) לגבי המתאמים (קורלציות) בין מדידות הנערכות על מערכות פיזיקליות מרוחקות.
מכניקת הקוונטים, לעומת זאת, חוזה הפרה של אי-שוויונות אלו.
קלאוזר, הורן, שימוני והולט (CHSH) הציעו ב-1969 גרסה של אי-שוויון בל (אי-שוויון CHSH) שניתנת לבדיקה ניסיונית.
ניסויים רבים אישרו את תחזיות מכניקת הקוונטים והפרו את אי-שוויון CHSH, ובכך שללו תאוריות משתנים חבויים מקומיות.
ב-1980, בוריס צירלסון הראה שמכניקת הקוונטים עצמה מטילה חסם על מידת ההפרה האפשרית של אי-שוויון CHSH, ושקבוע גרותנדיק קובע את ההפרה המקסימלית של אי-שוויוני בל כלליים יותר (מסוג מסוים) במכניקת הקוונטים.
קבוע גרותנדיק מסדר (עבור מרחבי הילברט ממשיים), המסומן , הוא הקבוע המינימלי כך שלכל מטריצה ממשית בגודל , ולכל שני סטים של וקטורים ו- המקיימים ו-, מתקיים:
במילים אחרות, הוא קבוע גרותנדיק כאשר מרחב הילברט מוגבל להיות (או כל מרחב הילברט ממשי מממד לכל היותר).
הסדרה היא סדרה לא יורדת של קבועים.
הקבוע שהוגדר קודם הוא למעשה:באופן אינטואיטיבי, מודד עד כמה ניתן "להפר" את הגרסה הסקלרית של הביטוי כאשר הווקטורים חיים במרחב מממד .
לקבועים אלה יש יישומים חשובים, למשל בפיזיקה קוונטית בהקשרים של אי-שוויוני בל וחסם צירלסון (על שם המתמטיקאי בוריס צירלסון), ובאופטימיזציה.
לאורך השנים פותחו חסמים שונים על קבועי גרותנדיק אלו:
בהשראת אי-שוויון גרותנדיק, הוגדר קבוע גרותנדיק של גרף''' סופי כקבוע המינימלי כך שלכל פונקציית משקולות על הקשתות מתקיים:
כאשר היא ספירת היחידה של .
נסמן ב- את הקבוע המינימלי הזה.
נבחן, למשל, את הגרף דו-צדדי המלא .
אם הוא תת-גרף מושרה של , אזי .
לכן, לכל גרף דו-צדדי מתקיים .
ואולם, עבור גרפים כלליים הקבוע אינו נשאר חסום.
למעשה, ידוע כי קיים קבוע מוחלט כך שלכל גרף (ללא לולאות עצמיות) מתקיים:
חסם זה הוא הדוק אסימפטוטית.
במתמטיקה, ובפרט באנליזה פונקציונלית, אי-שוויון בסל הוא אי-שוויון המאפשר, בהינתן מרחב מכפלה פנימית, להשוות בין הנורמה של וקטור מסוים במרחב לערכי המכפלה הפנימית של אותו וקטור בקבוצת וקטורים אורתונורמלית (כלומר, קבוצת וקטורי יחידה אורתוגונלים בזוגות).
אחת המסקנות החשובות מאי-שוויון זה היא שבהינתן מרחב מכפלה פנימית וקבוצה אורתונורמלית, כל וקטור במרחב תלוי לכל היותר בקבוצה בת-מנייה של וקטורים מתוך הקבוצה האורתונורמלית.
אי-השוויון נקרא על שם פרידריך בסל, שהוכיח אותו בשנת 1828.
יהי מרחב וקטורי מעל שדה המרוכבים מממד אינסופי עם מכפלה פנימית ונורמה המושרית ממנה.
כמו כן, תהי קבוצה אורתונורמלית, כלומר:
לכל ( היא קבוצת המספרים הטבעיים)
אזי, לכל מתקיים אי-השוויון הבא:
אי-שוויון זה הוא אי-שוויון בסל.
כאשר אי-השוויון נובע מחיוביות הנורמה המושרית והשוויון הראשון נובע מליניאריות ברכיב הראשון ואנטי-ליניאריות ברכיב השני של המכפלה הפנימית.
על-ידי העברת אגפים מתקבל כי לכל .
מאחר שכל האיברים חיוביים, וכל תתי-הטורים הסופיים של הטור האינסופי המבוקש חסומים על-ידי , בהכרח הטור האינסופי כולו מתכנס וחסום אף הוא על-ידי (הדבר נובע מכך שבקבוצת המספרים הממשיים , כל סדרה מונוטונית עולה וחסומה מלעיל בהכרח מתכנסת).
תלות ליניארית בקבוצה אורתונורמלית שאינה בת מנייה
יהי מרחב וקטורי מממד אינסופי מעל שדה המרוכבים עם מכפלה פנימית ונורמה המושרית ממנה.
כמו כן, תהי היא קבוצה אורתונורמלית.
כלומר, היא לכל היותר קבוצה אינסופית בת-מנייה.
מניחים בשלילה ש- אינה בת-מנייה.
מגדירים קבוצת קטעים אינסופית בת-מניה באופן הבא:
ניתן לראות כי כל הקטעים הללו זרים בזוגות ושאיחודם הוא קבוצת כל המספרים הממשיים החיוביים.
לכל מספר שלם אי-שלילי מגדירים .
זוהי חלוקה של למספר בן-מנייה של תתי-קבוצות זרות בזוגות.
לכן בהכרח קיים כלשהו כך ש- היא קבוצה שאינה בת-מנייה, שכן אחרת הוא איחוד בן-מנייה של קבוצות מעצמה בת-מנייה, ולכן קבוצה בת מנייה בסתירה להנחה בשלילה.
מאחר ש- היא קבוצה שאינה בת-מנייה, קיימת לה תת-קבוצה שהיא אינסופית בת-מנייה.
עולה מכך ש- היא קבוצה אינסופית בת-מנייה כך שלכל מתקיים ש-.
מאחר שהקבוצה בת-מנייה ואורתונורמלית, איבריה מקיימים את התנאי באי-שוויון בסל, מה שמבטיח שהסכום מתכנס.
מנגד, הסכום מתבדר כי הוא סכום אינסופי שכל איבריו גדולים או שווים ל-.
הטלה באמצעות קבוצת אורתונורמלית בת מנייה
יהי מרחב הילברט מממד אינסופי עם מכפלה פנימית ונורמה המושרית ממנה.
כמו כן, תהי קבוצה אורתונורמלית.
אזי, לכל קיים יחיד כך ש:
על-פי אי-שוויון בסל, הסכום האינסופי מתכנס, מה שמאפשר להוכיח כי הסדרה היא סדרת קושי.
מאחר ש- הוא מרחב שלם (מתוך היותו מרחב הילברט), בהכרח הסדרה מתכנסת ל- כלשהו.
כמו כן, תהי מערכת אורתונורמלית שלמה.
ראשית, ניתן לצמצם את לתת-קבוצה בת-מנייה לפי המסקנה הראשונה לעיל, שכן המכפלה הפנימית בין לאיברי אינה מתאפסת לכל היותר לקבוצה בת-מנייה של .
לאחר מכן, מגדירים בהתאם למסקנה השנייה המופיעה לעיל.
לבסוף, ניתן להוכיח כי , שכן אחרת ניתן למצוא כך ש-, וזו סתירה להגדרת .
במתמטיקה, אי-שוויון המשולש הוא אי-שוויון מהצורה , כאשר היא פונקציית מרחק.
אי-השוויון מתאר את העובדה הגאומטרית שהקו הישר הוא הדרך הקצרה ביותר בין שתי נקודות; בפרט, אורכה של צלע במשולש אינו עולה על סכום אורכי הצלעות האחרות.
אי-שוויון המשולש נחשב לתכונה יסודית של כל שיטה למדידת מרחק, ומשום כך מניחים, כאקסיומה, שהוא מתקיים בכל מרחב מטרי או נורמי.
הגרסה החזקה נקראת אי-שוויון המשולש למטריקות לא ארכימדיות.
אי-שוויון המשולש בין מספרים ממשיים
ניתן לראות את אי-שוויון המשולש במספרים הממשיים כמקרה פרטי של אי-השוויון על הישר הממשי.
כיוון שהמרחק בין שתי נקודות על הישר נמדד באמצעות הערך המוחלט, אי-השוויון במקרה זה שקול ל-, לכל .
כשבוחרים c=0, b=y ו-a=x+y, מתקבלת הצורה החלופית .
צורה זו אפשר להוכיח בעזרת חיבור שני האי-שוויונים ו-, או בדיקה של האפשרויות השונות לסימנים של x ושל y.
גרסה נוספת של אי-שוויון המשולש היא: .
לצורך הוכחת אי השוויון נשתמש בתכונות ו-.
דרך נוספת היא להשתמש בשוויון , ואז .
לפי אי שוויון המשולש ולכן
ולכן לפי ש וגם אז
אי-שוויון המשולש ב הוא הטענה , המתייחסת למספרים מרוכבים.
ניתן להוכיח את נכונותו שם בכמה דרכים: גאומטרית, הוא שקול לתכונות היסוד של משולש; אלגברית, אפשר לקבל אותו על ידי העברת אגפים מתאימה והעלאה בריבוע; וניתן להסיק אותו מאי-השוויון הממשי באמצעות משפט פיתגורס.
אי-שוויון המשולש מבטא את העובדה שלא ניתן לקצר את הדרך מ-A ל-C על ידי מעבר בנקודה B.
זוהי תכונה יסודית כל-כך של מושג ה"מרחק", עד שהיא מהווה אחת מהאקסיומות המגדירות מטריקה ומרחב מטרי.
מאותה סיבה, מניחים את האקסיומה בהגדרה של נורמה ומרחב נורמי.
במתמטיקה, אי־שוויון קושי-שוורץ הוא אי־שוויון הקושר את המכפלה הפנימית והנורמה במרחבי מכפלה פנימית.
מכיוון שמרחבים וקטוריים רבים מצוידים במכפלה פנימית טבעית, יש לאי־שוויון קושי-שוורץ שימושים בתחומים שונים של המתמטיקה, ובפרט באנליזה פונקציונלית.
הגרסה הראשונה של האי־שוויון, אותה גילה אוגוסטין קושי ב־1821, קובעת כי
לאי־שוויון יסודי זה ידועות היום עשרות רבות של הוכחות.
קושי הוכיח גם ששויון מתקיים רק כאשר הווקטורים
פרופורציוניים זה לזה (תלויים ליניארית).
בוניקובסקי לא ראה צורך בהוכחה נפרדת של האי־שוויון החדש, והסתפק בציטוט האי־שוויון של קושי.
ב־1885 הזדקק הרמן שוורץ, שישב אז באוניברסיטת גטינגן, לאי־שוויון , המשווה בין אינטגרלים כפולים.
מאוחר יותר הובנו שלושה אי־שוויונות אלה כמקרים פרטיים של הגרסה הכללית יותר, התקפה בכל מרחב מכפלה פנימית .
שוורץ לא הכיר את ניסוחו של בוניקובסקי, וההוכחה שהציג לאי־שוויון שלו מתאימה לכל מרחב מכפלה פנימית (הוכחה זו, הנעזרת בתכונות פשוטות של פולינום ריבועי, מובאת בהמשך).
משום כך נקרא האי־שוויון הכללי אי־שוויון קושי-שוורץ.
האי־שוויון במרחבי מכפלה פנימית, ושימושים
בצורתו המודרנית, אי־שוויון קושי-שוורץ קובע שאם הוא מרחב מכפלה פנימית (מעל הממשיים או המרוכבים), אז לכל מתקיים
כאשר הנורמה המושרית על מן המכפלה הפנימית.
שוויון ממש מתקיים אם ורק אם תלויים ליניארית.
בין המקרים הפרטיים של האי־שוויון, ניתן למצוא את הטענות
המתקבלות מן המקרים (המרחב L2) עם המכפלה הפנימית הסטנדרטית בכל מקרה.
אם אחד הווקטורים שווה ל־0, האי־שוויון מתקיים באופן טריוויאלי כי שני האגפים שווים לאפס.
ההוכחה מתאימה גם למקרה שבו מרחב המכפלה הפנימית הוא מרחב וקטורי ממשי, וגם למקרה שבו הוא מרוכב.
פיתוח ביטוי זה יתן לנו משוואה ריבועית ב־, ומכיוון שאנו יודעים שערך הביטוי אי־שלילי, נוכל להסיק מכך שהדיסקרימיננטה של המשוואה הריבועית אי־חיובית.
מהאי־שוויון המתקבל נקבל את אי־שוויון קושי-שוורץ.
הפרבולה המיוצגת על ידי המשוואה נוגעת בציר X לכל היותר אך אינה עוברת מתחתיו, ולכן יש למשוואה פתרון אחד לכל היותר.
על כן נקבל מחישוב הדיסקרימיננטה:
אם האי־שוויון מתקיים באופן טריוויאלי (כי אגף ימין בו תמיד חיובי או אפס).
לכן נניח כי , ולאחר העברת אגפים וחלוקה ב־ נקבל:
הוצאת שורש ריבועי משני האגפים נותנת לנו את אי־שוויון קושי-שוורץ.
יהיו שני וקטורים במרחב מכפלה פנימית, ונוכיח את אי-השוויון.
אם או , ברור כי מתקיים שוויון.
נגדיר את הווקטור באופן הבא:
נשים לב כי ניצב ל-: שני וקטורים הם ניצבים אם ורק אם המכפלה הפנימית ביניהם היא אפס.
(הוכחה זו תקפה רק עבור מרחבי מכפלה פנימיים מעל )
אי שוויון המשולש במרחבים נורמיים בהם הנורמה מושרית ממרחב מכפלה פנימית, נובע מאי שוויון קושי-שוורץ:
לפי הגדרת הנורמה במרחבי מכפלה פנימית:
נפתח את הביטוי על ידי שימוש בתכונות המכפלה הפנימית ונקבל:
בשני האגפים מופיע מספר אי-שלילי שהועלה בריבוע, ולכן ניתן להוציא שורש:
בתורת ההסתברות, אי-שוויון צֶ'בּישב (גם: צ'בישוֹב) הוא אי-שוויון המאפשר להעריך את ההתפלגות של משתנים מקריים על ידי התוחלת שלהם.
אי-השוויון קרוי על שמו של ממציאו, המתמטיקאי הרוסי פפנוטי צ'בישב.
אי-שוויון צ'בישב קובע כי אם השונות והתוחלת של משתנה מקרי קיימות, אז
אי-שוויון צ'בישב מאפשר להעריך את ההסתברות לכך שמשתנה מקרי כלשהו יסטה במידה זו או אחרת מהתוחלת שלו, באופן מדויק יותר מאי-שוויון מרקוב, ונותן משמעות נוספת למושג השונות.
בפרט נובע ממנו שכאשר השונות קטנה, ההסתברות לסטיות גדולות מהתוחלת קטנה גם היא.
בעזרת אי-שוויון צ'בישב אפשר להוכיח את החוק החלש של המספרים הגדולים למקרה הפרטי שבו לסדרת המשתנים המקריים יש שונות סופית.
אי-שוויון צ'רנוף נותן גרסה חזקה יותר עבור משתני ברנולי.
בגרסה כללית יותר, אי-שוויון צ'בישב קובע כי .
אי-שוויון קאנטלי הוא גרסה חד צדדית של אי-שוויון צ'בישב.
עבור אינטגרציה רק על קבוצת הנקודות במרחב ההסתברות עבורן יתקבל גודל הקטן יותר או שווה לזה שהתחלנו ממנו:
חלוקת שני האגפים ב־ מביאה לצורה הכללית של אי-שוויון צ'בישב:
ניתן גם להוכיח את אי-שוויון צ'בישב ישירות מאי-שוויון מרקוב.
במתמטיקה, אי-שוויון ינסן טוען שממוצע ערכי פונקציה קמורה גדול או שווה לערך הפונקציה בממוצע הנקודות.
האי־שוויון נקרא על שם המתמטיקאי הדני יוהאן ינסן.
ניתן להבין זאת באופן אינטואיטיבי על ידי התרשים:
ממוצע הנקודות הוא אמצע הקטע שעליו מדברים, באיור מסומן על ידי הקו המקווקו.
ניתן לראות כי ערך הגרף הכתום בנקודה זו, מכיוון שהוא ליניארי, שווה לממוצע ערכי הפונקציה (הכתומה).
ניתן להשתכנע בקלות מכיוון שממוצע כל שתי נקודות הנמצאות מימין ומשמאל לאמצע הקטע באותו מרחק שווה לערך באותה נקודה.
עתה, נוסיף גרף (הגרף הירוק) המתאר פונקציה קמורה.
קל לראות כי מכיוון שהפונקציה קמורה, כל הערכים של הפונקציה יהיו גבוהים יותר מערכי הפונקציה הקודמת, או לפחות שווים להם.
מכיוון שבפונקציה הכתומה הערך באמצע שווה לממוצע, אם הערכים יגדלו ממוצע הערכים בהכרח יעלה ולכן הערך באמצע יהיה קטן בהכרח מממוצע הערכים.
הערך הממוצע יהיה גדול מערך הפונקציה בממוצע הנקודות, כמו שאומר אי שוויון ינסן.
אם פונקציה ממשית קמורה המוגדרת על קטע ואם אז מתקיים
אין במשפט דרישה שהנקודות הן שונות.
ניתן להשתמש בעובדה זו ולהוכיח הכללה של המשפט שבה הממוצע הרגיל מוחלף בממוצע משוקלל כלשהו.
אם הפונקציה היא קעורה, אי השוויון הוא הפוך.
לדוגמה, עבור הפונקציה , שהיא קעורה בקטע , אי-השוויון קובע ש-
לכל חיוביים שסכומם 1. כלומר, האנטרופיה של מרחב הסתברות עם n מצבים היא מקסימלית בהתפלגות האחידה.
אם פונקציה ממשית קמורה ואם מידת הסתברות על הקטע אז
מכאן ניתן לגזור כי עבור פונקציה ממשית קעורה ואם מידת הסתברות על הקטע אז
אם משתמשים בפונקציה הקמורה ומציבים , מקבלים את אי-שוויון הממוצעים .
במתמטיקה, ובמיוחד באנליזה פונקציונלית, אי שוויון המשולש האינטגרלי הוא גרסה של אי שוויון המשולש עבור הנורמה האינטגרלית.
משפט: אם היא פונקציה אינטגרבילית בקטע אזי מתקיים .
הערה: ניתן להוכיח כי אם אינטגרבילית בקטע , אז גם אינטגרבילית שם.
מהגדרת הערך המוחלט, לכל מתקיים ,
ומתכונת המונוטוניות של האינטגרל נסיק ש- .
מליניאריות האינטגרל נקבל ש- .
אי-שוויון כלכלי מתייחס להבדלים בין יחידים וקבוצות בתוך חברה מסוימת או בין מדינות בנוגע לבעלות על נכסיהם ולגובה הכנסתם.
המונח מעורר דיונים רבים, למשל, מהן סיבותיו והשלכותיו של האי-שוויון.
לגבי המדד עצמו, קיימת מחלוקת האם המדד מבטא שוויון הזדמנויות או שוויון בתוצאות.
אחת מההשלכות של אי-שוויון כלכלי הוא אי-שוויון בתחום הדיור.
כדי למדוד את רמת האי-שוויון הכלכלי בין יחידים או קבוצות שונות באוכלוסייה, משתמשים בדרך כלל במדדים המתייחסים לכלכלה בתוך גבולות מדינה מסוימת, מכיוון שמדינות שונות פועלות ועובדות כלכלית בצורות שונות.
ישנם מספר מדדים כמותיים שמשווים את שיעורי הרווחה של העשירים לעומת העניים.
מדד ג'יני הוא אחד מהמדדים הנפוצים למדידת רמת האי-שוויון הכלכלי.
ישנן סיבות רבות לאי-שוויון כלכלי בקרב חברות.
הסיבות הללו לעיתים קרובות בעלות קשר הדדי, אינן ליניאריות ומורכבות.
הגורמים המוכרים כמשפיעים על אי השוויון הכלכלי כוללים את שוק העבודה, היכולות הטבעיות, חינוך, מוצא, מין, תרבות, חוקים, מיסוי, נכונות לקחת סיכונים ועיבוי העושר.
סיבות אפשריות לאי- שוויון כלכלי בין מדינות הן המערכת הכלכלית של מדינה (לדוגמה קפיטליזם וסוציאליזם), מלחמות, יכולת תפוקה כלכלית המשתנה מאדם לאדם, המיקום הגאוגרפי, יחסי גומלין בין מדינות, סוגיות פוליטיות, מחצבים ועוד.
אחד הגורמים העיקריים לאי-שוויון כלכלי בקרב כלכלות השוק המודרניות הוא קביעת המשכורות על ידי השוק, בתנאי, ששוק זה הוא שוק חופשי הנשלט על ידי כללי ההיצע והביקוש.
לפי השקפה זו אי-השוויון נגרם על ידי ההבדלים בהיצע והביקוש לסוגי העבודות השונים.
עבודה בה יש עובדים פוטנציאלים רבים (הצע גבוה) אבל רק קומץ של משרות זמינות (דרישה נמוכה) תוביל בדרך כלל למשכורות נמוכות בקרב כלל העובדים בעבודה זו.
המשכורות הנמוכות נגרמות בשל התחרות בין העובדים.
דוגמה לכך היא העבודות אשר מצריכות מומחיות בסיסית יחסית כגון רחיצת כלים או שרות לקוחות.
בשל העובדה שמשרות אלו דורשת מעט מאוד מומחיות קודמת, עובדים רבים מוכנים לעבוד בעבודות אלו.
תחרות בשוק בקרב עובדים מובילה להורדה במשכורת משום שאם עובד אחד ידרוש משכורת גבוהה יותר, המעביד יכול פשוט למצוא עובד אחר שיסכים לעבוד במשכורת הנמוכה.
עבודה בה יש מעט עובדים פוטנציאלים (הספק נמוך) אבל דרישה גדולה לכישורים ספציפיים בהם העובדים הללו מחזיקים, תוביל למשכורות גבוהות יחסית עבור המשרות הללו.
זאת משום שהתחרות בין המעבידים תוביל להעלאת המשכורות.
דוגמה לכך הן עבודות המצריכות כישורים מתקדמים כגון מהנדסים או ספורטאים מקצועיים.
התחרות בין המעבידים נוטה להוביל למשכורות גבוהות יותר, משום שאם מעביד אחד יציע משכורת נמוכה, העובד יכול פשוט להתפטר ולמצוא בקלות יחסית עבודה במקום אחר בה יקבל משכורת גבוהה יותר.
על אף שהדוגמאות הנ"ל נוטות לשייך כישורים לביקוש גבוה ולמשכורות גבוהות, זהו לא תמיד הכלל.
לדוגמה, המשכורות של המתכנתים המומחים במדינות המערביות ירדו באופן משמעותי בעקבות התחרות עם המתכנתים במדינות המתפתחות אשר מוכנים לקבל משכורות נמוכות יותר.
מחקרים בארצות הברית מצאו ששכר גבוה במיוחד (בפרט בסקטור הציבורי) אינו נחוץ להשגת הקצאה יעילה בשוק העבודה ואין לו כל קשר למאמץ שמשקיעים העובדים.
בסקטור הציבורי השכר נקבע לעיתים קרובות לפי לחצים פוליטיים ואינו קשור בתפוקה או בביצועים.
התוצאות הסופיות של פעולות גומלין של ההיצע והביקוש מוביל לשינוי ההדרגתי של המשכורות השונות ולאי השוויון בגובה ההכנסות בשוק העבודה.
אנשים רבים מאמינים שקיים קשר הדדי בהבדלים בין התכונות המולדות של האדם כגון חכמה, חוזק, כריזמה לבין עושר.
ייחוס היכולות הטבעיות הללו לשוק העבודה מצביע כי היכולות הללו הן בדרישה גבוהה יחסית להצע שלהן ולכן משחקות תפקיד מכריע בקביעת גובה המשכורת של אלו אשר ניחנו בתכונת הללו.
גורם משפיע ביצירת אי-השוויון הכלכלי הוא היכולת המשתנה של פרטים להשיג חינוך או השכלה.
השכלה, במיוחד השכלה בתחום שבו יש ביקוש גבוה לעובדים, מאפשרת לבעלי ההשכלה להרוויח משכורות גבוהות יותר.
בניגוד אליהם, אלו שאינם מסוגלים להרשות לעצמם השכלה, או אלו שאינם בוחרים במסלול ההשכלה, מקבלים בדרך כלל משכורות נמוכות בהרבה.
כלכלנים רבים מאמינים כי הסיבה העיקרית לגידול באי השוויון הכלכלי בעולם משנות השמונים ואילך היא הגידול בביקוש לעובדים מיומנים בעיקר בתעשיות ההי-טק.
הם מאמינים כי דבר זה גרר עליה במשכורות עבור בעלי ההשכלה, אבל לא העלה את משכורתם של חסרי ההשכלה, דבר שהוביל לגידול באי השוויון.
הקיום של מינים שונים, מוצאות שונים ותרבויות שונות בחברה נחשב כגורם לאי שוויון הכלכלי.
תרבויות ודתות שונות אינן מעודדות צבירת עושר, ולכן המשתייכים לאותה תרבות או דת יהיו עניים יותר.
אפליה על בסיס מגדר או רבוצה חברתית יכולה גם היא לתרום לאי שוויון כלכלי.
במדינות רבות בעולם, עצם ההשתייכות למיעוטים אתניים מסוימים מגדילה את הסבירות להיות עני.
מגוון האפשרויות הקיים בתוך החברה לעיתים קרובות תורם ישירות לאי השוויון הכלכלי.
כאשר נאלצים לבחור בין האפשרות לעבוד קשה יותר ולהרוויח יותר כסף או ליהנות מנוחיות, אנשים רבים בעלי יכולות שוות ופוטנציאל שווה להרוויח את אותה המשכורת לעיתים קרובות בוחרים באסטרטגיות שונות.
גורם זה מוביל לבסוף לאי שוויון כלכלי בחברות בהם קיים שוויון הזדמנויות לכלל התושבים בהתאם ליכולותיהם.
עיבוי העושר (Wealth condensation) הוא תהליך שבו, בתנאים מסוימים, עושר נוטה להתרכז בבעלותם של אנשים או ישויות שהיו עשירים עוד קודם לכן.
לפי תאוריה זו, אלו שכבר אוחזים בעושר הם בעלי אמצעים להשקיע במשאבים חדשים ליצירת עושר או לחלופין למנף את העושר הצבור וכך הם מקבלים עוד עושר.
במשך הזמן, התרכזות העושר יכולה לתרום באופן משמעותי לקיום המתמשך של אי שוויון בתוך חברה.
לדוגמה, נהגי משאיות שבבעלותם משאית מרוויחים באופן עקבי יותר מאשר אלו שאין בבעלותם משאית, היות שבעל המשאית נמנע מתשלום דמי השכירות שנדרשים הנהגים לשלם לבעלי המשאיות (גם אם לוקחים בחשבון עלויות תחזוקה ושאר הוצאות).
משום כך, נהג משאית שיש לו רכוש מלכתחילה, יכול לקנות משאית עבור עצמו כדי להרוויח יותר כסף.
נהג שלא יכול להרשות לעצמו לקנות משאית, מרוויח פחות ולכן נתקע במלכוד 22, שבו הוא לא יכול לקנות משאית משל עצמו כדי להגדיל את ההכנסה שלו.
דוגמה נוספת יכולה להיות בעלות על דירה המאפשרת לאורך זמן חסכון כספי ניכר, וכן יצירת הון מעלייה במחירי הנדל"ן.
ישנן מדינות רבות בהן הבעלות על קרקעות עוברת בירושה על פני דורות רבים, ומנציחה אי שוויון כפועל יוצא של בעלות על עתודות קרקע נרחבות.
נושא שקשור לעיבוי עושר ומלכודות עוני הן ההשפעות של אי שוויון בין-דורי.
העשירים נוטים לספק לילדיהם חינוך טוב יותר, דבר שמשפר את הסיכויים שלהם להשיג הכנסה גבוהה יותר.
נוסף לזאת, העשירים בדרך כלל משאירים לילדיהם ירושה נכבדת, דבר שמהווה נקודת קפיצה לתהליך של עיבוי עושר של הדור הבא.
מקובל לבדוק את יכולת הניידות החברתית כמדד לשוויון.
הסחר החופשי בין המדינות יכול לעיתים רבות לגרום לכך שאי-שוויון כלכלי ברמה הגלובלית תשפיע על האי-שוויון הכלכלי בתוך המדינה.
כאשר המדינות העשירות מנהלות קשרי מסחר עם המדינות העניות, עובדי כפיים במדינות העשירות לעיתים רבות יקבלו משכורות נמוכות יותר כתוצאה מהעברת הייצור למדינות בהן שכרם של עובדי הכפיים נמוך.
במגזר השירותים קשה יותר להעביר את המשרות.
פעולות לצמצום אי השוויון הכלכלי
הניסיון הקיצוני ביותר לצמצום אי השוויון התרחש במדינות הקומוניסטיות של המאה ה-20, כאשר אלו פעלו במוצהר בניסיון למנוע פערים כלכליים.