Компьютерно-аналитические методы решения вероятностных задач, возникающих при исследовании случайных точечных структур

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

УДК 004
Компьютерно-аналитические методы решения вероятностных задач, возникающих при исследовании случайных точечных структур*
А. Л. Резник, В. М. Ефимов, А. А. Соловьев, А.В. Торгов
Институт автоматики и электрометрии Сибирского отделения Российской академии наук (Новосибирск, Россия)
Computer Analytical Methods of Solving Probability Problems in Random Dot Patterns Research
A.L. Reznik, V.M. Efimov, A.A. Solovev, A.V. Torgov
Institute of Automation and Electrometry, Siberian Branch of the Russian Academy of Sciences (Novosibirsk, Russia)
Предложен оригинальный подход к решению весьма трудных и не имеющих на сегодня точного аналитического решения проблемных вероятностных задач, возникающих при считывании случайных точечных полей. Представлены схемы прямого, итеративного и комбинаторно-рекурсивного аналитического расчетов многомерных интегральных выражений, которыми описываются частные решения таких задач (эти решения в дальнейшем используются для нахождения общих замкнутых аналитических зависимостей). Огромный объем требующихся вычислений вынудил авторов полностью формализовать алгоритмы и перенести на ЭВМ всю тяжесть рутинных аналитических выкладок. Проведенные вычисления помогли установить (а впоследствии и доказать) целый ряд новых, ранее неизвестных вероятностных формул, характеризующих надежность считывания случайных точечных изображений, когда такое считывание проводится многоуровневыми интеграторами. Таким образом, удалось реализовать (что в научной практике случается чрезвычайно редко) идею, высказанную в свое время Дж. фон Нейманом: исследователь, встречаясь с трудной и не поддающейся решению проблемой, прибегает к компьютерным расчетам, которые «подсказывают» ему правильный ответ, а затем этот подсказанный ответ он строго доказывает. Еще одна важная особенность исследований состоит в том, что введено новое понятие «трехмерные обобщенные числа Каталана» и найден их явный вид, знание которого было эффективно использовано при решении задач, связанных с регистрацией и анализом случайных точечных изображений.
Ключевые слова: компьютерные аналитические вычисления, случайное точечное поле, многомерное интегрирование, трехмерные числа Каталана.
DOI 10. 14 258/izvasu (2015)1. 1−32
This paper proposes an original approach to solving complicated probability problems (there is no exact analytical solution) that arise in the reading of random point fields. The schemes of direct, iterative, and combinatorial recursive analytical calculation of multidimensional integral expression that describes the particular solutions of such problems (these solutions are used then to find the general closed analytic dependencies) are shown. A huge amount of required computations forced us to formalize all the algorithms and transfer routine analytical calculations to a computer. The calculations helped us to establish (and later prove) new set of previously unknown probabilistic formulas describing the reliability of reading random point images when such a reading is based on multilevel integrators. Thus, we were able to demonstrate the implementation of the idea proposed by John Von Neumann (extremely rare case in scientific practice): researcher meet difficult and unsolvable problem, use the computer to & quot-suggest"- him the right answer, then finds a rigorous proof. Another important feature of our study is that we introduced a new concept of & quot-three-dimensional generalized Catalan numbers& quot- and found their explicit form- this knowledge has been effectively used by us in solving problems related to the registration and analysis of random point images.
Key words: computer analytical calculations, random point field, multidimensional integration, three-dimensional Catalan numbers.
* Работа была поддержана Российским фондом фундаментальных исследований (проект № 13−01−361), Президиумом Российской академии наук (проект № 11/2012), Сибирским отделением Российской академии наук (проект сотрудничества СО РАН и НАН Беларуси № 16/2012).
Введение. Исследования по надежности считывания случайных точечных полей привели нас к следующей очень простой (в постановке) вероятностной задаче, имеющей непосредственное отношение к случайному разбиению интервала.
Пусть п точек хх, х2,…, хп случайно брошены на интервал (0,1), т. е. имеется п независимых испытаний случайной величины, равномерно распределенной на интервале (0,1). Требуется определить вероятность Рп, к (е) события, состоящего в том, что не найдется ни одного подынтервала с (0,1) длины е, содержащего более к точек.
Аналитическое решение этой одномерной задачи необходимо знать, в частности, при расчете вероятности безошибочного считывания точечных изображений, когда они формируются случайными пуас-соновскими потоками постоянной интенсивности, а считывание осуществляется интеграторами, обладающими к пороговыми уровнями. Кажущаяся простота этой задачи обманчива, а ее аналитическое решение известно [1−2] лишь для к = 1:
Рп1(е) = (1 — (п-1)е)п, (0 & lt- е & lt- 1/(п-1)). (1)
Следует заметить, что многие задачи, связанные со случайным разбиением интервала [3], просты в постановке, но их решение является серьезной научной проблемой. Один из путей достижения решения (1) заключается в представлении вероятности Рп! (е) в виде повторного интеграла
1 Рпд (е) = п! 2 & lt-х" хп- е 2 & lt-хп-1 ••• х^ -е 2 & lt-хъ х3- е 2 & lt-х2~
(п-1)е (п-2)е 2е е
2 ^[[[к)
Последовательное интегрирование соотношения (2) по переменным хь х2, …, хп приводит к равенству (1). Из приведенных соотношений следует, что процесс решения сформулированной выше вероятностной задачи для случая к = 1 весьма прост и компактен. К сожалению, для к & gt- 1 вероятность Рп, к (е) не может быть сведена к единственному повторному интегралу, в результате чего алгоритмические трудности, которые должны быть преодолены при ее нахождении, возрастают настолько, что по состоянию на сегодня ее полного аналитического решения нет даже для к = 2. В настоящей работе описываются возможные подходы к решению обсуждаемой проблемы.
Программно-аналитический расчет вероятностных формул. Вероятность Рпк (е) представляет собой многомерный интеграл
рп, к (е) = п!2.. 2dXl … <-хп
(3)
В, к (е)
по области интегрирования Бп, к (е) с Rn, описываемой системой линейных неравенств
0& lt-х1 & lt-х2 & lt-… <-хп-1 & lt-хп & lt-1, хк+1 — х1 & gt- е & gt- Хк+2 — х2 & gt- е & gt-
(4)
Интеграл (3) по области (4) может быть переписан в эквивалентной форме
Рп, к (е) = п! 2 & quot-'-2 1[х1 ]1[х2 М хп — хп-1 I1!1-хп 11[хк+1 — х1 — е]1[хк + 2 — х2 — е]. 1[хп — хп-к — е ]& lt-х1 & quot-А,, (5)

где сомножителями в подынтегральном выражении Затем п-мерный интеграл (5) с помощью цикличе-
выступают функции Хевисайда ского применения тождества
[0, ^ & lt- 0,
1, 2 & gt- 0.
1[ =
-=1
П1[хг — а, ] ПИ 3 — хг ] =ЕЕИхг — а, ]1[ !3{ - хг ]1[ 3 — а,
,=1 ?=1
преобразуется к набору повторных интегралов с уже расставленными пределами интегрирования (в тождестве (6) подразумевается, что выражения, а и Ь не содержат переменной хг).
Основная трудность практического использования приведенной процедуры состоит в том, что уже
Ш а, —
q=1
Пи з — з
5 = 1 5 ^
(6)
для п = 4 огромный объем вычислений, требующихся при расстановке пределов интегрирования, непосредственном интегрировании п-мерных повторных интегралов и проверке всех промежуточных систем неравенств на непротиворечивость, делает невозможным их проведение вручную. Поэтому нами был соз-
дан программный пакет, базирующийся на алгоритме (3)-(6) и осуществляющий все аналитические выкладки в автоматическом режиме [4].
В качестве еще одной альтернативы была предложена следующая процедура. По аналогии с известным решением (1), справедливым для k = 1, мы попытались найти общее решение Pn2 (s) для k = 2. В отличие от описанного выше алгоритма здесь была использована принципиально другая математическая техника, а именно: с помощью чисто комбинаторных средств был построен рекурсивный алгоритм, в котором формулы Pn2 (s) как функции непрерывного аргумента s достигаются из дискретно-комбинаторной схемы посредством предельного перехода. При этом на каждом последующем вычислительном этапе использовались как полученные на предыдущих этапах новые результаты, так и классические комбинаторные соотношения [5].
И, наконец, третий программный пакет основан на многократном циклическом дифференцировании исходного интеграла (3) по параметру s с дальнейшей реконструкцией вероятностных формул Pn, k (s) по зна-
d (j) P (e)
чениям производных (-, (j = 0, 1, …, n) в нуле
(т.е. при s = 0). Главное достоинство этого алгоритма заключается в том, что его применение позволяет заменить трудоемкие процедуры нахождения пределов интегрирования и последовательного многомерного интегрирования на элементарные операции подстановки и замены переменных. В данном случае это возможно благодаря применению очевидных равенств
,? d 1[z] = S (z), f 6(z)F (z)dz = F (0),
— ?
которые были использованы при расчете интегралов вида (5) (здесь 5(z) — дельта-функция Дирака). Применение этого алгоритма имеет и определенные ограничения, поскольку он эффективно вычисляет формулы Pn, k (s) только в одном диапазоне изменения параметра s, примыкающем к точке s = 0.
Используя три вышеупомянутые программные системы, мы рассчитали формулы Pn, k (s) для конкретных значений целочисленных переменных n и k (k & lt- n) вплоть до n = 14 во всех диапазонах изменения непрерывного параметра s. В дальнейшем эти компьютерные аналитические расчеты помогли нам сначала установить, а затем и строго доказать новые, ранее неизвестные вероятностные закономерности, относящиеся к случайному разбиению интервала.
Использование чисел Каталана для доказательства «компьютерных» формул. Анализ рассчитанных на компьютере формул Pn, k (s) позволил определить новые, ранее неизвестные общие аналитические зависимости. В частности, для четных зна-
чений n = m и k = 2 нам удалось установить формулу
P2m, 2(e) = -CZ1 (1 — (m — 1) e)2™, (7)
m
которая справедлива в диапазоне 1/m& lt- s & lt- 1/(m-1). Коэффициенты (1 / m) C2m1 в соотношении (7) являются классическими числами Каталана, известными еще по работам Леонарда Эйлера, интерес к которым сохраняется до наших дней (см., например, [6−8]), поскольку они лежат в основании перечислительной комбинаторики [9]. Любопытно отметить, что соотношение (7) было «подсказано» компьютером и опубликовано в качестве научной гипотезы более 30 лет назад [10], а строгое математическое доказательство этой формулы было получено относительно недавно [11−12]. Таким образом, мы реализовали на практике совет Дж. фон Неймана: если вы не можете найти прямое решение трудной научной проблемы, попытайтесь выполнить трудоемкие вспомогательные выкладки программно. Если вам повезет, то эти вспомогательные компьютерные вычисления «подскажут» вам правильный ответ, который вы впоследствии строго обоснуете.
Недавно нам удалось доказать [13], что вероятность Pn, k (s) для k = 2 при нечетных значениях n = 2m + 1 в диапазоне 1/(m+1) & lt- s & lt- 1/m представляется в виде
Pm+u (e) = C2m+1 (1 — me) m21 (1 — (m — 1) e) m — -2 C2mm++21 (1 — me) m+2 (1 — (m — 1) e)m-1 + +C2mm++31 (1 — me) m+3 (1 — (m — 1) e)m-2.
(8)
Оказалось, что найти и математически обосновать соотношение (8) много труднее, чем доказать формулу (7). Так, один из этапов этого доказательства потребовал введения нового понятия «трехмерные обобщенные числа Каталана» и определения их явной формы. В наших исследованиях эти числа возникли, когда мы столкнулись с необходимостью отыскания общего числа специальных перестановок элементов трех подмножеств, каждое из которых представляло собой ранжированную последовательность одинаково распределенных случайных величин.
Если оставить в стороне исследования, связанные со случайным разбиением интервала, то задача, которая привела нас к трехмерным числам Каталана, допускает следующую наиболее прозрачную постановку.
Необходимо найти точное число Ql? m?n различных слов длины 1+т+п, которые могут быть образованы из I символов «а», т символов «Ь» и п символов «с» при одновременном соблюдении двух условий: 1) при просмотре слова слева направо количество встреченных символов «Ь» никогда не превышает количества
встреченных символов «а" — 2) при просмотре слова справа налево количество встреченных символов «с» никогда не превышает количества встреченных символов «а». Естественно, должно быть выполнено ограничение т, п & lt- I (в решавшихся нами задачах со
случайным разбиением интервала выполнялось более строгое условие: т + п & lt- I).
Сведя эту задачу с трехсимвольными словами к геометрической проблеме поиска путей на трехмерной дискретной решетке, нам удалось показать, что
01, т, п
(I + т + п)! (I + т + п)!
(I + т + п)!
(I + т + п)!
I! т!п!
(1 + т + п)! (I-X —
I! т! п!
(1 + 1)!(т — 1)!п! (1 + 1)!т!(п-1)! (1 + 2)!(т-1)!(п-1)! -1)(1 + 2) — (т + п)(1 + 2) + тп
(9)
(1 +1)(I + 2)
Детальное доказательство этого равенства может быть найдено в [14]. Здесь же мы коротко опишем лишь основную суть алгоритма.
Итак, рассматриваются различные пути на трехмерной дискретной решетке в координатной системе (X Y, Т), которые ведут из точки (0, 0, 0) в точку (I, т, п). Каждому слову ставится в соответствие один из этих путей. Символу «а» соответствует движение из текущей точки (i, j, к) в соседнюю точку (/'-+1, j, к) — символ «Ь» указывает на движение в точку (/, 1, к), а символ «с» означает движение в точку (/, j, к+1). Требуется найти общее количество таких путей из точки (0, 0, 0) в точку (I, т, п), которые не пересекают ни плоскости Рх, определяемой уравнением X-У = 0 (т.е. все учитываемые пути лежат в полупространстве X & gt- У), ни плоскости Р2, определяемой уравнением X — Т + п — I = 0. Таким образом, каждый из путей, удовлетворяющих обоим условиям, лежит не только в полупространстве X & gt- У, но также в полупространстве I — X & gt- п — Т.
Эта переформулированная задача решается следующим образом. Из общего числа путей = (1+т+п)!/ (1!т!п!), ведущих из точки (0, 0, 0) в точку (I, т, п), нужно вычесть количество путей Q, пересекающих, по крайней мере одну из плоскостей Рх или Р2. В свою очередь для вычисления Q мы должны просуммировать количество Q1 различных путей, пересекающих плоскость Р1, и количество Q2 путей, пересекающих плоскость Р2, а затем отнять из результата число Q12 путей, пересекающих обе плоскости Рх и Р2 (поскольку они учтены в сумме Q два раза).
Мы показали [14], что
Ql =
(I + т + п)!
Q2 =-
(I + т + п)!
(I + 1)!(т — 1)!п! — (1 +1)!т!(п — 1)!-
О = (1 + т + п)! °12 = (1 + 2)!(т — 1)!(п — 1)! Следовательно,
О-тп = 5 — - Q2 + Ql2 =
(I + т + п)! (I + т + п)!
(I + т + п)!
I! т! п!
(I + т + п)! (I + т + п)!
(1 + 2)!(т — 1)!(п — 1)!
I! т! п!
1 --
(1 + 1)!(т — 1)!п! (1 +1)! т!(п — 1)! т + п тп
I +1 (1 +1)(1 + 2)
Таким образом, доказательство равенства (9) завершено. Напомним, что справедливость этой формулы доказывалась нами при условии т + п & lt- I, которое всегда выполнялось в рамках решавшихся нами задач, относящихся к исследованию случайных точеч-
ных полей. Если же условие т + п & lt- I не выполняется (но, естественно, соблюдается условие т, п & lt- /), то решение сформулированной задачи о количестве Q^m?n специальных трехсимвольных слов в общем виде запишется следующим образом:
О, =
(I + т + п)! (I + т + п)!
I! т!п! (I-(I + т + п)!
(I + т + п)!
(т + п — I — 2)!(1 +1)!(1 +1)! (т + п — I — 2)!1 !(1 + 2)!
(I + т + п)!
— 1)!(т — 1)!п! (1 + 1)!т!(п — 1)! (I + т + п)!
(1 + 2)!(т — 1)!(п — 1)!
(10)
Мы назвали числа Q?? m?n «трехмерными обобщенными числами Каталана», имея в виду то, что эти числа расширяют традиционную последовательность Каталана, известную по многим приложениям (см., например, [15−16]) и получающуюся из равенства (10) при п = 0 и I = т. Соотношение (10) полезно не толь-
ко при решении прикладных вероятностных и статистических задач, но и имеет самостоятельный теоретический интерес.
Заключение. Для нахождения точных аналитических решений проблемных вероятностных задач, возникающих при исследовании надежности считывания
случайных точечных полей, предложено и реализовано несколько программных систем, выполняющих трудоемкие аналитические выкладки. С помощью разработанного программного обеспечения был рассчитан широкий набор частных «компьютерных» решений, последующий анализ которых позволил установить (а позже и строго доказать) ряд новых, ранее неизвестных аналитических соотношений. Знание этих точных аналитических зависимостей оказывается полезным при решении многих задач, относящихся к случайному разбиению интервала.
Еще одной отличительной чертой представленной работы является то, что успешность проведенных в ней исследований в значительной мере обеспечена введением нового понятия «трехмерные обобщенные числа Каталана». Нам удалось найти простую и прозрачную интерпретацию этого естественного расширения классической последовательности Каталана, при котором обобщенные числа Каталана предстают как решение «комбинаторно-лингвистической» задачи со специальными трехсим-вольными словами.
Библиографический список
1. Parzen E. Modern Probability Theory and Its Applications. John Wiley and Sons Inc. — New-York — London, 1960.
2. Wilks S.S. Mathematical Statistics. J. Wiley and Sons. -New-York — London, 1962.
3. David H.A., Nagaraja H.N. Order Statistics. John Wiley. — New-York, 2003.
4. Reznik A.L., Efimov V.M. Analytical Computer Calculations in Analysis of Discrete-Point Images // Pattern Recognition and Image Analysis. — 2003. — Vol. 10 (1).
5. Feller W. An introduction to probability theory and its applications. Vol. 1, 3rd ed. — New-York, 1968.
6. Stanimirovic S., Stanimirovic P., Ilic A. Ballot matrix as Catalan matrix power and related identities // Discrete Applied Mathematics. — 2012. — Vol. 160 (3).
7. Koc C., Guloglu I., Esin S. Generalized Catalan numbers, sequences and polynomials // Turk J. Math. — 2010. — Vol. 34.
8. Chamberland M., French C. Generalized Catalan Numbers and Generalized Hankel Transformations // Journal of Integer Sequences. — 2007. — Vol. 10.
9. Stanley R.P. Enumerative Combinatorics. Vol. 2. Cambridge Studies in Advanced Mathematics 62. — Cambridge, 1999.
10. Reznik A.L. Computer modeling of continuous readout of random discrete-structural images // Avtometriya. — 1981. -Vol. 6.
11. Reznik A.L., Efimov V.M., Solov'-ev A.A. Computer-analytical calculation of the probability characteristics of readout of random point images // Avtometriya. — 2011. — Vol. 47 (1).
12. Reznik A.L., Efimov V.M., Torgov A.V., Solov'-ev A.A. Analytical Computer Calculations in Problems with Random Division of an Interval // Pattern Recognition and Image Analysis. Advances in Mathematical Theory and Applications. -2012. — Vol. 22 (2).
13. Reznik A.L., Efimov V.E., Solov'-ev A.A., Torgov A.A. Errorless Readout of Random Discrete-Point Fields // Avtometriya. — 2012. — Vol. 48 (5).
14. Reznik A.L., Efimov V.E., Solov'-ev A.A., Torgov A.V. Generalized Catalan Numbers in Problems of Processing of Random Discrete // Images Avtometriya. — 2011. — Vol. 47 (6).
15. Gardner M. Mathematical Games, Catalan numbers: an integer sequence that materializes in unexpected places // Scientific American. — 1976.
16. Hilton P., Pedersen J. Catalan numbers, their generalization, and their uses. Math. Int. — 1991. — Vol. 13.

ПоказатьСвернуть
Заполнить форму текущей работой