Доска Гальтона

[Aritaborian]

А я уже дарил.

[svv]

(Оффтоп)

Вот и как Вас не считать ответственным за все шероховатости Вольфрама, да чуть ли не представителем Wolfram Research на форуме. Я и считаю.

[Aritaborian]

(Оффтоп)

а) что за шероховатости-то? Чем конкретнее вы будете выражаться, тем больше шансы, что этих шероховатостей когда-нибудь не станет;
б) я далеко не единственный из форумчан, кто знает, любит и продвигает в массы технологии Вольфрама;
в) никогда не имел никаких деловых отношений с компанией Wolfram Research и являться её представителем на форуме dxdy никак не могу;
г) а вы... а вы... а вы тогда — душеприказчик Ритчи и представитель Страуструпа, вот вы кто ;-D

[svv]

(Оффтоп)

Не, я так, абстрактно. Знаете, как приятно: если что — есть ответственный человек. Хотя пару раз, действительно, получив от Вольфрама неудовлетворительный ответ, я Вас вспоминал.

Aritaborian в сообщении #1116680 писал(а):

никогда не имел никаких деловых отношений с компанией Wolfram Research и являться её представителем на форуме dxdy никак не могу;

Всё, моя интуиция равна нулю.
Страуструпа? Да. Потому что он на одной из фотографий на меня похож.

[Yu_K]

(Оффтоп)

https://www.youtube.com/watch?v=aGiKdJ2npc4

[arseniiv]

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

-- Идиоматический или не идиоматический хаскель без оптимизации
module Galton where

import Data.Array (Array, accumArray, elems, Ix, inRange)
import System.Random (RandomGen, newStdGen, random)
import Control.Monad.State (State, state, evalState)

histogram :: Ix i => (i, i) -> [i] -> Array i Int
histogram bounds bins = accumArray (+) 0 bounds [(x, 1) | x <- bins, inRange bounds x]

bernoulli :: RandomGen gen => Double -> State gen Int
bernoulli p =
  do x <- state random
     return $ if x < p then 1 else 0

binomial :: RandomGen gen => Int -> Double -> State gen Int
binomial count p =
  do ns <- sequence $ replicate count $ bernoulli p
     return $ sum ns

simulate :: RandomGen gen => gen -> Int -> State gen a -> [a]
simulate gen tries m = evalState (sequence $ replicate tries m) gen

test :: Double -> Int -> Int -> IO ()
test bias nails tries =
  do gen <- newStdGen
     let bins = simulate gen tries $ binomial nails bias
     let h = histogram (0, nails) bins
     print $ elems h

main :: IO ()
main = test 0.5 10 10000
 

-- Вт апр 19, 2016 23:13:49 --

Там надо прям сразу использовать вероятностную монаду вместо RandomGen gen => State gen, но не помню, в каком пакете её искать, а руками определять всё лень.

[Aritaborian]

(svv)

svv в сообщении #1116681 писал(а):

Не, я так, абстрактно.

Не отнекивайтесь, давайте конкретно ;-)

svv в сообщении #1116681 писал(а):

Знаете, как приятно: если что — есть ответственный человек.

Понимаю, о чём вы. Но если бы Wolfram Research решили завести своё представительство на dxdy, это было бы сделано более явным образом, уж поверьте моим словам. А я всего лишь фанат и апологет. Немножко волонтёр, но не наёмный работник. И немножко специалист, но не самый крутой из форумчан, это уж точно.

(arseniiv)

А Хаскель забавный. Забавнее, чем Питон, который я взялся изучать вот совсем недавно. Но не перескакивать же теперь с поезда на поезд; глупо было бы. Тем более, что какой-то он чересчур уж забавный и странноватый.

[arseniiv]

(Оффтоп)

Не буду говорить, что не старался написать страшнее, чем может быть. И ещё там кое-что можно улучшить.

State s a — это по сути (но в обычной реализации не ровно, есть причины) тип функций s -> (a, s), которые на основе старого состояния вычисляют новое и какой-то результат, а вычисление псевдослучайного числа как раз так выглядит — старое состояние генератора превращается в новое и результат. Для функций вида a -> State s b есть «композиция» как для обычных функций a -> b, но правильно передающая состояние. do-нотация имеет дело с удобным описанием таких композиций специального вида. Здесь всё пронесение состояние, в основном, упрятано в sequence :: Monad m => [m a] -> m [a], которая «выполняет» элементы переданного списка по очереди и складывает в новый список их результаты, так что можно было бы написать без do и, вероятно, яснее.

В конце там ещё do, относящееся к другой монаде, IO.

[vamoroz]

