Матожидание для случайной последовательности символов

[B@R5uk]

Someone в сообщении #1285977 писал(а):

А среднее квадратичное отклонение какое?

Среднее квадратичное отклонение в этом случае нет смысла считать, потому что получится характеристика самой случайной величины, а не оценка того, с какой точностью посчитано её среднее значение. Если уж считать СКО, то надо провести несколько серий экспериментов по определению среднего значения и уже для этих полученных средних посчитать среднее и отклонение от него. СКО надо дополнительно поделить на корень из числа опытов.

Вот я провёл эксперимент с разумными значениями исходных параметров:

Используется синтаксис Java

import java.util.*;

public class Study_Probability_p1677 {
        private static final Random rng = new Random();
        private static final int setSize = 3;
        private static final int wordSize = 4;
        private static final int testsNumber = 1000000;
        private static final int[] testsResults = new int[testsNumber];
        
        public static void main(String[] args) {
                int n, value, counter, charsCounter;
                double meanResult = 0.0;
                for (n = 0; testsNumber > n; ++n) {
                        counter = 0;
                        charsCounter = 0;
                        while (true) {
                                value = rng.nextInt(setSize);
                                ++counter;
                                if (0 > counter) {
                                        --counter;
                                        System.out.println("Counter limit exceeded.");
                                        break;
                                }
                                if (0 == value) {
                                        ++charsCounter;
                                        if (wordSize == charsCounter) {
                                                break;
                                        }
                                } else {
                                        charsCounter = 0;
                                }
                        }
                        testsResults[n] = counter;
                        meanResult += counter;
                }
                meanResult /= testsNumber;
                double deviation = 0.0;
                for (n = 0; testsNumber > n; ++n) {
                        value = testsResults[n];
                        deviation += (meanResult - value) * (meanResult - value);
                }
                deviation /= (testsNumber - 1);
                deviation /= testsNumber;
                System.out.println("Mean value: " + meanResult);
                System.out.println("Deviation: " + Math.sqrt(deviation));
                //System.out.println(Arrays.toString(testsResults));
        }
}

Среднее значение получается 120 с высокой точностью и довольно стабильно из эксперимента в эксперимент. Ищется слово из 4-х нулей в алфавите из 3-х символов. Должно получиться $11110_3=3^4+3^3+3^2+3^1=120$.

Mean value: 119.814248
Deviation: 0.1166500302761449

Mean value: 120.014564
Deviation: 0.11694825507371227

Mean value: 119.889117
Deviation: 0.1169242645871219

Mean value: 119.9645
Deviation: 0.11683799403819259

Mean value: 120.000451
Deviation: 0.11686436540742849

-- 21.01.2018, 00:00 --

Dmitriy40 в сообщении #1286015 писал(а):

Так что веры такому тесту нет.

Не согласен. Тест подтвердил полученный результат.

Dmitriy40 в сообщении #1286015 писал(а):

стандартное отклонение $111\,751\,198{,}1$ (by Excel)- т.е. снова практически совпадают.

Dmitriy40 в сообщении #1286015 писал(а):

За 20 минут работы выполнено $3\,100$ попыток

Эту величину надо поделить на $\sqrt{3100}$ получится $2\,007\,111$. То есть ответ $\left( 112\pm 2 \right)\cdot 10^6$, что в пределах погрешности содержит теоретическое значение $111\,111\,110$.

-- 21.01.2018, 00:05 --

arseniiv в сообщении #1285986 писал(а):

Я-то в общем говорил, насчёт части:...
Дескать, не всё так плохо.

Ну так ведь я же говорю, что и в той книжке задача решается через производящие функции. Ладно, там хоть понятно решение, а в статье Соловьёва вообще зубодробительные суммы по переменному числу аргументов. Я не в зуб ногой, как он от одной формулы к другой переходит.

[Dmitriy40]

Не, ну если стандартное отклонение делить на количество опытов, то да, с возрастанием количества оно будет уменьшаться, вот для $5000$ опытов уже примерно $\pm1/\sqrt{5000}<\pm1{,}5\%$ (т.к. совпадает с хорошей точностью со средним).
Ну значит верить можно.

[B@R5uk]

Ну, это прописная истина, что статистическая погрешность падает как корень из размера статистики. Если это не так, то есть повод остановиться и ещё раз всё внимательно обдумать.

[Someone]

atlakatl, если не ошибаюсь, в Борланд Паскале (и в Дельфи) генератор псевдослучайных чисел имеет период $2^{31}$. Когда-то я и там, и там его работу просматривал отладчике в режиме ассемблера. К сожалению, дело было очень давно, и я уже не помню, что там происходило.
Если у Вас получаются интервалы в сотни миллионов шагов, то таким генератором пользоваться нельзя, потому что используемая часть псевдослучайной последовательности должна составлять очень малую часть её периода. Если у Вас Турбо Паскаль или Борланд Паскаль для DOS, можете попробовать взять генератор RandAs на сайте http://someoneltd.narod.ru/programs.htm и подключить модуль Rnd64Fnc. Рекомендую использовать функцию RandMM (для генерации десятичных цифр — RandMM(9)). Период этой функции не меньше $2^{48}$.
Если у Вас другой Паскаль, то ничего посоветовать не могу.

