We study the number distribution for monotone strings of a length s in a sequence of n random independent variables uniformly distributed on the set {0,..., N - 1} where N is a constant. By means of the Stein method we construct an estimate of the variation distance between this distribution and a compound Poisson distribution. As a corollary of this result we prove the limit theorem as n, s ^ то for the number of monotone strings. The approximating distribution is the distribution of the sum of Poisson number of independent random variables with geometric distribution.
Download file
Counter downloads: 332
- Title Compound Poisson approximation of the number distribution for monotone strings of fixed length in a random sequence
- Headline Compound Poisson approximation of the number distribution for monotone strings of fixed length in a random sequence
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 2 (28)
- Date:
- DOI
Keywords
монотонные цепочки, оценка точности сложной пуассонов-ской аппроксимации, сложное пуассоновское распределение, метод Стейна, monotone strings, estimate of the variation distance of the compound Poisson approximation, compound Poisson distribution, Stein methodAuthors
References
Гончаров В. Л. Из области комбинаторики // Изв. АН СССР. Сер. матем. 1944. Т. 8. Вып. 1. С. 3-48.
Wolfowitz J. Asymptotics distribution of runs up and down // Ann. Math. Statist. 1944. V. 15. P. 163-172.
David F. N. and Barton D. E. Combinatorial Chance. N.Y.: Hafner Publishing Co., 1962.
Pittel B. G. Limiting behavior of a process of runs // Ann. Probab. 1981. V. 9. No. 1. P. 119-129.
Chryssaphinou O., Papastavridis S., and Vaggelatou E. Poisson approximation for the non-overlapping appearances of several words in Markov chains // Combinatorics, Probability and Computing. 2001. V. 10. No. 4. P. 293-308.
Меженная Н. М. Многомерная нормальная теорема для числа монотонных серий заданной длины в равновероятной случайной последовательности // Обозр. прикл. промышл. матем. 2007. Т. 14. Вып.3. С. 503-505.
Roos V. Stein's method for compound Poisson approximation: the local approach // Ann. Appl. Probab. 1994. V.4. No. 4. P. 1177-1187.
Bollobas B, Janson S, and Riordan O. Sparse random graphs with clustering // Random Structures and Algorithms. 2011. V.38. P. 269-323.
Compound Poisson approximation of the number distribution for monotone strings of fixed length in a random sequence | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2015. № 2 (28).
Download full-text version
Counter downloads: 1302