Уважаемые участники дискуссии.
Выражаю вам свою признательность за интерес к ней. Обращаю ваше внимание на саму доску Гальтона, на ее разновидности.
Широко известна доска Гальтона в виде «треугольника». Ссылку на видео с изображением треугольной доски, сделанной из конструктора «лего», дает Yu_K. Данное видео ничуть не хуже тех видео, что есть по данной теме в интернете. Совершенно непонятно почему данная ссылка объявлена «вне темы».
Участник Aritaborian дал ссылку на Вольфрамовский сайт с демонстрациями, где на данный момент лежат 6 демонстраций, которые сайт объединил по критерию «доска Гальтона». Если Aritaborian не будет возражать, то из 6-ти демонстраций, представленных на сайте, я выберу одну, наиболее типовую, которую можно найти по http://demonstrations.wolfram.com/IdealizedGaltonBoard/
Однако и здесь представлена треугольная доска Гальтона.
Значительно реже встречается доска Гальтона в виде «домика». Мне известно только одно изображение такой доски. Оно приведено на рисунке Гальтона 1889 года.
В настоящее время меня интересует доска Гальтона в виде домика.
Если треугольная доска Гальтона характеризуется одним параметром – числом накопителей-«карманов», куда попадают шарики в результате блуждания, вызванного прохождением через сетку «гвоздиков», то доска Гальтона в виде домика характеризуется еще одним показателем.
Александрович назвал его «высотой доски», arseniiv – «числом уровней на доске», svv –«число уровней гвоздиков». Попробую определить данный параметр и я. Как мне кажется, больше подходит определение «число рядов с гвоздиками».
Для удобства обозначим число карманов-накопителей за N, а число рядов с гвоздиками за K.
Известно, что при соотношении $K=N+1$ доска Гальтона дает биномиальное распределение.
Известно, что при $ K> N+1$ , распределение, полученное в результате падения шариков, будет отличаться от биномиального. На своем знаменитом рисунке (N=13, K=24) Гальтон пытался компенсировать данное отличие «сужением» области карманов-накопителей (изображение3).
Известно, что существует решение, что при $ K\to\infty$ распределение, полученное при падении шариков будет стремиться к равномерному. Если быть более точным, то при Гальтоновском числе карманов (N=13) , при $ K\to\infty$ вероятность попадания шарика в крайние карманы с номерами 1 и 13 будет примерно 0,05 , а вероятность попадания во все остальные карманы (с номерами от 2 до 12) составит что-то около 0,08.
Если это так, то алгоритмы svv и arseniiv легко подтвердят это. Однако, я прогнозирую, что ниже значения 0,11 для центрального, седьмого кармана, им не удастся опуститься. По моим прогнозам значение 0,11 в центральном кармане можно получить при K=42.
Уважаемые svv и arseniiv. Выражаю вам признательность за выложенный код. Думаю, что информация была бы более интересной, если бы вы дополнили свои алгоритмы небольшим расчетом.

[arseniiv]

Расчётом чего? Вы просили доску, вот вам модель доски.

[svv]

А Вы сами разве не программируете?

[vamoroz]

Еще раз выражаю признательность svv и arseniiv за выложенные алгоритмы.
Сожалею, что представленные алгоритмы не дополнены расчетами.
Считаю, что независимый расчет более объективно оценит моделируемый процесс.
Вынужден написать свой алгоритм, расчет по которому для случая
- количество карманов-накопителей 13
- количество рядов с гвоздиками 42
- количество падающих шаров 800
привожу в виде таблицы

$$\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline \text{вер. попадан.}& 1 & 2&3 &4 &5 &6 &7 &8 &9 &10 &11 &12 &13 \\ \hline \text{вер. попадан.}&0,03&0,05&0,06&0,08&0,1&0,12&0,12&0,11&0,11&0,09&0,07&0,06&0,02\\ \hline \end{tabular}$$

Для наглядности результат расчета представляю в виде графика.

На графике изображена статистика моделирования, ее полиномиальная аппроксимация и «равномерное» распределение, которое дает «теоретический расчет».
Еще раз обращаюсь к участникам svv и arseniiv.
В виду того, что они располагают аналогичными алгоритмами (по крайне мере, они сами заявили об этом), то определенный интерес составляет статистика, полученная на основе работы этих программ. Статистика может подтвердить или поставить под сомнение представленный результат. Поэтому, прогон их программ на близких исходных данных с публикацией результатов, поможет объективно принять решение по предельному распределению, которое можно получить с помощью доски Гальтона.

[svv]

Других алгоритмов у меня нет. А этот, как я предполагал, Вы при желании сами легко приспособите под Ваши задачи. (Я специально удостоверился, что Вы сами программируете.) Я его проверил в набросанной за пять минут программе, передал Вам, а у себя тут же стёр.

[arseniiv]

vamoroz в сообщении #1122730 писал(а):

В виду того, что они располагают аналогичными алгоритмами (по крайне мере, они сами заявили об этом), то определенный интерес составляет статистика, полученная на основе работы этих программ. Статистика может подтвердить или поставить под сомнение представленный результат. Поэтому, прогон их программ на близких исходных данных с публикацией результатов, поможет объективно принять решение по предельному распределению, которое можно получить с помощью доски Гальтона.

Зачем это делать, когда есть математическое доказательство? А именно, одна из теорем, носящих гордое имя центральной предельной. И для этого не понадобятся прогоны потенциально ошибочных программ на потенциально сбоящем железе.

[vamoroz]

Уважаемые svv и arseniiv.
Выражаю свою признательность за Ваши ответы.

Удивительная закономерность получается.
Два заслуженных участника по каким-то соображениям выкладывают свои алгоритмы и отказываются по ним считать.
Кроме того, результат, полученный третьей стороной, один из авторов выложенных программ объявляет ошибочным.
И это при полном отсутствии статистики по данной задаче.

Еще раз обращаю ваше внимание на разновидности досок Гальтона.
Широко известна доска Гальтона в виде «треугольника». Значительно реже встречается доска Гальтона в виде «домика».
Схематичные схемы обоих вариантов представлены на рисунке.



Доска Гальтна типа «треугольник» есть частный случай доски Гальтона «домик».
К доске Гальтона «треугльник» можно применить результаты центральной предельной теоремы, а к доске Гальтона типа «домик», - нельзя.
Рассматривается доска Гальтна типа «домик».
Известно, что с увеличением количества рядов с гвоздиками в «жилой части домика» биномиальное распределение, полученное благодаря гвоздикам «крыши» начинает трансформироваться.
Есть решение, что при достаточно большом количестве рядов с гвоздиками можно получить равномерное распределение.
Имитационное моделирование данного процесса опровергло это решение.
Предельное распределение шариков по накопителям на доске Гальтона типа «домик» при бескнечно большом количестве рядов с гвоздиками неравномерно.