×

zbMATH — the first resource for mathematics

On coincidences of tuples in a \(q\)-ary tree with random labels of vertices. (English. Russian original) Zbl 1409.05057
Discrete Math. Appl. 28, No. 5, 293-307 (2018); translation from Diskretn. Mat. 30, No. 3, 48-67 (2018).
Summary: Let all vertices of a complete \(q\)-ary tree of finite height be independently and equiprobably labeled by the elements of some finite alphabet. We consider the numbers of pairs of identical tuples of labels on chains of subsequent vertices in the tree. Exact formulae for the expectations of these numbers are obtained, convergence to the compound Poisson distribution is proved. For the size of cluster composed by pairs of identically labeled chains we also obtain exact formula for the expectation.
MSC:
05C05 Trees
05C78 Graph labelling (graceful graphs, bandwidth, etc.)
Software:
BinaryTrees
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Erhardsson T. “Stein’s method for Poisson and compound Poisson approximation”, In Barbour A.D., Chen L.H.Y. (ed.) “An introduction to Stein’s method” Singapore Univ. Press 2005 61-113.
[2] Guibas L.J., Odlyzko A.M. “Long repetitive patterns in random sequences”, Z. Wahrscheinlichkeitstheorie verw. Geb.53 (1980), 241-262. · Zbl 0424.60036
[3] Hoffmann C.M., O’Donnell M.J. “Pattern matching in trees”, J. ACM, 29:1 (1982), 68-95. · Zbl 0477.68067
[4] Karlin S., Ost F. “Counts of long aligned word matches among random letter sequences”, Adv. Appl. Probab., 19:2 (1987) 293-351. · Zbl 0621.60074
[5] Karnin E.D. “The first repetition of a pattern in a symmetric Bernoulli sequence”, J. Appl. Prob., 20:3 (1983), 413-418. · Zbl 0518.60017
[6] Rowland E.S. “Pattern avoidance in binary trees”, arxiv: arXiv: 0809.0488. · Zbl 1221.05058
[7] Steyaert J.-M., Flajolet P. “Patterns and pattern-matching in trees: an analysis”, Inf. & Control, 58:1 (1983) 19-58. · Zbl 0567.68053
[8] Zubkov A. M., Mikhailov V. G. “Limit distributions of random variables associated with long duplications in a sequence of independent trials”, Theory Probab. Appl., 19:1 (1974), 172-179. · Zbl 0326.60024
[9] Mikhailov V. G. “Estimate of the accuracy of the compound Poisson approximation for the distribution of the number of matching patterns”, Theory Probab. Appl., 46:4 (2002), 667-675. · Zbl 1040.60007
[10] Mikhaylov V. G. “Estimates of accuracy of the Poisson approximation for the distribution of number of runs of long string repetitions in a Markov chain”, Discrete Math. Appl.,26:2 (2016), 105-113. · Zbl 1375.60116
[11] Mikhailov V. G. “On the probability of existence of substrings with the same structure in a random sequence”, Discrete Math. Appl.,27:6 (2017), 377-386. · Zbl 1397.60099
[12] Zubkov A. M., Kruglov V. I. “On coincidences of tuples in a binary tree with random labels of vertices”, Discrete Math. Appl.,26:3 (2016), 145-153. · Zbl 1345.05092
[13] Kruglov V., Zubkov A. “Number of pairs of template matchings in q-ary tree with randomly marked vertices”, In: Analytical and Computational Methods in Probability Theory, Lect. Notes Comput. Sci., 10684 2017, 336-346. · Zbl 1383.60032
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.