{'fraction_non_alphanumeric': 0.06377121884080135, 'fraction_numerical': 0.025539073252790947, 'mean_word_length': 3.7295081967213113, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 21, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
On the extendibility of partially and Markov exchangeable binary sequences

In [Fortini et al., Stoch. Proc. Appl. 100 (2002), 147--165] it is demonstrated that a recurrent Markov exchangeable process in the sense of Diaconis and Freedman is essentially a partially exchangeable process in the sense of de Finetti. In case of finite sequences there is not such an equivalence. We analyze both finite partially exchangeable and finite Markov exchangeable binary sequences and formulate necessary and sufficient conditions for extendibility in both cases.


Introduction
A finite sequence of r.v.s (X 1 , . . . , X n ) defined on a common probability space is said exchangeable (sometimes n-exchangeable) if its joint distribution is invariant under permutations of its components. The sequence may or may not be the initial segment of a longer exchangeable sequence, i.e., as is said, it may or may not be "extendible", and is said ∞-extendible, if it is the initial segment of an infinite exchangeable sequence.
de Finetti characterized all the n-exchangeable sequences of r.v.s taking values in a finite space I, disregarding their extendibility, as unique mixtures of certain n-exchangeable, not extendible distributions, namely the hypergeometric processes. From this result, he has been able to demonstrate his representation theorem for exchangeable infinite sequences by a passage to the limit, and in [5] derived necessary and sufficient conditions for extendibility of {0, 1}-valued finite sequences in a geometric approach (see also [7], [10], [2] and [23]).
Under partial exchangeability, introduced in [3] (pp. 193-205 of [17]), (X 1 ,. . .,X n ) is divided into groups or subsequences (e.g. women and men) accordingly to a characteristic we consider relevant (e.g. each unit's sex), and we retain exchangeability to hold just for variables within the same subsequence. Again, we can represent every finite partially exchangeable sequence as a mixture of not extendible, partially exchangeable sequences, and an analogous representation theorem holds if all the exchangeable subsequences forming it are ∞-extendible. de Finetti in [4] (pp. 147-227 of [6]), suggested to consider in a sequence of observations the last observation preceding the present one as a relevant characteristic to define a an interesting case of partial exchangeability. Consider a finite state space I; call the variables immediately subsequent any occurrence of i ∈ I the successors of i. Then the subsequences forming the partially exchangeable sequence are those constituted of the successors of each state in I. He apparently suggested the possibility to characterize, by the usual passage to the limit, the mixtures of Markov Chains processes as partially exchangeable processes of that kind.
Diaconis and Freedman in [9] demonstrated that the limit argument does not hold for mixtures of transient Markov Chains. They dropped the intuitive idea of "relevant characteristics", introduce a different notion of partial exchangeability in terms of sufficient statistics (we will call this case Markov exchangeability) and characterized the mixtures of Markov Chains under the additional assumption of recurrence of the process. In [13] it is demonstrated that the two definitions (that in terms of subsequences and that in terms of sufficient statistics) coincide in case of recurrent processes. But they differ in case of finite sequences.
We will focus on partial exchangeability in the sense of de Finetti and Markov exchangeability for finite sequences of {0, 1}-valued variables, and on the respective notions of extendibility. Some necessary conditions for the extendibility of a partially exchangeable finite sequence have been studied in [21] and in [20]. Finite Markov exchangeable sequences have been analyzed in [24,25], but, as far as I know, no criterion for extendibility in the Markov exchangeable case has been given. In Section 2 we define a general framework in order to analyze this topic. In Sections 3 we analyze the partially exchangeable case. In particular we present two bijective transformations of the probabilities defining a binary partially exchangeable distribution (i.e. two alternative parameterizations). The first, introduced by de Finetti, allows us to establish necessary and sufficient conditions for extendibility developing the geometric approach presented in [5], [7] and [2] for the simply exchangeable case. The second parameterization, in terms of generalized covariances, allows us to derive some simpler necessary conditions related to the central moments of the mixing distributions. In Section 4 we formulate analogous results for Markov exchangeable distributions.

A general setting
A sequence partially exchangeable in the sense of de Finetti is essentially a set of distinct exchangeable subsequences. The concept of partial exchangeability has been extended in various way, relating to ergodic theory and extreme points representation of a convex set, (see [14], [12], [11], [1, chap. 12]). In our case of discrete time processes taking values in a finite state space, we will refer to a simple formalization in terms of sufficient statistics borrowed from [8], (see also [24]). With this formalization, we can represent also simple exchangeability and partial exchangeability in the sense of de Finetti.
Let (Ω, F , P ) be the probability space on which all the r.v.s in the sequel will be defined. Consider a sequence of n r.v.s (X 1 , . . . , X n ) each taking values in a finite set I. Consider a statistic T from I n into a finite set {t 1 , . . . , t z }. We call the sequence, as well as its joint distribution, n-partially exchangeable with respect to T if: That is, T induces a partition of I n into z equivalence classes and P attributes the same probability to the elements within the same class. So we can say that T is a minimal sufficient statistic for (X 1 , . . . , X n ) under P . Denote with [t i ] the set {x ∈ I n : T (x) = t i }; denote P (x ∈ [t i ]) as w ti , and the probability of any specified sequence in | denotes the cardinality of the set [t i ], and the distribution of (X 1 , . . . , X n ) is completely defined by the z probabilities (w t1 , . . . , w tz ) subjected to z i=1 w ti = 1. On the converse, any set of nonnegative values (w t1 , . . . , w tz ) having sum 1, defines a sequence n-partially exchangeable w.r.t.
T . Consequently the space the conditional probability distribution on I n given T , assessing equal masses to all the sequences in the equivalence class [t i ] and mass 0 to the other sequences: Then the following stated in [8] is plain: . The set of all the distributions over I n partially exchangeable w.r.t.
T is a simplex whose vertices are the extremal distributions h [ti] , i = 1, . . . , z, and each partially exchangeable distribution is a unique mixture of those extremal distributions with mixing weights w t1 , . . . , w tz .
The extremal distributions can be conceived as urn processes without replacement, and, depending on the properties of T , de Finetti's style theorems may be deduced by the convergence of the hypergeometric processes to the i.i.d. processes.

Generalized covariances
We introduce a generalization of the usual concept of covariance defined as follows: the covariance of order k among the variables X 1 , . . . , X k is Under DFPE, these covariances depends only on the number of variables involved for each exchangeable subsequence. To simplify the notation, denote the value w k1,...,kg when k i = 1 and all other subscripts are zero as and the relation with the previous parameterization is Proof of (10): For the sake of simplicity, but without loss of generality, set g=2. By expanding the product, results as the sum of (k 1 + 1)(k 2 + 1) terms of the kind where the first sum ranges over all the possible i-tuples (h 1 , . . . , h i ) of distinct labels in {1, . . . , n 1 } and consists of k1 i terms, the second of k2 j terms. Passing to the expectation, by (5), the term (11) results as k1 One can prove that the inverse map, which is somewhat similar to the inverse of a binomial transform, is where Cov 0,...,0 = 1 and all the covariances having a single 1 and all zeros in the subscript are zero. So, a (n 1 , . . . , n g )-DFPE binary sequence is completely defined by the g probabilities w(1), . . . , w(g) together with the generalized covariances {Cov k1,...,kg } defined for every g-tuple (k 1 , . . . , k g ) with k i ≤ n i and such that The space of the Cov k1,...,kg is implicitly defined by Λ n1,...,ng and (10) and is not easily described. We can say that all the Cov k1,...,kg can be both positive or negative, and by (12) are all null if, and only if, X 1 , . . . , X n are i.i.d.

Extendibility
For the sake of simplicity in this section we set g = 2, but all the results hold for a general g.
For what we have said, we can represent any (n 1 , n 2 )-DFPE distribution as a point in the linear spaces ♦ (n1+1)(n2+1) and Λ n1,n2 . Formulas (7) and (6) define the linear maps between the two spaces. Clearly these maps are one-one and onto and establish affine congruence of the two sets. The (n 1 + 1)(n 2 + 1) vertices of ♦ (n1+1)(n2+1) are the points having one coordinate equal to one and the others equal to zero and represent the extremal distributions of Theorem 2.1. (6) maps this vertices onto the vertices of Λ n1,n2 . In particular, the extremal distribution having w , are affinely independent, then Λ n1,n2 , which is their convex hull, is a (n 1 + 1)(n 2 + 1) − 1 dimensional convex polytope with (n 1 + 1)(n 2 + 1) vertices, i.e. a non-standard simplex.
We say that a (n 1 , it is the initial segment of a (r 1 , r 2 )-DFPE sequence. So the sequence, represented in Λ r1,r2 such that its orthogonal projection over the the projection of Λ r1,r2 over the coordinates of Λ n1,n2 , and as λ (n1,n2) k1,k2; r1,r2 the analogous projection of λ k1,k2; r1,r2 . Then Λ is exactly the subspace of Λ n1,n2 representing the (n 1 , n 2 )-DFPE distributions which are at least (r 1 , r 2 )-extendible and it results as the convex . Moreover, we are going to see that none of this point is redundant with respect to the convex hull problem, that is they are exactly the vertices of Λ (n1,n2) r1,r2 .
The points in Λ we can use the following linear program: where z ∈ R (n1+1)(n2+1) and z 0 ∈ R. The last inequality is artificially added so that So, the probabilities w k1,...,kg are the ordinary mixed moments of the mixing measure Formulas (10) and (12) link the ordinary mixed moments and the central mixed moments of a multivariate distribution (see e.g. [19], equations (34.28) (34.29)), consequently we have: So, a simple necessary condition for a representation of the kind (17) to hold is Cov 2k1,...,2kg ≥ 0 ∀ k i = 1, . . . , ⌊n i /2⌋, i = 1, . . . , g To simplify the notation, denote as Cov(i, j) the covariance between a r.v. of the i-th group and one of the j-th group, i.e. the value Cov k1,...,kg when k i = k j = 1 and all other subscripts are 0. Another simple necessary condition for (17) to hold is that, in that case, for what we have said, Cov(i, j) 1≤i≤g 1≤j≤g is the Variance-Covariance matrix of Θ and hence must be nonnegative definite.

Markov exchangeability
Consider an I-valued sequence (x 1 , . . . , x n ). Define its transition counts n i,j for all i, j in I as and arrange them in a matrix N = {n i,j } i,j . Then, the distribution of (X 1 , . . . , X n ) is Markov exchangeable (hereafter ME or n-ME if we need to highlight the number of variables) when the sufficient statistic T in (1) while it is x 1 = x n if, and only if Moreover, an integer valued matrix N = {n i,j } i,j is a consistent transition count matrix if, and only if, it is irreducible and one between (19) and (20) The cardinality of [x 1 , N ] was first found by Whittle in [22]. Define the matrix B = By (19) and (20), if we know the starting state and the transition counts of a sequence, we also know its ending state.

Theorem 4.1 ([22]). The number of sequences in
where x n is uniquely determined by x 1 and N , and where B xn,xn is the matrix obtained by B removing the x n -th row and the x n -th column.
We say that an I-valued process X = {X n } n∈N is ME if (X 1 , . . . , X n ) is ME for every n. In [9] it is demonstrated that a recurrent process (X 1 = X n i.o.) is ME if, and only if, its law is a mixture of Markov Chains. That is, let P be the space of all the stochastic matrices Θ = {θ i,j } i,j on I × I. Then there exists, and is unique, a mixing measure ν on the Borel sets of I × P such that Let Γ i (k) be the step of the process X at which the state i occurs for the k-th time. Let but Lemma 5 in [13] assures that a recurrent ME process is strongly recurrent, then all the states are recurrent and the two characterizations coincide.
Zaman in [24,25] We can consider separately the sequences depending on the initial state. From now on, we fix P (X 1 = 0) = 1 and hence we will consider only the sequences starting with 0 and the probabilities {w 0,N } N ∈Φ(0,n) , and {p 0,N } N ∈Φ(0,n) . We will also use the self-explaining notation p 0 n 0,0 n 0,1 n 1,0 n 1,1 and w 0 n 0,0 n 0,1 n 1,0 n 1,1 when we need to display the number of transitions.
Unlike the DFPE case, the number of probabilities defining an n-ME distribution is not so evident. We have to count the possible different transition count matrices for each fixed starting state. From (19) and (20) two cases are possible when X 1 = 0, and we define  if N ∈ Φ 2 (0, n) (23) The first k steps (X 1 , . . . , X k ), k < n, of an n-ME sequence are k-ME, and we can obtain all the probabilities {p 0,K } K∈Φ(0,k) from the {p 0,N } N ∈Φ(0,n) . Let K = k 0,0 k 0,1 k 1,0 k 1,1 be the transition count matrix up to step k of a sequence starting in 0, and let k 0,0 + k 0,1 = k + 0 and k 1,0 + k 1,1 = k + 1 . Then Theorem 4.3.
where the sums should be restricted over those matrices N in Φ(0, n) having n i,j ≥ k i,j , for all i, j in {0, 1}. Consider the probability p 0 ( a 1 0 b ) of having the sequence of a + b + 2 steps starting in 0 with a transitions (0, 0), a single transition (0, 1) and ending with b transitions (1, 1), and denote it w 0,a,b . By the above theorem we have We set w 0,n−1,0 = p 0 n−1 0 0 0 . Define the operators ∆ 0 and ∆ 1 such that: and ∆ 1 (w 0,a,b ) = w 0,a,b+1 − w 0,a,b Then we have In an n-ME sequence the probabilities {w 0,a,b } are well defined for every couple of nonnegative integers (a, b) having sum not greater than n − 2, together with the case w 0,n−1,0 . Denote as L n the set of couples (a, b) such defined together with the couple (n − 1, 0). Theorem 4.4 assures that the probabilities {w 0,a,b } Ln suffice to completely define an n-ME sequence starting in 0. It is easily seen that |L n | = n 2 + 1 as we would expect.

Extendibility
Unlike the DFPE case, in a ME sequence it is meaningless to consider separately the extendibility of the two subsequences {V 0 (k)} k and {V 1 (k)} k . Then we say that an n-ME sequence (X 1 , . . . , X n ) is r-extendible if there exist (X n+1 , . . . , X r ) such that (X 1 , . . . , X r ) is r-ME.
The probabilities w 0,a,b allow us to study the extendibility of a ME sequence in a geometric approach analogous to that of Section 3.2.
The space of the probabilities {w 0,a,b } Ln of all the n-ME sequences starting in 0 (call it Γ n ) is implicitly defined by Theorem 4.4. That is, we have that every w 0,a,b should satisfy and we can write R } R∈Φ(0,r) . By (21), (22), (23), (24), and with passages similar to those of the proof of Theorem 3.1 one can prove the following is valid for any r > n: γ (n) R = γ (n) r 0,0 r 0,1 r 1,0 r 1,1 = r 0,1 r + 0 γ (n) r 0,0 r 0,1 r 1,0 −1 r 1,1 + r 0,0 r + 0 γ (n) r 0,0 −1 r 0,1 As a consequence, Γ r } r is a nested sequence of convex polytopes. To verify whether a point representing a distribution lies inside a certain polytope, and establish its extendibility, we can use a linear program analogous to (16).
We have computationally calculated the volume of some of the polytopes Γ (n) r . We consider the ratio of the volume of Γ (n) r to the volume of Γ n as an index of the proportion of n-ME distribution that are r-extendible, as has been done in [2] and [23] for the exchangeable case, and we report some values in Table 1. By (26) one can see that, unlike the DFPE case, not all the points γ  Table 1 we start with n = 4.  r ) / V ol(Γ n ) for different values of n and r. The entries relative to n = 6, 7, 8 with r = 10 are missing since it seems computationally intractable to find the relative volume of Γ (n) r .

