משפט Valiant-Vazirani, או: איך להרוג השמות מספקות עם פונקציות תמצות אקראיות

מזמן לא היה פה פוסט על סיבוכיות ומתחשק לי. מה שאני רוצה לדבר עליו הפעם הוא תוצאה מפתיעה יחסית (אם כי לא מפתיעה מספיק כדי להכנס לפנתאון של "תוצאות מפתיעות בסיבוכיות") של Valiant ו-Vazirani שיש בה את כל מה שטוב … להמשיך לקרוא

איך אלגברה לינארית מתקשרת לשרשראות מרקוב (ואיך כל זה קשור לגוגל)

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

תדהמתלוטו

תדהמה בישראל: בהגרלת הלוטו השבועית עלו בגורל אותם מספרים בדיוק (לא באותו סדר, אמנם) כמו בהגרלת הלוטו של לפני חודש. אתרי החדשות כמרקחה: "תדהמה" מכריז Ynet. "סטטיסטיקאים יגידו שהסיכוי שואף לאפס, קונספירטיבים יחשבו על כוונות זדוניות". פרופסור לסטטיסטיקה גויס כדי … להמשיך לקרוא

ילדים (הסתברותיים) זה שמחה

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