atlakatl в сообщении #1285978 писал(а):

Someone в сообщении #1285977 писал(а):

среднее квадратичное отклонение какое?

Специально не считал, по прикидкам 500 000 где-то.

Это эмпирическое значение? Слишком мало. Это, видимо, следствие слишком короткого периода генератора псевдослучайных чисел. А теоретическое значение среднего квадратичного отклонения не считали?

B@R5uk в сообщении #1286016 писал(а):

Среднее квадратичное отклонение в этом случае нет смысла считать, потому что получится характеристика самой случайной величины

Я как раз характеристику "самой случайной величины" и имел в виду, а не статистическую погрешность оценки среднего.

[--mS--]

Математическое ожидание числа испытаний до получения строки из $r$ нулей, если вероятность нуля равна $p$, есть

$$\dfrac{1-p^r}{(1-p)p^r}.$$

Вывод без производящих функций http://www.cyberforum.ru/statistics/thr ... ost5353431

[atlakatl]

--mS--
Как всё обыденно. Штурмовать неделю неприступную вершину и обнаружить на ней отару с пастухом.
Сравнил с экспериментом, всё сходится.
Так этот результат эквивалентен ответу стартовой задачи?

[--mS--]

Ну вообще-то ТС уже давно выписал решение, и даже для общего случая: post1285902.html#p1285902

[B@R5uk]

--mS-- в сообщении #1286055 писал(а):

Вывод без производящих функций

Спасибо! Потрясающе простой и красивый вывод! Жаль, конечно, что это не самый общий случай, но уже что-то.

Если сделать замену $p=1/k$, то формула преобразуется так:

$$N=\dfrac{1-p^m}{(1-p)p^m}=\dfrac{k(k^m-1)}{k-1}=k(k^{m-1}+k^{m-2}+\ldots+k^2+k+1)=11\ldots 1110_k$$

где в $k$-ичной записи $m$ единиц.

[--mS--]

atlakatl в сообщении #1286056 писал(а):

Так этот результат эквивалентен ответу стартовой задачи?

Нет, конечно. В исходной задаче ответ, как уже было отмечено на первой странице, зависит от самой строки, а не только от её длины. Это - ответ для строки, состоящей из одного и того же символа.

[atlakatl]

--mS-- в сообщении #1286074 писал(а):

Нет, конечно.

Вот это я так и не понял (по ссылке сходил). У нас совпало $n$ символов строки. Генерируем $(n+1)$-й. Какая разница, будет ли это "Ц" или всё тот же ноль? Вероятность обоих исходов $1/k$.

[B@R5uk]

atlakatl в сообщении #1286086 писал(а):

У нас совпало $n$ символов строки. Какая разница, будет ли это "Ц" или всё тот же ноль?

Зависит от того, встречается ли новый неудачный символ в уже совпавшей части строки, или же нет. Если да, то мы начнём поиск не с начала, а с середины.

Пример: мы ищем 010, уже сгенерировано 110. Если следующим выпадет 1, то мы продвинулись на один шаг вперёд, а если 0 — не продвинулись вперёд, но и не отступили назад. Допустим выпало 1, тогда последние символы 1101. Если сейчас выпадет 0, то удача, а если 1 — мы откатимся назад на 2, то есть начнём всё с начала.

Другой пример: мы ищем 001, уже сгенерировано 110. Если следующим выпадет 1, то мы отступим назад на 1 шаг, а если 0 — продвинемся вперёд на 1. Допустим выпало 0, тогда последние символы 1100. Если выпадет 1 — удача, а если выпадет 0, то мы не продвинемся вперёд, но и не отступим назад. Теперь всё что нужно — это дождаться первой единицы, а это будет в среднем за 2 новых символа.

Но на самом деле то, что поиск начинается с середины в случае предыдущей неудачи, — обманчивая иллюзия. В таких случаях среднее время ожидания искомой строки оказывается больше, чем у других строк той же длины, но без самоповторений.

-- 21.01.2018, 14:13 --

Вот, например, табличка для последовательностей орлов и решек, упорядоченная по возрастанию среднего числа символов:

Строка______Ожидание
О___________2
Р___________2
ОР__________4
РО__________4
ОО__________6
РР__________6
ООР_________8
РРО_________8
ОРР_________8
РОО_________8
ОРО_________10
РОР_________10
ООО_________14
РРР_________14
ОООР________16
РРРО________16
ООРР________16
РРОО________16
ОРРР________16
РООО________16
ООРО________18
РРОР________18
ОРОО________18
РОРР________18
ОРРО________18
РООР________18
ОРОР________20
РОРО________20
ОООО________30
РРРР________30