2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3
 
 Re: Матожидание для случайной последовательности символов
Сообщение20.01.2018, 22:51 
Аватара пользователя


26/05/12
1534
приходит весна?
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 писал(а):
Я-то в общем говорил, насчёт части:...
Дескать, не всё так плохо.
Ну так ведь я же говорю, что и в той книжке задача решается через производящие функции. Ладно, там хоть понятно решение, а в статье Соловьёва вообще зубодробительные суммы по переменному числу аргументов. Я не в зуб ногой, как он от одной формулы к другой переходит.

 Профиль  
                  
 
 Re: Матожидание для случайной последовательности символов
Сообщение20.01.2018, 23:15 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Матожидание для случайной последовательности символов
Сообщение20.01.2018, 23:17 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Матожидание для случайной последовательности символов
Сообщение20.01.2018, 23:28 
Заслуженный участник
Аватара пользователя


23/07/05
17973
Москва
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 писал(а):
Среднее квадратичное отклонение в этом случае нет смысла считать, потому что получится характеристика самой случайной величины
Я как раз характеристику "самой случайной величины" и имел в виду, а не статистическую погрешность оценки среднего.

 Профиль  
                  
 
 Re: Матожидание для случайной последовательности символов
Сообщение21.01.2018, 06:08 
Заслуженный участник
Аватара пользователя


23/11/06
4171
Математическое ожидание числа испытаний до получения строки из $r$ нулей, если вероятность нуля равна $p$, есть
$$\dfrac{1-p^r}{(1-p)p^r}.$$
Вывод без производящих функций http://www.cyberforum.ru/statistics/thr ... ost5353431

 Профиль  
                  
 
 Re: Матожидание для случайной последовательности символов
Сообщение21.01.2018, 07:12 
Аватара пользователя


21/09/12

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

 Профиль  
                  
 
 Re: Матожидание для случайной последовательности символов
Сообщение21.01.2018, 07:21 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Матожидание для случайной последовательности символов
Сообщение21.01.2018, 10:34 
Аватара пользователя


26/05/12
1534
приходит весна?
--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$ единиц.

 Профиль  
                  
 
 Re: Матожидание для случайной последовательности символов
Сообщение21.01.2018, 10:51 
Заслуженный участник
Аватара пользователя


23/11/06
4171
atlakatl в сообщении #1286056 писал(а):
Так этот результат эквивалентен ответу стартовой задачи?

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

 Профиль  
                  
 
 Re: Матожидание для случайной последовательности символов
Сообщение21.01.2018, 12:35 
Аватара пользователя


21/09/12

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

 Профиль  
                  
 
 Re: Матожидание для случайной последовательности символов
Сообщение21.01.2018, 12:55 
Аватара пользователя


26/05/12
1534
приходит весна?
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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 41 ]  На страницу Пред.  1, 2, 3

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: Vladimir Pliassov


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group