§ 11. Завершимостъ работы алгоритма

93

сов (не исключается равенство нулю каких-то кратностей); пусть т = т_г + т₂ + ■■■ + т_п. Если т = О, то сеанс заканчивается, иначе вы­бирается очередной вопрос; вероятность того, что будет выбран i-й

вопрос, должна равняться —.

т

Сеанс обучения становится бесконечным, если, например, с неко­торого момента обучаемый начинает давать только неправильные от­веты. Но можно интересоваться вероятностями и средним временем ожидания некоторых событий в течение этого бесконечного сеанса. Пусть в некоторый момент только один вопрос, скажем, вопрос с но­мером 1, имеет кратность 1, а все остальные — кратности большие, чем 1. Предположим, что начиная с этого момента обучаемый ста­бильно дает неправильные ответы на предлагаемые вопросы. Найдем вероятность того, что рано или поздно обучаемый получит вопрос с номером 1, а также математическое ожидание времени, проходяще­го до появления этого вопроса (время измеряется количеством задан­ных вопросов). Пусть т — суммарная кратность, а п — общее число вопросов, т > п ^ 2. Вероятность получить вопрос с номером 1 после

i вопросов с другими номерами равна —, если i = 0, и равна

т

т-\ т m + i-2 1 т-1

. . ш

т т + 1'" m + i-1 m + i (m + i-l)(m + i)'

если i ^ 1. Поэтому вероятность получить рано или поздно вопрос с номером 1 равна

со

- + (т-1)Ут ^4тт ^- (11.1)

т-t—t (m + i- l)(m + 0

Так как

1 11

zz —

(m + i-l)(m + i) m + i-1 m + i' то для частичной суммы

_%=Xi

1

(m + i-l)(m + i)

i = l

имеем

1 1

N m m + N'

и lim s_N = —, откуда значение выражения (11.1) (искомая вероят­ность) есть

m m

94 Глава 3. Оценивание числа шагов (итераций) алгоритма

Математическое ожидание времени есть

со

При этом ряд 2 7—-L i _ iir—Т_i) расходится: члены этого ряда поло-

жительны, и i-й член есть в- (является величиной порядка -).

-) (является величиной порядка -Отсюда математическое ожидание (11.2) равно бесконечности.

Пусть теперь u вопросов (будем считать, что это вопросы с но­мерами 1,2,..., u) имеют кратность 1, а остальные n — u вопро­сов—кратность большую, чем 1, и пусть u ^2. Оказывается, что при стабильных неправильных ответах обучаемого на задаваемые вопро­сы математическое ожидание времени, проходящего до получения всех, кроме какого-то одного, вопросов с номерами 1,2,...,u, есть конечная величина. Докажем конечность среднего времени ожида­ния какого-нибудь одного вопроса с номером от 1 до u, далее можно применить индукцию. Вероятность получить такого рода вопрос по­сле i вопросов с номерами из диапазона от u + 1 до n полностью определяется значениями u,m,i:

m-u m-u+1 m-u+i-l u m ' m+1 '" m + i-1 ' m + i

Эта вероятность при i > u равна

u(m-u)(m-u+l)...(m-l)

-u+l)...(m-

(m-u + i)(m-u + i + l)...(m + i-l)(m + i)

Поэтому искомое математическое ожидание есть сумма некоторого конечного числа слагаемых и ряда

со

v-< u(m-u)(m-u+l)...(m-l) _fi ^

2-1 (m - u + i)(m - u + i + 1)... (m + i - 1)(m + i) ^{U J}'

i=u+l или

со

u(m-u)(m-u + l)...(m-l) V 7 -- ^{i + 1} „ -■.

' i—i (m-u + i)(m-u + i + l)...(m + i)

i=u+l

Упрощая, получаем

j + u+1

u(m-u)(m-u + 1)...(m-1)У

j^ (j +m)(j +m + l)...(j + m + u)