בתשובה להאייל האלמוני, 24/11/02 14:14
מה זה חוק גודווין? 108804
אני בכלל לא בטוח שבכל סדרה אינסופית של מספרים אקראיים חייבת להופיע כל סדרה סופית.
אתה (ואם לא אתה, אולי עוזי?) יכול להוכיח את זה?
מה זה חוק גודווין? 108816
נתחיל ממשפט פשוט יותר, שאומר שבכל סדרה אינסופית אקראית של ספרות תוכל למצוא כל תת-סדרה סופית של ספרות שתבחר. (הוכחה באינדוקציה, די מייגע אותי לרשום את זה בפירוט אבל אם תתעקש, ואם עוזי לא ישלוף איזה שפן פשוט יותר, אטרח).

עכשיו עבור לבסיס ספירה ששווה למספר הגדול ביותר בסדרה הסופית+1, וחזרת למשפט הקודם.
מה זה חוק גודווין? 108919
ההמשך ברור, המשפט הראשון לא.
אם אני בונה סדרה אקראית ע"י הגרלה של ספרות. (לשם הפשטות אני אניח התפלגות שווה) אני לא רואה איך אתה יכול להוכיח שבהכרח סדרה זו תכלול תת סדרה סופית מסויימת. אתה יכול להוכיח שההסתברות שהיא לא תכלול תת-סדרה סופית מסויימת היא קטנה מאוד ולמעשה שואפת ל0. אבל עדיין תתכן סדרה כזאת, מאחר וקיימות אין סוף (לא בר מנייה) סדרות כאלו.
מה זה חוק גודווין? 108925
ראשית, המלה "אקראי" אינה חד-משמעית. לפעמים מתכוונים למשהו שמגרילים (ולא חשוב איך בדיוק), ולפעמים דווקא להגרלה מהתפלגות אחידה. נניח שמדובר בסדרות שכל הספרות שלהן מוגרלות באופן לא תלוי מאותה התפלגות, שבה לכל ספרה יש הסתברות חיובית.

כל רצף סופי של מספרים מופיע, בהסתברות 1, בסדרה מקרית אינסופית. יתרה מזו, גם הסיכוי ש*כל* הרצפים הסופיים יופיעו בסדרה מקרית אינסופית, הוא 1.
לעומת זאת, לכל רצף סופי, קיימות סדרות אינסופיות שבהן הוא אינו מופיע.

העובדה שמאורע קורה בהסתברות 1 (ולא "שואפת ל-‏1"; זהו המספר 1 המוכר מהשוויון 1+1=2) אינה מבטיחה שהוא יקרה. היא רק אומרת שלא כדאי להמר על ההיפך (בשום יחס הימורים סופי).
מה זה חוק גודווין? 108932
כלומר, צדקתי?
למעשה קיבלתי כבר בדואר יעוץ מתמטי שאמר פחות או יותר את מה שאתה אומר והיווה את הבסיס להודעה הקודמת שלי.

מה הסיכוי למצוא את התנ"ך בשלמותו מקודד ברציפות במספר PI?
מה זה חוק גודווין? 108946
האבחנה החשובה היא (כפי שציינת) בין "נכון בהסתברות 1" לבין "נכון בהכרח".

מספר ממשי נקרא "נורמלי" אם כל רצף סופי מופיע בו, בשכיחות הנכונה (כלומר, 1/10 בחזקת מספר הספרות של הרצף). ידוע שכמעט כל‏1 המספרים הם נורמליים, למרות שלא קל למצוא כאלה.
משערים‏2 שפאי הוא מספר נורמלי, ואז, בפרט, אם נכתוב אותו בבסיס 256, אפשר יהיה למצוא בו כל רצף סופי של תווים. בינתיים ידועות‏2 כמליארד הספרות (העשרוניות) הראשונות של פאי, ולכן אפשר למצוא שם את רוב הרצפים של תשע ספרות.

אפשר לשאול גם את ההיפך: מה הסיכוי למצוא את פאי מקודד בתנ"ך?...

1 "כמעט כל" = לקבוצה המשלימה יש מידה אפס. כשמגרילים מספר (על-ידי הגרלת הספרות שלו באופן אחיד) הוא נורמלי בהסתברות 1.
2 למרות שלא ברור את מי זה מעניין
מה זה חוק גודווין? 108960
הסיכוי למצוא את פיי בתנ"ך הוא אפס, ולו רק בגלל סופיותו של האחרון. אפשר כמובן להחליט שפיי בתנ"ך זה 3, כמו שהחליטו בנברסקה על פי מידות ים הנחושת.
מה זה חוק גודווין? 108985
נכון שפאי אינו מספר רציונלי, אבל זה לא אומר שצריך ספר אינסופי כדי לתאר אותו. אפילו האייל יספיק: "היקף מעגל לחלק לקוטרו".

