בשנת 2016 שיחק בסרט המתח "רואה החשבון" לצידם של בן אפלק, אנה קנדריק וג'יי. קיי. סימונס. בשנת 2017 שיחק בסרט "סטלין מת!", אשר מתאר את מאבקי הכוחות בעקבות מותו של יוסיף סטלין ב-1953.
אי-שוויון צ'רנוף
בתורת ההסתברות, אי-שוויון צ'רנוף או חסם צ'רנוף הוא אי-שוויון המתאר את הקשר בין סכום של משתני ברנולי לבין התוחלת של סכום זה. אי-שוויון צ'רנוף מראה דעיכה מעריכית של ההסתברות לכך שסכום המשתנים יהיה רחוק מהתוחלת הצפויה, כפונקציה של המרחק הנמדד בסטיות תקן. במילים אחרות, ההסתברות שהסכום יהיה רחוק t סטיות תקן מהתוחלת קטנה כפונקציה מעריכית ב-t.
באופן פורמלי,
יהיו formula_1 מאורעות בלתי תלויים אשר מתרחשים בהסתברות formula_2 כך שformula_3 (כלומר, formula_4)
אז מתקיים:
formula_5
מכיוון שסכום המאורעות מפולג בינומית, formula_6, תוחלת סכום המאורעות היא formula_7, וסטיית התקן היא formula_8.
מכיוון שהחסם המתקבל מעריכי, אי שוויון צ'רנוף חזק יותר מאשר אי-שוויון צ'בישב, ואי-שוויון מרקוב, בהם דעיכת הזנב פולינומית.
אי השוויון קרוי על שם המתמטיקאי הרמן צ'רנוף (Herman Chernoff), שהוכיח את אי-השוויון בשנת 1952. כיום משמש השם "אי שוויון צ'רנוף" לתיאור משפחה של אי שוויונות המבוססים על אי שוויון זה או על אי-שוויונות דומים לו כגון
אי שוויון הופדינג ואי שוויון ברנשטיין (שניתן לראותם כמקרה פרטי של אי-שוויון זה).
מוטיבציה ודוגמאות.
אי שוויון צ'רנוף נפוץ בתחומים רבים של המדעים בעיקר בחישובים סטטיסטיים של מדגמים וכן באנליזה של אלגוריתמים אקראיים במדעי המחשב, על מנת לחסום את הסתברות השגיאה של מדגם/אלגוריתם נתון.
למשל, נניח כי קיים אלגוריתם אקראי A שעונה את התשובה הנכונה בהסתברות 0.6 (ובהסתברות 0.4 עונה תשובה אחרת). דרך אפשרית לבניית אלגוריתם "משופר" תהיה להריץ את האלגוריתם A מספר רב של פעמים, ולענות את התשובה שחזרה על עצמה הכי הרבה פעמים. למשל, אם האלגוריתם A מחשב בעיה מסוימת שהתשובה עבורה היא "כן/לא", נגדיר אלגוריתם חדש B המריץ את האלגוריתם A מספר רב של פעמים (נניח, 100 פעמים) ועונה לפי הרוב. נצפה שכ-60 מההרצות יענו תשובה אחת (התשובה הנכונה), ושאר 40 ההרצות יענו תשובה אחרת. ונשאלת השאלה: מה ההסתברות של אלגוריתם B לטעות?
אי השוויון של צ'רנוף נותן נוסחה פשוטה המגדירה את הסתברות הכישלון של B כפונקציה של מספר ההרצות. נשים לב שאלגוריתם B טועה אם התשובה הנכונה הופיעה פחות מ-50 פעמים, כלומר, סטיה של 10 הרצות מן התוחלת הצפויה של 60 פעמים (כ-2 סטיות תקן). כמובן שאם היינו מריצים 1000 פעמים, אלגוריתם B יטעה כאשר התשובה הנכונה תופיע פחות מ-500 פעמים, כלומר סטייה של 100 מהתוחלת הצפויה (כ-6.5 סטיות תקן). מכאן ניתן להעריך שהסתברות השגיאה של B במקרה הראשון (100 הרצות) היא מסדר גודל של formula_9 ואילו במקרה שני (1000 הרצות) הסתברות השגיאה של B קטנה באופן משמעותי (עקב הדעיכה המעריכית) והיא מסדר גודל של formula_10.
באופן שקול, אם נתונה הסתברות השגיאה הרצויה מאלגוריתם B, ניתן לחשב את מספר ההרצות החוזרות של אלגוריתם A הנדרשות על מנת לעמוד בהסתברות זו.
משתנים בלתי-תלויים בהתפלגות זהה.
אי-שוויון צ'רנוף עבור משתנים בלתי-תלויים בהתפלגות זהה (i.i.d)
יהיו formula_1 משתנים אקראיים מפולגים זהה ובלתי תלויים (i.i.d), כך ש־formula_12. נסמן formula_13, ונסמן
את התוחלת של formula_14 ב־formula_15. אי השוויון קובע כי לכל formula_16
formula_17
וכן,
formula_18
כאשר formula_19 הוא דיברגנס קולבק-ליבלר.
אי-שוויון צ'רנוף עבור משתנים בלתי-תלויים.
וריאנט זה חוסם את ההסתברות שסכום המשתנים שונה מהתוחלת הצפויה, כאשר המרחק נמדד בכפולות של התוחלת (לעומת כפולות של סטיית התקן, כפי שמתקיים באי-שוויון לעיל).
יהיו formula_1 אינדיקטורים בלתי תלויים (משתנים אקראיים המקבלים ערך 0 או 1), ונניח שהסתברות כל מאורע נתונה
formula_21. נסמן את הסכום בתור formula_13 ואת התוחלת של הסכום formula_23 אזי מתקיים לכל formula_24
formula_25
formula_26
או באופן מעט פחות הדוק (אבל יותר נוח לשימוש)
formula_27
formula_28
או באופן כללי (Angluin/Valiant version)
formula_29
אי-שוויון צ'רנוף עבור משתנים תלויים.
אי תלות בין משתנים הוא תנאי מספיק אך לא הכרחי. הכללה של אי השוויון מתקיימת לכל קבוצה של formula_30 משתנים בינאריים המקיימת לכל תת-קבוצה formula_31,
formula_32
כאשר formula_33 הוא קבוע כלשהו formula_34, ו- |S| הוא מספר האיברים בקבוצה. במקרה זה נקבל:
formula_35.
אי-שוויון צ'רנוף מתקיים גם עבור משתנים שהם negatively related.
שמואל גוטמן
שמואל גוטמן (1925, רייצא, סלובקיה - 2006, ירושלים) היה מעצב גרפי ישראלי, אחראי על עיצוב מרבית הגופנים העבריים הנמכרים עם מערכת חלונות ותוכנת אופיס של מיקרוסופט.
נולד בעיירה רייצא הסמוכה לפרשבורג, צ'כוסלובקיה. מגיל צעיר עסק בשרטוט אותיות ובעיצוב גופנים. בתקופת השואה עסק בזיוף מסמכים לצורך הצלת יהודים. בין היתר זייף לעצמו ולעוד קבוצת יהודים תעודות המורות כי הם חברי המשטרה הלאומית ההונגרית, ועם תעודות אלו הגיעו לבודפשט. בתום המלחמה עלה לארץ ישראל כמעפיל והחל לעבוד במחלקה הגרפית של קק"ל.
בשנת 1964 הקים בירושלים את המסדרה העברית הראשונה לצורך מחשבים. מאוחר יותר היה אחראי לעיצוב הגופן הראשון של התנ"ך בהוצאת ידיעות אחרונות. גוטמן אחראי למרבית הגופנים העבריים הנמכרים עם מערכת חלונות ותוכנת אופיס של מיקרוסופט. כמו כן היו ברשותו יותר מ-400 גופנים שיצר. רוב הגופנים היו תעתיק של גופנים או של "הקו האמנותי" של גופנים קיימים בעברית או באותיות לועזיות (בעיקר אנגלית). גוטמן הוציא מספר מהדורות של הגדה של פסח וכן חומש עם פירוש רש"י בהוצאת ידיעות אחרונות.
גוטמן ראה בעבודתו שליחות דתית, בטוענו כי נולד עם "נשמה מתאימה לפיתוח האותיות של לשון הקודש".
ניסן רובין
ניסן רובין (נולד בה' בתשרי תרצ"ה, 14 בספטמבר 1934) הוא אנתרופולוג וחוקר תרבות חז"ל ופרופסור אמריטוס באוניברסיטת בר-אילן, מהמחלקה לסוציולוגיה ולאנתרופולוגיה. תחומי התמחותו העיקריים הם: חקר סוציולוגי ואנתרופולוגי של החברה היהודית בתקופת המשנה והתלמוד, כפי שהיא משתקפת בספרות חז"ל, וחקר סוציולוגי ואנתרופולוגי של טקסים בחברה בת-זמננו, ובהם טקסים לא-רשמיים וטקסים פרטיים.
ביוגרפיה.
ניסן רובין נולד בירושלים, שם למד בבית הספר היסודי "תלמוד תורה שילה". לאחר מלחמת העצמאות עברה משפחתו לתל אביב ושם סיים את לימודיו בישיבת ה"ישוב החדש", שבו קיבלו התלמידים תעודת בגרות אקסטרנית לאחר חמש שנות לימודים. את לימודיו התורניים המשיך בישיבת "חברון" בירושלים. ב-1954 התגייס לצה"ל ושירת בחטיבת גולני, תחילה בגדוד חי"ר ואחר כך בגדוד מרגמות כבדות ממנו השתחרר בדרגת סמל.
עם שחרורו מצה"ל ב-1957 למד לתואר ראשון בכלכלה ובסוציולוגיה באוניברסיטת בר-אילן, והיה מבוגרי המחזור השני של אוניברסיטה זו (1960). במסגרת לימודי החובה ביהדות שמע ניסן רובין קורסים בתלמוד אצל הפרופסורים שמואל ביאלבלוצקי, בנימין דה-פריז, יצחק דב גילת ושמשון רוזנטל, שמהם למד את המתודות של המחקר התלמודי. הוא שמע גם קורסים בהיסטוריה של עם ישראל בתקופת בית שני, המשנה והתלמוד אצל פרופ' משה בר. הקורסים ששמע היו מיועדים בחלקם למתמחים בתלמוד ובהיסטוריה של עם ישראל, כי כבר אז הייתה כוונתו להשתמש בגישה המתודית של מדעי החברה לשם חקר ספרות חז"ל.
מכיוון שהשילוב בין מדעי יהדות וסוציולוגיה נראה לו מעניין יותר מאשר השילוב בין מדעי יהדות וכלכלה, החליט להמשיך בלימודי תואר שני בסוציולוגיה באוניברסיטה העברית במגמה של סוציולוגיה היסטורית שבראשה עמד פרופ' יעקב כ"ץ. כן שמע את שיעוריהם של גרשום שלום, שמואל אטינגר ושאול אש. מלימודיו אלה עיצב את הפרספקטיבה הסוציאלית וההיסטורית שלו על החברה הישראלית והיהודית. פרופ' כ"ץ היה מקור ההשראה העיקרי לתפיסתו ובהדרכתו כתב את עבודת התזה לתואר השני.
תוך כדי לימודיו לתואר שני התקבל כאסיסטנט במחלקה לסוציולוגיה באוניברסיטת בר-אילן בשנת הלימודים תשכ"ד (1964) ובאותה שנה נבחר גם לשמש כיושב-ראש ראשון של ארגון הבוגרים של אוניברסיטת בר-אילן. הסוציולוגיה הפוזיטיביסטית הייתה באותם ימים בעלת מעמד הגמוני בישראל, וניסן רובין לימד קורסים בשיטות מחקר כמותיות. הוא הכניס לתוכנית הלימודים את שיטותיו החדשניות של פרופ' לואיס גוטמן ב"ניתוח שטחות", שאת שיעוריו במתודולוגיה שמע באוניברסיטה העברית. בעקבות הוראת קורסים אלה פרסם יחד עם פרופ' ארנסט קראוס וד"ר סטיבן מילר את הספר שיטות מחקר במדעי החברה.