לדלג לתוכן
שינוי מצב סרגל צד
Math-Wiki
חיפוש
יצירת חשבון
כלים אישיים
יצירת חשבון
כניסה לחשבון
דפים לעורכים שלא נכנסו לחשבון
מידע נוסף
שיחה
תרומות
ניווט
עמוד ראשי
שינויים אחרונים
העלאת קובץ
כלים
דפים המקושרים לכאן
שינויים בדפים המקושרים
דפים מיוחדים
מידע על הדף
עריכת הדף "
88-165 תשעב סמסטר ב/תקצירי הרצאות
" (פסקה)
דף
שיחה
עברית
קריאה
עריכה
גרסאות קודמות
עוד
קריאה
עריכה
גרסאות קודמות
אזהרה:
אינכם מחוברים לחשבון. כתובת ה־IP שלכם תוצג בפומבי אם תבצעו עריכות כלשהן. אם
תיכנסו לחשבון
או
תיצרו חשבון
, העריכות שלכם תיוחסנה לשם המשתמש שלכם ותקבלו גם יתרונות אחרים.
בדיקת אנטי־ספאם.
אין
למלא שדה זה!
=== הרצאה עשירית === מעבר להתפלגויות הקלאסיות, חשוב לדעת גם לטפל בתופעות שבהן חישוב ישיר הוא מסובך או בלתי אפשרי, כדי לקבל קירוב להתנהגות שלהן. בחנו מקרוב את הדוגמא המפורסמת של "פרדוקס יום ההולדת": הסיכוי שבין 23 אנשים יהיו שניים שנולדו באותו יום בשנה הוא מעט יותר מחצי, למרות ש-23 "הרבה יותר קטן" מ-365. ההסבר הוא בחישוב הסיכוי לכך שאין התנגשויות בבחירה אקראית של ימי ההולדת: מתברר שהסיכוי הזה יורד בקצב קרוב ל- <math>\ exp(-\frac{n^2}{2K})</math> כאשר n הוא מספר האנשים (כאן 23) ו-K גודל המרחב שבו הם בוחרים. בדרך כלל קל יותר לחשב תוחלות מאשר הסתברויות (במיוחד אם מדובר במשתנה שאפשר לפרק לסכום של משתנים מציינים רבים). גם לגבי ימי הולדת, קל לחשב שתוחלת מספר ההתנגשויות (כלומר, זוגות של אנשים שנולדו באותו יום) היא <math>\ \frac{n(n-1)}{2K}</math>, כך שמספר ההתנגשויות עולה באופן ריבועי עם מספר האנשים, וכאשר n הוא מסדר הגודל של <math>\ \sqrt{K}</math> אפשר כבר לצפות להתנגשויות. דיברנו גם על המשתנה של זמן ההמתנה (להתנגשות הראשונה), שגם התוחלת שלו - שאותה לא חישבנו - פרופורציונלית לשורש גודל המרחב. את הנימוקים האלה אפשר להפוך על ראשם כדי להעריך את גודל המרחב (כשזה אינו ידוע). אם המחשב בוחר מספרים באקראי ואחרי 979 צעדים מופיע לראשונה אותו מספר בפעם השניה, סביר להעריך שגודל המרחב הוא כ- 979 בריבוע, היינו כמליון. טכניקת הפירוק לסכום של משתנים מציינים מאפשרת לתאר את המבנה של גרף מקרי (שבו יש n קודקודים, וכל אחת מ-n-מעל-2 הקשתות הפוטנציאליות מתממשת בהסתברות p, באופן בלתי תלוי). נניח ש-p הוא פונקציה של n, וש-n שואף לאינסוף. תארנו בהרצאה מה קורה כאשר p הוא כפולה קבועה של <math>\ n^{-2}</math> (בשלב זה יש רק מספר סופי של קשתות), או של <math>\ n^{-3/2}</math> (מספר הקשתות שואף לאינסוף ובגרף יש מסלולים באורך 2, ולא יותר), וכן הלאה. הדרגה של קודקוד מוגדרת כמספר הקשתות שיוצאות ממנו. הדרגה של קודקוד, אם כך, מתפלגת <math>\ Bin(n,p)</math>, וכאשר n גדל אפשר לקרב התפלגות זו לפי התפלגות פואסון <math>\ P(np)</math>. בפרט, הסיכוי לכך שהקודקוד מבודד הוא בקירוב טוב <math>\ \exp(-np)</math>, ולכן תוחלת מספר הקודקודים המבודדים בגרף היא <math>\ n\exp(-np)</math>. אם למשל <math>\ p = \frac{\lambda \log(n)}{n}</math>, אז תוחלת מספר הקודקודים המבודדים היא <math>\ n^{1-\lambda}</math>, מה שמסביר מדוע כאשר <math>\ \lambda < 1</math> מספר הקודקודים המבודדים שואף לאינסוף, וכאשר <math>\ \lambda>1</math> הוא שואף לאפס (והגרף קשיר, למרות שזה דורש כמובן נימוקים נוספים).
תקציר:
לתשומת לבך: תורמים אחרים עשויים לערוך או אף להסיר את תרומתך ל־Math-Wiki. אם אינך רוצה שעבודתך תהיה זמינה לעריכה על־ידי אחרים, אין לפרסם אותה פה.
כמו־כן, שמירת העריכה משמעה הבטחה שכתבת את הטקסט הזה בעצמך, או העתקת אותו ממקור שאינו מוגן בזכויות יוצרים (אפשר לעיין בדף
Math-Wiki:זכויות יוצרים
לפרטים נוספים).
אין לעשות שימוש בחומר המוגן בזכויות יוצרים ללא רשות!
ביטול
עזרה בעריכה
(נפתח בחלון חדש)