קירוב לא רע לפאי מקודד בפסוק על ים הנחושת: "ויעש [המלך שלמה] את הים מוצק, עשר באמה משפתו אל שפתו, עגול סביב, וחמש באמה קומתו, וקו(ה) שלשים באמה יסוב אותו סביב", כאשר למלה "קו" כתיב "קו" וקרי "קוה". היחס בין שתי המלים בגימטריה, 105/111, הוא קירוב טוב מאד ליחס בין שלוש (היחס המופיע בפסוק) לפאי (האמיתי).
הקירוב הזה הוא הקירוב הטוב ביותר האפשרי מבין כל אלו שהמכנה שלהם אינו גדול מ- 111.
האמנם? 108997
ומה שקרה כאשר שלחו את זה לאתר "מנוף":
ומה? 109000
אני מכיר את המקורות האלה היטב, וכל מלה שכתבתי - מדויקת.

אפשר לקבל קירובים אופטימליים של פאי על-ידי פיתוח לשברים משולבים. הקירובים הראשונים לשליש פאי הם כדלקמן:
1, 22/21, 111/106, 355/339, 103993/99306.
בפרט: אין קירוב רציונלי עם מכנה קטן מ- 99000, שהוא מדויק יותר מ- 355/339; אין קירוב רציונלי עם מכנה קטן מ- 339 שהוא מדויק יותר מ- 111/106.
מה זה חוק גודווין? 109066
ואני תוהה - האם אתה מתייחס לעובדה זו כהוכחה למשהו? האם לדעתך מי שכתב את הדברים קודד שם את הקירוב לפאי, מתוך כוונה מפורשת לקודד שם קירוב לפאי?
מה זה חוק גודווין? 109124
לא; לא.
מה זה חוק גודווין? 109181
כלומר מדובר לדעתך בקוריוז משעשע בלבד?
מה זה חוק גודווין? 109229
בדיוק. והכי משעשע - כמות המלל שאפשר לייצר מהקוריוז.

מעבר לזה, אני לא בקיא בהסטוריה של קירובים רציונליים לפאי, אבל אני מעריך ש- 333/106 הוא קירוב מצויין יחסית לתקופה שבה נכתב הפסוק. מהנתון הזה לבדו אי-אפשר להסיק דבר על הכוונה לטמון את הקירוב דוקא שם.
מה זה חוק גודווין? 109101
התאור שנתת לפאי מזכיר לי פרדוקס ישן שקראתי פעם, אודות המספר הקטן ביותר שאי אפשר לכתוב בפחות משלושים וארבע הברות.
רקוויאם למעגל 109130
ועוד דבר, יש סרט בשם "פיי" של הבמאי דארן אהרונופסקי, שגם עשה את הסרט "רקוויאם לחלום" עוצר הנשימה, שבו הגיבור מנסה למצוא איזו מחזוריות לא ברורה‏1 בערך העשרוני של פיי, תוך שהוא זוכה להתעניינות מצד גורמים בבורסה וחבורה של "קבליסטים", כל קבוצה מסיבות השמורות עימה.

1 שהרי פיי אינו רציונלי, ועל כן אינו ניתן ליצוג מחזורי, אבל אולי הוא חיפש משהו אחר.
1 108951
כמו אלוהינו.
Contact 108950
אינדוקציה על מס' האיברים בסדרה הסופית.

עבור n=1 זה טריביאלי. חפש בסדרה האינסופית את האיבר הראשון של הסדרה הסופית. מאחר ואיברי הסדרה האינסופית הוגרלו, ההסתברות לכך שלא תמצא אותה היא 0.

אם מצאנו תת-סידרה עם n-1 איברים ששוים ל n-1 האיברים הראשונים בסדרה הסופית, נסתכל על הסיפרה הבאה. אם שווה, גמרנו (ההסתברות לכך היא 0.1 אם הגרלת את הספרות בסדרה המקורית). אם לא, נבנה את הסידרה האינסופית הבאה שלנו: האיבר הראשון שלה הוא האיבר שאחרי האיבר האחרון בסדרה המקורית שהיה שווה לאיבר ה n-1 בסדרה הסופית, ונחזור על התהליך עבור הסדרה החדשה. מאחר ואפשר לחזור על התהליך ללא הגבלה, בעוד ההסתברות למציאת הספרה (ה-nית בסדרה הסופית שלנו) גדולה מאפס, ההסתברות לכך שנצליח היא 1 (כמו בשלב הראשון באינדוקציה).

