On coincidences of tuples in a binary tree with random labels of vertices. (English. Russian original) Zbl 1345.05092
Discrete Math. Appl. 26, No. 3, 145-153 (2016); translation from Diskretn. Mat. 27, No. 4, 38-48 (2015).
Summary: Let all vertices of a complete binary 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.
Software:
BinaryTreesReferences:
| [1] | Erhardsson T., “Stein’s method for Poisson and compound Poisson approximation”, An introduction to Stein’s method, eds. Barbour A.D., Chen L. H. Y., Singapore Univ. Press, 2005, 61-113.; Erhardsson, T.; Barbour, AD; Chen, LHY, “Stein’s method for Poisson and compound Poisson approximation”, An introduction to Stein’s method, 61-113 (2005) |
| [2] | Guibas L. J., Odlyzko A. M., “Long repetitive patterns in random sequences”, Z. Wahrscheinlichkeitstheorie verw. Geb., 53(1980), 241-262.; Guibas, LJ; Odlyzko, AM, “Long repetitive patterns in random sequences”, Z. Wahrscheinlichkeitstheorie verw. Geb, 53, 241-262 (1980) · Zbl 0424.60036 |
| [3] | Hoffmann C. M., O’Donnell M. J., “Pattern matching in trees”, J. ACM, 29:1 (1982), 68-95.; Hoffmann, CM; O’Donnell, MJ, “Pattern matching in trees”, J. ACM, 29, 1, 68-95 (1982) · 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.; Karlin, S.; Ost, F., “Counts of long aligned word matches among random letter sequences”, Adv. Appl. Probab, 19, 2, 293-351 (1987) · 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.; Karnin, ED, “The first repetition of a pattern in a symmetric Bernoulli sequence”, J. Appl. Prob, 20, 3, 413-418 (1983) · Zbl 0518.60017 |
| [6] | Rowland E. S., “Pattern avoidance in binary trees”, J. Comb. Theory, Ser. A, 117:6 (2010), 741-758.; Rowland, ES, “Pattern avoidance in binary trees”, J. Comb. Theory, Ser. A, 117, 6, 741-758 (2010) · Zbl 1221.05058 |
| [7] | Steyaert J.-M., Flajolet P., “Patterns and pattern-matching in trees: an analysis”, Inf. & Control, 58:1 (1983), 19-58.; Steyaert, J-M; Flajolet, P., “Patterns and pattern-matching in trees: an analysis”, Inf. & Control, 58, 1, 19-58 (1983) · 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.; Zubkov, AM; Mikhailov, VG, “Limit distributions of random variables associated with long duplications in a sequence of independent trials”, Theory Probab. Appl, 19, 1, 172-179 (1974) · 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.; Mikhailov, VG, “Estimate of the accuracy of the compound Poisson approximation for the distribution of the number of matching patterns”, Theory Probab. Appl, 46, 4, 667-675 (2002) · Zbl 1040.60007 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
