תורת החישוביות/סיבוכיות קולמוגורוב/הסתברות אוניברסאלית: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
מ ←התכנות בניית עץ השיוך: הגהה |
←התכנות בניית עץ השיוך: הרחבה |
||
שורה 213:
.
</math></center>
}}
נשים לב ש-<math>\sum_{x \in \Sigma^*} P_U(x) \leq 1</math>. אם נחבר זאת למשפט הקודם, נקבל את המשפט הבא.
{{משפט|תוכן=
עבור מחרוזת <math>x</math>, נניח ש-<math>J(x)</math> היא קבוצת האינדקסים בהם <math>n_j(x)</math> התעדכן כלפי מטה. אז
<center><math> \sum_{x \in \Sigma^*} \sum_{j \;|\; j \in J(x)}|\Sigma|^{-(n_j(x) + 1)} \leq 1 </math></center>
}}
| |||