למישהו יש כיוון?

[roger9]

למישהו יש כיוון?

זה אמור להיות קשור לשיטה ההסתברותית..

C זו סדרה של מחרוזות בינאריות.
C נקראת חופשית אם אף מחרוזת בC היא לא תחילית של מחרוזת אחרת בC.

בחלק הראשון יש להראות כי עבור C חופשית מתקיים:
zz sum_(x in C) 1/(2^x) < 1 zz כש |x| זה אורך המחרוזת x.

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

 

[ןן גיל ןן]

רמז

תתאים לכל מחרוזת תת-קטע של הקטע הממשי [0,1] כך שהקטעים שיתקבלו יהיו זרים.

 

[nox120]

ניסוח לא שלם

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

 

[roger9]

זה אכן קטן שווה, ולא קטן ממש. מתנצל על חוסר הדיוק.

 

[nox120]

אם השאלה היא על סדרות סופיות, נסה באינדוקציה על אורך הסדרה.

 

[יונתן 2000]

עוד אפשרות

נניח שהמחרוזת הארוכה ביותר היא באורך L, נסה להכפיל את שני האגפים ב-
2^L

 

[עעעערררר]

גישה הסתברותית

הטל מטבע (בינארי) הוגן אינסוף פעמים.
לכל מחרוזת x, התאם את המאורע "תוצאת |x| ההטלות הראשונות היא בדיוק x".
&nbsp
מה הסיכוי לכל מאורע? מה הסיכוי לכולם ביחד?

 

[roger9]

תשובה

עבור מחרוזת x,
|x| ההטלות נותנות בדיוק את x זה 1 חלקי סך האפשרויות עבור סדרת ביטים בגודל |x| . כלומר 1 חלקי 2 בחזקת הגודל של x.

עבור כל אורך של x, הסיכוי יהיה סיגמה 1 עד אינסוף של 1 חלקי 2 בחזקת הגודל של x. כלומר 1?

 

[עעעערררר]

על מה אתה סוכם?

 

[roger9]

הסיכוי שמחרוזת מ-C היא רישא של המחרוזת הראנדומית

הוא סכום של 1 חלקי zz 2^(|x|) zz, כשהסכום הוא על פני המחרוזות x in C.
לא?

 

[עעעערררר]

אכן. איך יצא לך 1?

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