בתשובה לeasy, 25/11/02 17:01
 |
|
 |
||
|
||||
 |
אל תהיה מצחיק. בסה"כ ציינתי תנאים המתארים סדרה אקראית בה מתקיימת התוצאה הרצויה. למה נטפלת דווקא ל"שווי התפלגות" ולא לשאר התנאים? למשל, גם סדרה בה כל הספרות זהות יכולה להיות אקראית. |
 |
 |
 |
|
|
|
||
|
||||
|
אני אשתדל. סדרה בה כל הספרות זהות יכולה אולי להתקבל באקראי, אבל זה מאוד לא סביר. בכל מקרה היא אינה אקראית. אתה הוספת תנאים שבהם תתקיים הדרישה ואני ציינתי שתנאים נוספים אלו אינם חלק מהטענה המקורית. סדרה אקראית אינה בהכרח שוות התפלגות, היא יכולה להיות סדרה אקראית בינארית (כלומר לכל הספרות חוץ מ0 ו1 הסתברות 0) וההתפלגויות שבה יכולות להיות תלויות. ברור שהתנאים שלך מגדילים את ההסתברות למציאת כל תת-סדרה סופית בסדרה אקראית אין סופית אבל עדיין זה לא בהכרח נכון שכל תת-סדרה סופית תמצא בה. |
|
|
|
|
|
|
||
|
||||
|
כדאי להעיר שאין דבר כזה "סדרה אקראית". במונח הזה מתכוונים יותר לתהליך המייצר סדרות, מאשר לתוצאות שלו. כמובן, כל סדרה שהוגרלה כבר, אינה אקראית אלא קבועה למהדרין, וההסתברות לקבל דווקא אותה (אפוסטריורי) היא אפס. לפעמים קוראים ל*תוצאה* של תהליך אקראי בשם כזה ("סדרה אקראית", או "מספר אקראי"), אבל זה מוצדק רק כאשר אין סכנה של בלבול (ולא נראה לי שזה המקרה שלנו). |
|
|
|
|
|
|
||
|
||||
|
מהי, אם כך, הגדרתך לסדרה אקראית? בסדרה המוגרלת תחת התנאים שציינתי מופיעה כל תת סדרה סופית בהסתברות 1. |
|
|
|
|
|
|
||
|
||||
|
נכון וכפי שעוזי כבר הסביר, זה לא מחייב שסדרה אינסופית כזאת תכיל תת-סדרה סופית מסויימת. אני לא מכיר הגדרה ממש טובה לסדרה אקראית. הגדרה שימושית היא סדרה שלא ניתן לתאר תחילית סופית שלה בסדרת סימנים (או ספרות) קצרה מאורך התחילית. (תאור, לצורך העניין, פונקציה שעבור מספר טבעי n מחזירה את הספרה במקום הn של הסדרה) |
|
|
|
|
|
|
||
|
||||
|
הגדרה מענינת, לא מקובלת במיוחד, הלקוחה מתחום תורת האינפורמציה במקום תורת ההסתברות. לרוע מזלך, אני משוכנע שסידרה כמו שהגדרת חייבת להכיל כל תת סדרה סופית ולמעשה חייבת להיות נורמלית. אם לא, יהיה אלגוריתם דחיסה שיתאר רישא בפחות מאורכה. אין לי זמן כרגע לחשוב על כך, אבל אופתע מאוד אם לא כך הוא המצב. בהבטחת תשובה מדויקת יותר מחר.. |
|
|
|
|
|
|
||
|
||||
|
נכון, זו לא הגדרה מקובלת, אבל כאמור, היא שימושית. (ולא סתם היא מגיעה מהתחום בו יש שימוש לסדרות אקראיות - תורת האינפורמציה) אני לא מצליח לחשוב על נימוק טוב למה לסידרה לא נורמלית חייב להיות אלגוריתם דחיסה כפי שתארת. אשמח אם תביא כזה. |
|
|
|
|
|
|
||
|
||||
|
יחס הדחיסה של אלגוריתם למפל-זיו שואף לאינפורמציה הממוצעת לספרה, ולכן סדרה שאינה נורמלית אפשר לדחוס באופן אפקטיבי. | |
|
|
|
|
|
||
|
||||
|
יחס הדחיסה ידוע, אבל אני לא רואה איך כמות האינפורמציה הממוצעת לספרה משתנה באופן משמעותי בסדרה שהיא ''כמעט'' נורמלית. (דהיינו מכילה כמעט כל תת-סדרה סופית) השינוי במקרה של סדרה כזו לעומת סדרה נורמלית ''ממש'' צריך להיות די זניח. אתה מוזמן להסביר לי למה אני טועה. |
|
|
|
|
|
|
||
|
||||
|
1. התייחסתי להגדרה של סדרה נורמלית שכתבתי למעלה, כלומר סדרה שבה השכיחות של כל רצף סופי שווה למה שהיינו מצפים מסדרה אקראית. כמובן שסדרה שבה רצף סופי מסויים הוא "אסור" אינה נורמלית, כך שהטענה שלי (שסדרות נורמליות אפשר לדחוס אפקטיבית) היא חזקה יותר (מהטענה שסדרה בלי רצף מסויים אפשר לדחוס אפקטיבית). 2. נניח שהאלפא-בית הוא בן K אותיות (למשל 2 או 10), ונניח שיש מלה מסויימת, באורך N, שאינה מופיעה כלל. אז אפשר לחשוב על הסדרה כאילו היא כתובה ב- N^K-1 ה"אותיות" שהן מלים מותרות באורך K; בפרט, האינפורמציה הממוצעת לאותיות החדשות חסומה על-ידי (log(N^K-1, וקטנה ממש מ- (K*log(N. 3. המלה "זניח" עשויה להטעות. אני לא טוען שהאנטרופיה יורדת באופן משמעותי; למשל, אם מספר תעודת הזהות שלי (9 ספרות) אינו מופיע, האינפורמציה הממוצעת לספרה היא לכל היותר (log(10)*(1-1e-10.31; פחות מ-(log(10 במידה זניחה, אבל עדיין פחות. |
|
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |