A functional limit theorem is proved for multitype continuous time Markov branching processes. As consequences, we obtain limit theorems for the branching process stopped by some stopping rule, for ...example when the total number of particles reaches a given level.
Using the Athreya–Karlin embedding, these results yield asymptotic results for generalized Pólya urns. We investigate such results in detail and obtain explicit formulas for the asymptotic variances and covariances. The general formulas involve integrals of matrix functions; we show how they can be evaluated and simplified in important special cases. We also consider the numbers of drawn balls of different types and functional limit theorems for the urns.
We illustrate our results by some examples, including several applications to random trees where our theorems and variance formulas give simple proofs of some known results; we also give some new results.
We consider random two‐colorings of random linear preferential attachment trees, which includes recursive trees, plane‐oriented recursive trees, binary search trees, and a class of d‐ary trees. The ...random coloring is defined by assigning the root the color red or blue with equal probability, and all other vertices are assigned the color of their parent with probability p$$ p $$ and the other color otherwise. These colorings have been previously studied in other contexts, including Ising models and broadcasting, and can be considered as generalizations of bond percolation. With the help of Pólya urns, we prove limiting distributions, after proper rescalings, for the number of vertices, monochromatic subtrees, and leaves of each color, as well as the number of fringe subtrees with two‐colorings. Using methods from analytic combinatorics, we also provide precise descriptions of the limiting distribution after proper rescaling of the size of the root cluster; the largest monochromatic subtree containing the root.
Discussed here is the presence of a warrior aristocracy in south-western Hungary, principally in County Somogy, during the early (and middle) Urnfield period (Br D–Ha A1-A2) based on the ...archaeological record. The period's offensive and protective weapons wielded by the warrior aristocracy during the Urnfield period (mid-thirteenth to ninth century BC) are exclusively known from hoards in this region; none have been recovered from burials. The Lengyeltóti V hoard contained a greave, a composite cuirass, a cheek-piece indicating the presence of a military aristocracy riding horses and wagons or chariots when going to battle and a realistic wheel model. The swords and spearheads were part of the period's offensive weaponry. The hoard's other articles represented the jewellery of the female aristocracy: a diadem, a torc and an ornamented disc pendant. The hoard contained over seven hundred items. In A. Mozsolics's view, the hoard could be assigned to the period lasting up to the close of the Hallstatt period (Ha A2). The rise of the warrior aristocracy began during the Br D, Br D/Ha A1 period, while its consolidation and heyday fell into the early Urnfield period (Ha A1). The aristocracy lived in hillforts – fortified settlements – which had a flourishing bronze industry. The number of settlements and burials declined drastically in the ensuing Ha B period in south-western Transdanubia.
The coexistence of several types of urns in the funerary antiquities of the Aestians and Prussians testifies to the fact that in the imagination of community members (obviously, mainly women), there ...were prototypes of urns that were of ethno-cultural significance for (forced) ceramists. The aforementioned inhabitants of the Amber Coast at the beginning of our era were called Aestii by the Germans (ancient German - "living in the east"). The low quality of urn ceramics and their weak firing characterize the insignificant professional training of members of the tribal collective, who are forced to mold vessels only when necessary to prepare the urn for the funeral of a relative. The large sizes of the main part of the types of urns in our array are obviously the result of some cult norms. Ashes from the fire and cremated remains of the deceased, together with his inventory, occupy a small part of the urn's volume and were not necessarily at its bottom. Existing in the traditions of the population of the Amber Coast for half a millennium, the urn, as it turned out, can contain information of a chronological and ethno-cultural nature, and not just be recorded by archaeologists as a repository of the ashes of the buried.
We introduce a general two-colour interacting urn model on a finite directed graph, where each urn at a node reinforces all the urns in its out-neighbours according to a fixed, non-negative, and ...balanced reinforcement matrix. We show that the fraction of balls of either colour converges almost surely to a deterministic limit if either the reinforcement is not of Pólya type or the graph is such that every vertex with non-zero in-degree can be reached from some vertex with zero in-degree. We also obtain joint central limit theorems with appropriate scalings. Furthermore, in the remaining case when there are no vertices with zero in-degree and the reinforcement is of Pólya type, we restrict our analysis to a regular graph and show that the fraction of balls of either colour converges almost surely to a finite random limit, which is the same across all the urns.
In this paper, we prove convergence and fluctuation results for measure-valued P\'olya processes (MVPPs, also known as P\'olya urns with infinitely many colours). Our convergence results hold almost ...surely and in $L^2$, under assumptions that are different from that of other convergence results in the literature. Our fluctuation results are the first second-order results in the literature on MVPPs; they generalise classical fluctuation results from the literature on finitely-many-colour P\'olya urns. As in the finitely-many-colour case, the order and shape of the fluctuations depend on whether the "spectral gap is small or large". To prove these results, we show that MVPPs are stochastic approximations taking values in the set of measures on a measurable space $E$ (the colour space). We then use martingale methods and standard operator theory to prove convergence and fluctuation results for these stochastic approximations.
We consider two types of random networks grown in blocks. Hooking networks are grown from a set of graphs as blocks, each with a labelled vertex called a hook. At each step in the growth of the ...network, a vertex called a latch is chosen from the hooking network and a copy of one of the blocks is attached by fusing its hook with the latch. Bipolar networks are grown from a set of directed graphs as blocks, each with a single source and a single sink. At each step in the growth of the network, an arc is chosen and is replaced with a copy of one of the blocks. Using Pólya urns, we prove normal limit laws for the degree distributions of both networks. We extend previous results by allowing for more than one block in the growth of the networks and by studying arbitrarily large degrees.
It is known that in an irreducible small Polya urn process, the composition of the urn after suitable normalization converges in distribution to a normal distribution. We show that if the urn also is ...balanced, this normal convergence holds with convergence of all moments, thus giving asymptotics of (central) moments.
In this article, we introduce a dynamic generative model, the Bayesian allocation model (BAM), for modeling count data. BAM covers various probabilistic nonnegative tensor factorization (NTF) and ...topic models under one general framework. In BAM, allocations are made using a Bayesian network, whose conditional probability tables can be integrated out analytically. We show that, when allocations are viewed as sequential, the resulting marginal process is a special type of Polya urn process, which we name as Polya-Bayes process, an integer valued self-reinforcing process. Exploiting the Polya urn construction, we develop a novel sequential Monte Carlo (SMC) algorithm for marginal likelihood estimation in BAM, leading to a unified scoring method for discrete variable Bayesian networks with hidden nodes, including various NTF and topic models. The SMC estimator for marginal likelihood has the remarkable property of being unbiased in contrast to variational algorithms which are generally biased. We also demonstrate how our novel SMC-based likelihood estimation can be integrated within a Markov chain Monte Carlo algorithm for a principled and correct (in terms of respecting the true posterior distribution) Bayesian model selection and hyperparameter estimation for BAM. We provide several numerical examples, both on artificial and real datasets, that demonstrate the performance of the algorithms for various data regimes.
Online extremists’ use of social media poses a new form of threat to the general public. These extremists range from cyberbullies to terrorist organizations. Social media providers often suspend the ...extremists’ accounts in response to user complaints. However, extremist users can simply create new accounts and continue their activities. In this work we present a new set of operational capabilities to address the threat posed by online extremists in social networks. We use thousands of Twitter accounts related to the Islamic State in Iraq and Syria (ISIS) to develop behavioral models for these users—in particular, what their accounts look like and with whom they connect. We use these models to track existing extremist users by identifying pairs of accounts belonging to the same user. We then present a model for efficiently searching the social network to find suspended users’ new accounts based on a variant of the classic Pólya’s urn setup. We find a simple characterization of the optimal search policy for this model under fairly general conditions. Our urn model and main theoretical results generalize easily to search problems in other fields.
The electronic companion is available at
https://doi.org/10.1287/opre.2018.1719
.