{'fraction_non_alphanumeric': 0.043974550898203596, 'fraction_numerical': 0.016747754491017963, 'mean_word_length': 3.8964727439303712, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 6, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 6, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Azuma-Hoeffding bounds for a class of urn models

We obtain Azuma bounds for the probabilities of being away from the limit for a class of urn models. The method consists of relating the variables to certain linear combinations using eigenvectors of the replacement matrix, thus bringing in appropriate martingales. Some cases of repeated eigenvalues are also considered using Jordan vectors.


Introduction
Consider a two color urn model, with colors white and black, evolving as follows: at time 0 the color count is (W 0 , B 0 ) = C 0 , 0 ≤ W 0 , B 0 ≤ 1, W 0 + B 0 = 1. There is a 2 × 2 irreducible and stochastic replacement matrix R which drives the color count evolution as follows: given the color composition (W n , B n ) = C n at time n, we choose a color at random with probabilities proportional to W n /(n + 1), B n /(n + 1), respectively. If white is chosen we add the first row of R, or if black is chosen we add the second row of R, to C n to get C n+1 , the color count vector at time (n + 1). Denoting by χ n+1 a row vector which takes the value (1, 0) if white is chosen, or (0, 1) if black is chosen as above, we clearly have at the (n + 1)th stage C n+1 = C n + χ n+1 R. Since each row sum of R is one, the total color count in each step increases by 1, making the urn model balanced.Various eigenvalues and eigenvectors of R can be used to understand the limiting behavior of various linear combinations of W n and B n . The above model easily generalizes to urn models with more than two colors and we state some of the limit theorems (for these more general models with d colors) necessary for our notation and results.
The strong law states that Cn n+1 → π almost surely, where π is the left eigenvector to the Perron-Frobenius eigenvalue 1 of R (see Laruelle and Pages [9]). This π is also a probability vector with all components positive. Next, if we multiply the equation C n+1 = C n +χ n+1 R by a right eigenvector ξ to a non Perron-Frobenius eigenvalue λ (which necessarily satisfies |λ| < 1), then Rξ = λξ gives a reduction which has been used in central limit theorems. The scaling in these theorems depend on whether the real part of λ is 1/2 or not. See Smythe [12], Basak and Dasgupta [2], and the comprehensive paper Janson [7].
The above two results are clearly the analogues (for urn models) of the strong law of large numbers and the central limit theorem for the sum S n of i.i.d. random variables X i with mean µ and variance σ 2 . For sums of i.i.d. random variables, another class of very important reasults measure the probability of deviation P (| Sn n − µ| > ǫ) = P (|S n − nu| > ǫn). If these probabilities decrease fast (say like e −const.n ) then even for n not too large, S n /n is close to µ with high probability. In fact, under the assumption of finite exponential moments, in the theory of large deviation the limit lim 1 n log P (| Sn n − µ| > ǫ) is obtained. However in the general dependent set up such a limit is not easy to obtain (see however Grama and Haeusler [6], for an extension), and for the required random variables Y n /n with limit ν say, one sided bounds like P (|Y n − nν| > nǫ) ≤ e −const.f (n) where f (n) is an increasing function, serve the same useful purpose. One such bound is the Azuma inequality, also called Azuma-Hoeffding bound, see Ross [11], which assumes a martingale structure.
In the case of our urn models clearly the last problem reduces to finding bounds for P (|W n − (n + 1)π 1 | > (n + 1)t). Because of the dependence here, large deviation considerations have been approached in different ways in the literature. For an approach through generating functions see Flajolet, Dumas, Puyhaubert [4] and Morcrette [10]. Franchini [5] gives a functional form for a class of urn models, Bandyopadhyay and Thacker [1] consider deviations from the expected configuration over a class of probabilities which keep the expected configuration fixed and get rate log n. Even in a simple set up, it is not easy to understand the limit (or limsup and liminf) of − 1 n log P (C n /(n + 1) ∈ B), where C n is the urn composition at time n, and B is a set in R d where d is the number of colors. We thus focus on exponential upper bounds depending on the eigenvalues for the class of urn models described in the first paragraph. We now describe the organization of the article. In section 2 we consider a linear combination using the eigenvector ξ to the non Perron-Frobenius eigenvalue λ and show how deviations of W n can be related to deviations of a corresponding martingale. In section 3 the same is done for some multicolor urn models, however now there may be more than one distinct eigenvalues, or a repeated eigenvalue. We consider only the case when these eigenvalues are real and stress the systematic use of eigenvectors and Jordan vectors.
In view of this we represent C n .ξ as a sum of martingale differences and apply Azuma-Hoeffding inequality to get exponential bounds. In many practical applications such bounds suffice, since large deviation principle (LDP) under dependent set up is not easy. The exponential bounds are well known in the urn model literature for particular examples, also see the recent work of Kuba and Sulzbach [8] who also use martingale inequalities for Polya type urns, where we note that our irreducible R is different from the R of Polya's original urn models. Our approach is through a combination of linear algebra and martingale theory which tries to cover a family of urn models depending on the value of λ. Although the precise forms can be recovered from the proof that follows, the statement of next proposition stresses the increasing nature of f (n).
We first state the form of Azuma-Hoeffding inequality that we use.
The Azuma inequality is the following exponential inequality for the probability with similar statements for t < 0. Our martingale differences depend on both i and n, and handling this is the main part of the work.
where c is a constant greater than zero.
Proof: When λ = 0 the martingale doesn't move. Since Rξ = 0 we have C n+1 ξ = C n ξ, that is this linear combination equals C 0 ξ and the exponential inequality is satisfied for any c > 0.
In this case the two martingale differences corresponding to the two eigenvectors can be added and we can use the calculations of the previous proof as follows (of the two distinct ones, one zero eigenvalue contributes a constant 0-th term only): Theorem 3.1 For nonzero λ 2 , λ 3 ∈ (−1, 1) one can find increasing functions f (n) so that for positive t, where c is a constant greater than zero.
Proof: The combined martingale differences here give rise to the martingale difference As before these martingale differences are bounded by constant times which are bounded by constant times n λ 2 j λ 2 + n λ 3 j λ 3 . For the squares of these bounds we can use (a + b) 2 ≤ 2(a 2 + b 2 ) and repeat the previous proof starting analogously from inequality (3) with D n (λ 2 ) + D n (λ 3 ). ✷ Now suppose that R has one repeated real nonprincipal eigenvalue λ.
Using RP = P λ 1 0 λ where the columns of P are ξ 2 , ξ 3 respectively, we get Rξ 3 = ξ 2 + λξ 3 . Like the eigenvector ξ 2 , for the Jordan vector ξ 3 one again has C n ξ 3 /(n + 1) → 0. To see this note that with F n , the urn composition σ-field upto time n, E(C n+1 ξ 3 |F n ) = (1 + λ n+1 )C n ξ 3 + Cn n+1 ξ 2 . In this case following Dasgupta and Maulik [3] one can consider the martingale with Π n (λ) = n−1 j=0 (1 + λ j+1 ). The martingale differences of the above M n have variances like 1/n 2λ and Lemma 2.1 of Dasgupta and Maulik [3] with a n = n 1−λ shows C n ξ 3 /(n + 1) → 0 using C j ξ 2 /(j + 1) → 0. Martingales with other Jordan vectors can be handled in a similar manner successively. Hence as before, for C 1n − π 1 (n + 1), it is enough to consider a linear combination using the eigenvector ξ 2 and the Jordan vector ξ 3 . From the statements of the previous theorems and the proofs we see that identifying the 0-th term and the sum of the martingale differences for each linear combination is necessary. We first do this for the case of the repeated eigenvalue zero to bring out the different nature of C n+1 ξ 3 corresponding to the Jordan vector.
Next for the repeated eigenvalue λ = 0 we consider the 0-th term and the size of the martingale differences for C n+1 ξ 3 where ξ 3 is the Jordan vector, the case of the eigenvector ξ 2 having been worked out in Theorem 2.1 Proposition 3.2 For λ ∈ (−1, 1)\{0}, C n+1 ξ 3 when expanded in terms of martingale differences has a 0-th term which is o(n) and its sum of squares of bounds on martingale differences is bounded by constant times (1 + log n) 2 D n (λ).
Proof: We now have The first two terms of the last line are familiar from the proof of Theorem 2.1 (equation (2) with appropriate changes), and the new last term (1 + λ k + 1 ) using equation (2) and the notational convention in the line following it.
Finally, to get the required 0-th term for C n+1 ξ 3 , we collect 0-th terms of (4), and use the estimates from Theorem 2.1 and the previous paragraph. We also collect the martingale differences and use (a + b) 2 ≤ 2(a 2 + b 2 ) to get bounds on the sums of squares of the martingale difference bounds. ✷ The statement and proof of the Azuma-Hoeffding bound for α 2 C n+1 .ξ 2 + α 3 C n+1 .ξ 3 where ξ 2 , ξ 3 are the eigenvector and Jordan vector respectively to the repeated eigenvalue λ( = 0) is now similar to the statement of Theorem 3.1 with the appropriate changes brought in by Proposition 3.2. We omit the detailed formulas, which can be recovered as needed.
Remark: In cases with more colors, other Jordan vectors corresponding to the same real eigenvalue involve multiple iterated sums and are similar though more involved, and we have not pursued them in this short article. Also in the case of complex eigenvalues a possible approach is to take the real part of the right hand side of equation (2), we refer to Basak and Dasgupta [2], Dasgupta and Maulik [3], Janson [7] etc. and the references therein.

Concluding remarks
In strong or weak limit theorems for urn models it is usual to derive recursive equations for appropriately scaled C n+1 ξ, for example in law of large numbers the scaling is (n + 1), in central limit theorem the scaling is √ n or √ n log n etc. depending on the eigenvalue. For large deviations we have used recursive equations for C n+1 ξ itself along with the the Azuma inequality to derive Azuma-Hoeffding bounds, which are exponentially decreasing depending on the eigenvalues, for a class of urn models through linear combinations corresponding to the eigenvectors and Jordan vectors of the replacement matrix.