∞-extendible case
An ∞-extendible n-ME sequence is not necessarily the initial segment of a mixture of Markov Chains. As pointed out in [9], an infinite ME sequence starting in 0 is a mixture of two kinds of processes: recurrent Markov Chains and processes that deterministically begin with a streak of zeros, make a single (0, 1) transition and end with all ones. But if, as n → ∞, both n + 0 and n + 1 go to infinity, there exists a unique mixing measure ν over [0, 1] 2 and a couple (θ 0,0 , θ 1,1 ) such that, conditionally on X 1 = 0 p 0 n 0,0 n 0,1 n 1,0 n 1,1 = Denote the indicator function of the event the k-th successor of i is j as Y i,j (k): When we consider sequences starting both in 0 and 1, we introduce the probabilities w 1,a,b , defined as the probabilities of having the sequence starting in 1 with b transitions (1, 1) a single transition (1, 0), and ending with a transitions (0, 0). Then we have: In a mixture of Markov Chains it is So, unlike the DFPE case, we do not have the mixed moments of the mixing distribution, but those involved differences. It is easily seen that it is not possible to single out the mixed moments from the probabilities w 0,a,b and w 1,a,b . However, let N be the transition count matrix of (X 1 , . . . , X n ) intended as a r.v. Then, if the ME distribution is such that X 1 and N are independent, we can obtain them. Define and let P (X 1 = i) = q i . Under independence of X 1 and N we have Then we have m 1,b = m 0,b − (w 0,0,b /q 0 ), and in general, by recurrence So an n-ME distribution such that X 1 and N are independent is defined by the quantities m a,b , for every couple (a, b) such that a + b ≤ n − 1. In a mixture of Markov Chains it is m a,b = E ν θ a 0,0 θ b 1,1 and we can formulate generalized covariances as in (9) and (10) and state simple necessary conditions for ∞-extendibility as in the DFPE case.

Concluding remarks
For what we have said, either for exchangeable, DFPE and ME cases, the ∞-extendible Gupta in [15,16] looked for an extension of the Hausdorff's moment problem for distributions over the simplex, and implicitly found the necessary and sufficient conditions for the extendibility of an exchangeable finite sequence taking values in a finite state space, with the same geometric interpretation we have given. Combining his results with those of Section 3 one can easily find the conditions for the extendibility of DFPE sequences when the variables assume more than two values. It seems hard to find an analogous extension for the ME case.
Consequently, each matrix of the second kind is constructible by one of the first kind of a step longer, as long as n 1,0 is not null. Then we have to exclude the matrix having n 1,0 = n 0,1 = 0 and it is: We have just demonstrated that all the terms on the right hand side of (28) can be derived from (27), and it is p 0 ( a 2 1 b ) = ∆ 0 (∆ 1 (w 0,a,b )). So, we can derive the probability of any sequence starting in 0 and consistent with the transition count matrix ( a 2 1 b ).