אני מתנצל על שימוש במילים במקום בסימונים המקובלים (a(n וכו', אני מנסה להימנע משיחה בנוסח סמילי-ד. פר בתקווה שגם ילדות בנות 13 תוכלנה לעקוב והמערכת לא תוצף בתלונות.
Connecticut 108954
או שלא הבנתי או שהוכחת משהו אחר.
הטענה היתה שבסדרה אקראית ניתן למצוא כל תת-סדרה סופית ואתה הראית שקיימת סדרה אקראית שכוללת תת-סדרה סופית מסויימת.
זה לא אותו דבר.
Connecticut 108956
למה "קימת"? לא הינחתי כלום על הסדרה האינסופית שלנו מלבד שספרותיה הוגרלו. הראיתי ש*בכל* סדרה כזאת, ההסתברות למצוא *כל* סידרה סופית (שהרי גם לגביה לא הינחתי כלום) היא 1.

עוזי טוען שזה לא תואם את טענתי שזה אומר "בהכרח תימצא", ואני מניח שהוא צודק (מאחר וישנם מאורעות בעלי הסתברות 0 שכן קורים). במובן הזה אתה והוא צודקים כנראה. אבל אם כך אפשר לצמצם את ה"ויכוח" (אם מותר לקרוא לזה כך) לשאלה אם ספרה בודדת אחת (למשל: 7) תימצא ב*הכרח* בכל סידרה אינסופית של ספרות אקראיות. מה דעתך?

אגב, על הקוף המפורסם ההוא שאם יתנו לו מספיק זמן יקליד במקרה לגמרי את "המלט" בטח שמעת. זה אותו משפט עצמו.
Contact 108955
שוב - יש הבדל בין "קיימת סדרה המקיימת ..." לבין "כל סדרה מקרית מקיימת ..." לבין "הסיכוי שסדרה מקרית תקיים ... הוא 1".

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

הניסוח ההסתברותי של חוק מרפי: גם דברים שהסיכוי שלהם לקרות הוא אפס, עלולים לקרות.
Contact 108958
ראה את התשובה הקודמת שלי לאיזי. רק שוטים מתווכחים איתך על מתמטיקה.
שוטים? אחד, מסויים? 108986
אני תוהה אם זה מה שקורה כאן.
הלוואי, שיחזור כבר. 108987
מפיך לאוזניו הגלובליות 108988
מה זה חוק גודווין? 108822
כן.
(בהנחה שהם בלתי תלויים ושווי התפלגות ויש הסתברות חיובית לכל סיפרה, או משהו בדומה לזה)
מה זה חוק גודווין? 108912
העובדה שסדרה היא אקראית לא גוררת את שאר ההנחות שלך. (חוסר תלות, התפלגות אחידה וכו') גם אם הספרה 2 מופיעה בהסתברות כפולה מזו של הספרה 4 עדיין זו יכולה להיות סדרה אקראית.
מה זה חוק גודווין? 108991
מי כתב משהו על התפלגות אחידה?
מה זה חוק גודווין? 109001
כתבת ''שווי התפלגות''. אני לא בטוח מה זה אומר ונראה לי ש''התפלגות אחידה'' זה פרשנות סבירה.
אם התכוונת למשהו אחר, אני מתנצל.
מה זה חוק גודווין? 109075
''שווי התפלגות'' מציין את העובדה שכל הספרות בסידרה מוגרלות עם אותה התפלגות.
מה זה חוק גודווין? 109114
בסדר, אבל גם אם ההתפלגות היא שונה לספרות שונות זה לא בהכרח מונע מהסדרה להיות אקראית.
מה זה חוק גודווין? 109128
נכון, אך במקרה זה לא חייבת להופיע כל סדרה (ואף לא כל סיפרה) בהסתברות 1.
מה זה חוק גודווין? 109129
בדיוק, ולכן לא בכל סדרה אקראית וכו'.
מה זה חוק גודווין? 109133
חשבתי שהסכמנו (עפ''י הצעתך) שלצרכים שלנו סדרה אקראית היא סדרה שהספרות שלה מוגרלות.
מה זה חוק גודווין? 109161
בדיוק להפך, סדרה שספרותיה מוגרלות היא אקראית.
זה לא אותו דבר.
מה זה חוק גודווין? 109166
יצירת מספרים אקראיים היא פעולה חשובה מכדי להניח אותה ליד המקרה (רוברט קוביו)

ותודה לעוזי ו. (לא לזה שלנו, זה
מה זה חוק גודווין? 109321
בסדר. כנראה לא הבנתי נכון את מה שאמרת בתחילת תגובה 108919.

אם כן, טענִתי מצטמצמת ל:"קיימת הסתברות 1 שבכל סדרה אינסופית שספרותיה מוגרלות‏1, מוכל כל רצף סופי של ספרות". אני מתנצל על הניסוחים הלא מדויקים שלי.
_
1- ואני מודיע מראש שאין לי חשק להגדיר את טיבה של ההגרלה, אבל אם הטלת קוביה לא תספיק כמה נויטרונים חופשיים וגלאי גייגר בטח יכולים לספק הגרלה כזאת.
מה זה חוק גודווין? 109134
אל תהיה מצחיק.
בסה"כ ציינתי תנאים המתארים סדרה אקראית בה מתקיימת התוצאה הרצויה. למה נטפלת דווקא ל"שווי התפלגות" ולא לשאר התנאים?
למשל, גם סדרה בה כל הספרות זהות יכולה להיות אקראית.
מה זה חוק גודווין? 109171
אני אשתדל.
סדרה בה כל הספרות זהות יכולה אולי להתקבל באקראי, אבל זה מאוד לא סביר. בכל מקרה היא אינה אקראית.
אתה הוספת תנאים שבהם תתקיים הדרישה ואני ציינתי שתנאים נוספים אלו אינם חלק מהטענה המקורית.
סדרה אקראית אינה בהכרח שוות התפלגות, היא יכולה להיות סדרה אקראית בינארית (כלומר לכל הספרות חוץ מ0 ו1 הסתברות 0) וההתפלגויות שבה יכולות להיות תלויות.
ברור שהתנאים שלך מגדילים את ההסתברות למציאת כל תת-סדרה סופית בסדרה אקראית אין סופית אבל עדיין זה לא בהכרח נכון שכל תת-סדרה סופית תמצא בה.
מה זה חוק גודווין? 109235
כדאי להעיר שאין דבר כזה "סדרה אקראית". במונח הזה מתכוונים יותר לתהליך המייצר סדרות, מאשר לתוצאות שלו. כמובן, כל סדרה שהוגרלה כבר, אינה אקראית אלא קבועה למהדרין, וההסתברות לקבל דווקא אותה (אפוסטריורי) היא אפס.

לפעמים קוראים ל*תוצאה* של תהליך אקראי בשם כזה ("סדרה אקראית", או "מספר אקראי"), אבל זה מוצדק רק כאשר אין סכנה של בלבול (ולא נראה לי שזה המקרה שלנו).
מה זה חוק גודווין? 109255
מהי, אם כך, הגדרתך לסדרה אקראית?
בסדרה המוגרלת תחת התנאים שציינתי מופיעה כל תת סדרה סופית בהסתברות 1.
מה זה חוק גודווין? 109412
נכון וכפי שעוזי כבר הסביר, זה לא מחייב שסדרה אינסופית כזאת תכיל תת-סדרה סופית מסויימת.

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

בהבטחת תשובה מדויקת יותר מחר..
מה זה חוק גודווין? 109491
נכון, זו לא הגדרה מקובלת, אבל כאמור, היא שימושית. (ולא סתם היא מגיעה מהתחום בו יש שימוש לסדרות אקראיות - תורת האינפורמציה)
אני לא מצליח לחשוב על נימוק טוב למה לסידרה לא נורמלית חייב להיות אלגוריתם דחיסה כפי שתארת. אשמח אם תביא כזה.
מה זה חוק גודווין? 109641
יחס הדחיסה של אלגוריתם למפל-זיו שואף לאינפורמציה הממוצעת לספרה, ולכן סדרה שאינה נורמלית אפשר לדחוס באופן אפקטיבי.
מה זה חוק גודווין? 109665
יחס הדחיסה ידוע, אבל אני לא רואה איך כמות האינפורמציה הממוצעת לספרה משתנה באופן משמעותי בסדרה שהיא ''כמעט'' נורמלית. (דהיינו מכילה כמעט כל תת-סדרה סופית) השינוי במקרה של סדרה כזו לעומת סדרה נורמלית ''ממש'' צריך להיות די זניח.
אתה מוזמן להסביר לי למה אני טועה.
מה זה חוק גודווין? 109691
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 במידה זניחה, אבל עדיין פחות.

חזרה לעמוד הראשי המאמר המלא

מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים