משתמש:Niryo12/תורת ההתחדשות
תורת החידושים (באנגלית: **Renewal theory**) היא ענף בתורת ההסתברות המכליל את תהליך פואסון עבור זמני המתנה (holding times) שרירותיים. בשונה מתהליך פואסון, שבו זמני ההמתנה מתפלגים מעריכית, בתהליך חידוש זמני ההמתנה יכולים להיות בעלי כל התפלגות, ובלבד שהם בלתי תלויים ושווי התפלגות (ב"ת וש"ה) ובעלי תוחלת סופית. **תהליך חידוש עם תגמולים** (Renewal-reward process) כולל בנוסף סדרה אקראית של תגמולים (או עלויות) המתקבלים בכל זמן המתנה; התגמולים הם ב"ת וש"ה, אך אינם חייבים להיות בלתי תלויים בזמני ההמתנה.
לתהליך חידוש יש תכונות אסימפטוטיות המקבילות לחוק החזק של המספרים הגדולים ולמשפט הגבול המרכזי. פונקציית החידוש (תוחלת מספר ההגעות) ופונקציית התגמול (תוחלת ערך התגמול) הן בעלות חשיבות מרכזית בתורת החידושים. פונקציית החידוש מקיימת משוואה אינטגרלית ר recursiבית הנקראת "משוואת החידוש". משוואת החידוש המרכזית נותנת את הערך הגבולי של הקונבולוציה של עם פונקציה אי-שלילית מתאימה. הסופרפוזיציה (הרכבה) של תהליכי חידוש ניתנת לחקירה כמקרה פרטי של תהליך חידוש מרקובי.
יישומים של התורה כוללים חישוב האסטרטגיה הטובה ביותר להחלפת מכונות בלויות במפעל; השוואת היתרונות ארוכי הטווח של פוליסות ביטוח שונות; ומידול של התפשטות מחלות מידבקות, כאשר "אחד האמצעים הנפוצים ביותר להסקה על מספר ההתרבות הבסיסי הוא באמצעות משוואת החידוש". פרדוקס הבדיקה (Inspection paradox) מתייחס לעובדה שדגימת מרווח חידוש בזמן שרירותי מניבה מרווח בעל ערך ממוצע הגדול מזה של מרווח חידוש ממוצע רגיל.
תהליכי חידוש
[עריכת קוד מקור | עריכה]מבוא
[עריכת קוד מקור | עריכה]תהליך חידוש הוא הכללה של תהליך פואסון. במהותו, תהליך פואסון הוא תהליך מרקובי בזמן רציף על המספרים השלמים החיוביים (בדרך כלל מתחיל באפס), אשר לו זמני המתנה בלתי תלויים ומתפלגים מעריכית בכל מספר שלם לפני המעבר למספר הבא, . בתהליך חידוש, זמני ההמתנה אינם חייבים להתפלג מעריכית; למעשה, זמני ההמתנה יכולים להיות בעלי כל התפלגות על המספרים החיוביים, כל עוד הם בלתי תלויים ושווי התפלגות (IID) ובעלי תוחלת סופית.
הגדרה פורמלית
[עריכת קוד מקור | עריכה]תהי סדרה של משתנים מקריים חיוביים, בלתי תלויים ושווי התפלגות, עם תוחלת סופית:
אנו מתייחסים למשתנה המקרי כ"זמן ההמתנה ה-" (או "זמן השהייה ה-").
נגדיר לכל :
כל נקרא "זמן הקפיצה ה-" (או זמן המאורע ה-), והמרווחים נקראים "מרווחי חידוש".
אזי מוגדר על ידי המשתנה המקרי:
- הפענוח נכשל (שגיאת תחביר): {\displaystyle X_t = \sum^\infty_{n=1} \operatorname{\mathbb{I}}_{{J_n \leq t}}=\sup \left{, n: J_n \leq t, \right}}
כאשר היא פונקציה מציינת:
- הפענוח נכשל (פונקציה "\begin{cases}" לא מוכרת): {\displaystyle \operatorname{\mathbb{I}}*{{J_n \leq t}} = \begin{cases} 1, & \text{if } J_n \leq t \ 0, & \text{otherwise} \end{cases} }
התהליך מייצג את מספר הקפיצות שהתרחשו עד זמן , והוא נקרא תהליך חידוש.
פרשנות
[עריכת קוד מקור | עריכה]אם מתבוננים במאורעות המתרחשים בזמנים אקראיים, ניתן לחשוב על זמני ההמתנה כזמן האקראי שחלף בין שני מאורעות עוקבים. לדוגמה, אם תהליך החידוש ממדל את מספר התקלות של מכונות שונות, אזי זמן ההמתנה מייצג את הזמן שבין התקלקלות של מכונה אחת להתקלקלות של המכונה הבאה.
תהליך פואסון הוא תהליך החידוש היחיד בעל תכונת מרקוב, מכיוון שהתפלגות מעריכית היא המשתנה המקרי הרציף היחיד בעל תכונת חוסר הזיכרון.
תהליכי חידוש עם תגמולים
[עריכת קוד מקור | עריכה]תהי סדרה של משתנים מקריים ב"ת וש"ה (תגמולים) המקיימים:
אזי המשתנה המקרי:
נקרא תהליך חידוש עם תגמולים (Renewal-reward process). נציין כי בניגוד ל-, כל יכול לקבל ערכים שליליים וגם חיוביים.
המשתנה המקרי תלוי בשתי סדרות: זמני ההמתנה והתגמולים . שתי סדרות אלו אינן חייבות להיות בלתי תלויות. בפרט, עשוי להיות פונקציה של .
פרשנות
[עריכת קוד מקור | עריכה]בהקשר של הפרשנות לעיל של זמני ההמתנה כזמן בין תקלות עוקבות של מכונה, ה"תגמולים" (שבמקרה זה יהיו שליליים) יכולים להיתפס כעלויות התיקון העוקבות שנוצרו כתוצאה מהתקלות.
אנלוגיה חלופית היא שיש לנו אווזה קסומה המטילה ביצים במרווחי זמן (זמני המתנה) המתפלגים כ-. לעיתים היא מטילה ביצי זהב במשקל אקראי, ולעיתים ביצים רעילות (גם הן במשקל אקראי) הדורשות סילוק אחראי (ויקר). ה"תגמולים" הם הרווחים/הפסדים הכספיים העוקבים (האקראיים) הנובעים מהביצים העוקבות () ו- מתעד את סך ה"תגמול" הפיננסי בזמן .
פונקציית החידוש
[עריכת קוד מקור | עריכה]אנו מגדירים את פונקציית החידוש כתוחלת של מספר הקפיצות שנצפו עד זמן כלשהו:
משפט החידוש האלמנטרי
[עריכת קוד מקור | עריכה]פונקציית החידוש מקיימת:
הוכחה החוק החזק של המספרים הגדולים עבור תהליכי חידוש גורר: כדי להוכיח את משפט החידוש האלמנטרי, מספיק להראות ש-הפענוח נכשל (שגיאת תחביר): {\displaystyle \left{\frac{X_t}{t}; t \geq 0 \right}} היא אינטגרבילית במידה שווה (Uniformly integrable).
לשם כך, נבחן תהליך חידוש קטום (truncated) שבו זמני ההמתנה מוגדרים על ידי כאשר היא נקודה כך ש-, אשר קיימת לכל תהליך חידוש לא-דטרמיניסטי. תהליך חידוש חדש זה הוא חסם עליון על והחידושים בו יכולים להתרחש רק על הסריג . יתרה מזאת, מספר החידושים בכל זמן מתפלג גיאומטרית עם פרמטר . לכן מתקיים:
- הפענוח נכשל (פונקציה "\begin{align}" לא מוכרת): {\displaystyle \begin{align} \overline{X_t} &\leq \sum_{i=1}^{[at]} \operatorname{Geometric}(p) \ \operatorname{E}\left[,\overline{X_t}^2,\right] &\leq C_1 t + C_2 t^2 \ P\left(\frac{X_t}{t} > x\right) &\leq \frac{\operatorname E\left[X_t^2\right]}{t^2x^2} \leq \frac{\operatorname E\left[\overline{X_t}^2\right]}{t^2x^2} \leq \frac{C}{x^2}. \end{align} }
משפט החידוש האלמנטרי עבור תהליכי חידוש עם תגמולים
[עריכת קוד מקור | עריכה]נגדיר את פונקציית התגמול:
פונקציית התגמול מקיימת:
משוואת החידוש
[עריכת קוד מקור | עריכה]פונקציית החידוש מקיימת:
כאשר היא פונקציית ההתפלגות המצטברת של ו- היא פונקציית צפיפות ההסתברות המתאימה.
הוכחה אנו יכולים לבצע החלקה (iterated expectation) על זמן ההמתנה הראשון: מהגדרת תהליך החידוש, מתקיים:
לכן:
כנדרש.
משפט החידוש המרכזי
[עריכת קוד מקור | עריכה]יהי תהליך חידוש עם פונקציית חידוש ותוחלת זמן בין-חידושים . תהי פונקציה המקיימת:
- היא מונוטונית ולא עולה
משפט החידוש המרכזי (Key renewal theorem) קובע כי כאשר :
משפט החידוש
[עריכת קוד מקור | עריכה]הצבת עבור כל נותנת כמקרה פרטי את משפט החידוש (Blackwell's renewal theorem):
- כאשר
ניתן להוכיח את התוצאה באמצעות משוואות אינטגרליות או על ידי טיעון צימוד (coupling). אף שזהו מקרה פרטי של משפט החידוש המרכזי, ניתן להשתמש בו כדי לגזור את המשפט המלא, על ידי בחינת פונקציות מדרגה ולאחר מכן סדרות עולות של פונקציות מדרגה.
תכונות אסימפטוטיות
[עריכת קוד מקור | עריכה]לתהליכי חידוש ותהליכי חידוש עם תגמולים יש תכונות המקבילות להחוק החזק של המספרים הגדולים, אשר ניתנות לגזירה מאותו משפט. אם הוא תהליך חידוש ו- הוא תהליך חידוש עם תגמולים, אזי:
בהסתברות 1 (כמעט בוודאות).
הוכחה תחילה נבחן את . על פי ההגדרה מתקיים: לכל , ולכן:
לכל .
כעת, מכיוון ש-, מתקיים:
כאשר כמעט בוודאות (בהסתברות 1). מכאן:
כמעט בוודאות (שימוש בחוק החזק של המספרים הגדולים); באופן דומה:
כמעט בוודאות.
לפיכך (מכיוון ש- חסום בין שני הביטויים):
כמעט בוודאות.
כעת נבחן את . מתקיים:
כמעט בוודאות (שימוש בתוצאה הראשונה ושימוש בחוק המספרים הגדולים על ).
לתהליכי חידוש יש בנוסף תכונה המקבילה למשפט הגבול המרכזי:
פרדוקס הבדיקה
[עריכת קוד מקור | עריכה]תכונה מעניינת של תהליכי חידוש היא שאם אנו ממתינים זמן שרירותי שנקבע מראש , ואז בודקים מהו אורך מרווח החידוש שמכיל את , אנו צפויים לגלות שהוא בדרך כלל גדול יותר ממרווח חידוש בגודל ממוצע.
מבחינה מתמטית, פרדוקס הבדיקה (Inspection paradox) קובע: לכל , מרווח החידוש המכיל את הוא גדול סטוכסטית ממרווח החידוש הראשון. כלומר, לכל ולכל :
כאשר היא פונקציית ההתפלגות המצטברת של זמני ההמתנה . דוגמה מוחשית היא פרדוקס האוטובוס: עבור התפלגות אקראית נתונה של הגעות אוטובוסים, נוסע ממוצע בתחנת אוטובוס חווה עיכובים ארוכים יותר מאשר מפעיל האוטובוסים הממוצע.
פתרון הפרדוקס נעוץ בכך שההתפלגות הנדגמת בזמן היא מוטת-גודל (size-biased), משום שהסיכוי שמרווח זמן ייבחר פרופורציונלי לגודלו. לעומת זאת, מרווח חידוש ממוצע אינו מוטה-גודל.
הוכחה נשים לב שזמן הקפיצה האחרון לפני הוא ; ושמרווח החידוש המכיל את הוא . אזי: - הפענוח נכשל (פונקציה "\begin{align}" לא מוכרת): {\displaystyle \begin{align} \operatorname{P}(S_{X_t+1}>x) & {} = \int_0^\infty \operatorname{P}(S_{X_t+1}>x \mid J_{X_t} = s) f_{J_{X_t}}(s) , ds [12pt] & {} = \int_0^\infty \operatorname{P}(S_{X_t+1}>x | S_{X_t+1}>t-s) f_{J_{X_t}}(s), ds [12pt] & {} = \int_0^\infty \frac{\operatorname{P}(S_{X_t+1}>x , , , S_{X_t+1}>t-s)}{\operatorname{P}(S_{X_t+1}>t-s)} f_{J_{X_t}}(s) , ds [12pt] & {} = \int_0^\infty \frac{ 1-F(\max { x,t-s }) }{1-F(t-s)} f_{J_{X_t}}(s) , ds [12pt] & {} = \int_0^\infty \min \left{\frac{ 1-F(x) }{1-F(t-s)},\frac{ 1-F(t-s) }{1-F(t-s)}\right} f_{J_{X_t}}(s) , ds [12pt] & {} = \int_0^\infty \min \left{\frac{ 1-F(x) }{1-F(t-s)},1\right} f_{J_{X_t}}(s) , ds [12pt] & {} \geq \int_0^\infty (1-F(x)) f_{J_{X_t}}(s) , ds = 1-F(x) = \operatorname{P}(S_1>x),[12pt] \end{align} }
מכיוון שגם וגם גדולים או שווים ל- לכל ערכי .
סופרפוזיציה
[עריכת קוד מקור | עריכה]אלא אם כן תהליך החידוש הוא תהליך פואסון, הסופרפוזיציה (סכום) של שני תהליכי חידוש בלתי תלויים איננה תהליך חידוש. עם זאת, תהליכים כאלה ניתנים לתיאור במסגרת מחלקה רחבה יותר של תהליכים הנקראת תהליכי חידוש מרקוביים. עם זאת, פונקציית ההתפלגות המצטברת של הזמן עד למאורע הראשון בתהליך הסופרפוזיציה נתונה על ידי:
כאשר ו- הם פונקציית ההתפלגות המצטברת של הזמנים בין המאורעות וקצב ההגעה של תהליך , בהתאמה.
דוגמה ליישום
[עריכת קוד מקור | עריכה]אריק היזם מחזיק ב- מכונות, שלכל אחת מהן אורך חיים תפעולי המתפלג אחיד בין אפס לשנתיים. אריק יכול לתת לכל מכונה לפעול עד שהיא מתקלקלת, בעלות החלפה של 2,600 אירו; לחלופין, הוא יכול להחליף מכונה בכל זמן שהיא עדיין פועלת בעלות של 200 אירו.
מהי מדיניות ההחלפה האופטימלית עבורו?
פתרון ניתן למדל את אורך החיים של המכונות כ- תהליכי חידוש-פרס (renewal-reward) בלתי תלויים ומקבילים, ולכן מספיק לבחון את המקרה . נסמן תהליך זה ב-. משכי החיים העוקבים של המכונות החלופיות הם בלתי תלויים ושווי התפלגות, ולכן המדיניות האופטימלית זהה עבור כל המכונות החלופיות בתהליך. אם אריק מחליט בתחילת חיי המכונה להחליף אותה בזמן , אך המכונה מתקלקלת במקרה לפני זמן זה, אזי אורך החיים של המכונה מתפלג אחיד על הקטע ולכן התוחלת שלו היא . לפיכך, תוחלת אורך החיים הכוללת של המכונה היא:
ותוכלת העלות למכונה היא:
לפי החוק החזק של המספרים הגדולים, העלות הממוצעת לטווח ארוך ליחידת זמן היא:
גזירה לפי נותנת:
השוואה לאפס למציאת נקודות קיצון:
ולכן:
אנו לוקחים את הפתרון היחיד בקטע : . זהו אכן מינימום (ולא מקסימום) מכיוון שהעלות ליחידת זמן שואפת לאינסוף כאשר שואף לאפס, מה שאומר שהעלות יורדת ככל ש- גדל, עד לנקודה 2/3 שבה היא מתחילה לעלות.
ראו גם
[עריכת קוד מקור | עריכה]ביבליוגרפיה
[עריכת קוד מקור | עריכה]- Cox, David (1970). Renewal Theory. London: Methuen & Co. p. 142. ISBN 0-412-20570-X. *Doob, J. L. (1948). "Renewal Theory From the Point of View of the Theory of Probability" (PDF). Transactions of the American Mathematical Society. 63 (3): 422–438. doi:10.2307/1990567. JSTOR 1990567. *Feller, William (1971). An introduction to probability theory and its applications. Vol. 2 (second ed.). Wiley. *Grimmett, G. R.; Stirzaker, D. R. (1992). Probability and Random Processes (second ed.). Oxford University Press. ISBN 0-19-857222-0. *Smith, Walter L. (1958). "Renewal Theory and Its Ramifications". Journal of the Royal Statistical Society, Series B. 20 (2): 243–302. doi:10.1111/j.2517-6161.1958.tb00294.x. JSTOR 2983891. *Wanli Wang, Johannes H. P. Schulz, Weihua Deng, and Eli Barkai (2018). "Renewal theory with fat-tailed distributed sojourn times: Typical versus rare". Phys. Rev. E. 98 (4). arXiv:1809.05856. Bibcode:2018PhRvE..98d2139W. doi:10.1103/PhysRevE.98.042139. S2CID 54727926.
{{cite journal}}: פרמטר לא ידוע|article-number=(עזרה)