We introduce a novel preferential attachment model using the draw variables of a modified Pólya urn with an expanding number of colors, notably capable of modeling influential opinions (in terms of vertices of high degree) as the graph evolves. Similar to the Barabási-Albert model, the generated graph grows in size by one vertex at each time instance; in contrast however, each vertex of the graph is uniquely characterized by a color, which is represented by a ball color in the Pólya urn. More specifically at each time step, we draw a ball from the urn and return it to the urn along with a number of reinforcing balls of the same color; we also add another ball of a new color to the urn. We then construct an edge between the new vertex (corresponding to the new color) and the existing vertex whose color ball is drawn. Using color-coded vertices in conjunction with the time-varying reinforcing parameter allows for vertices added (born) later in the process to potentially attain a high degree in a way that is not captured in the Barabási-Albert model. We study the degree count of the vertices by analyzing the draw vectors of the underlying stochastic process. In particular, we establish the probability distribution of the random variable counting the number of draws of a given color which determines the degree of the vertex corresponding to that color in the graph. We further provide simulation results presenting a comparison between our model and the Barabási-Albert network.

Many classic networks grow by hooking small components via vertices. We introduce a class of networks that grows by fusing the edges of a small graph to an edge chosen uniformly at random from the network. For this random edge-hooking network, we study the local degree profile, that is, the evolution of the average degree of a vertex over time. For a special subclass, we further determine the exact distribution and an asymptotic gamma-type distribution. We also study the “core,” which consists of the well-anchored edges that experience fusing. A central limit theorem emerges for the size of the core.

At the end, we look at an alternative model of randomness attained by preferential hooking, favoring edges that experience more fusing. Under preferential hooking, the core still follows a Gaussian law but with different parameters. Throughout, Pólya urns are systematically used as a method of proof.

Motivated by recent studies of big samples, this work aims to construct a parametric model which is characterized by the following features: (i) a ‘local’ reinforcement, i.e. a reinforcement mechanism mainly based on the last observations, (ii) a random persistent fluctuation of the predictive mean, and (iii) a long-term almost sure convergence of the empirical mean to a deterministic limit, together with a chi-squared goodness-of-fit result for the limit probabilities. This triple purpose is achieved by the introduction of a new variant of the Eggenberger–Pólya urn, which we call the rescaled Pólya urn. We provide a complete asymptotic characterization of this model, pointing out that, for a certain choice of the parameters, it has properties different from the ones typically exhibited by the other urn models in the literature. Therefore, beyond the possible statistical application, this work could be interesting for those who are concerned with stochastic processes with reinforcement.

In addition to the features of the two-parameter Chinese restaurant process (CRP), the restaurant under consideration has a cocktail bar and hence allows for a wider range of (bar and table) occupancy mechanisms. The model depends on three real parameters, $\alpha$ , $\theta_1$ , and $\theta_2$ , fulfilling certain conditions. Results known for the two-parameter CRP are carried over to this model. We study the number of customers at the cocktail bar, the number of customers at each table, and the number of occupied tables after n customers have entered the restaurant. For $\alpha>0$ the number of occupied tables, properly scaled, is asymptotically three-parameter Mittag–Leffler distributed as n tends to infinity. We provide representations for the two- and three-parameter Mittag–Leffler distribution leading to efficient random number generators for these distributions. The proofs draw heavily from methods known for exchangeable random partitions, martingale methods known for generalized Pólya urns, and results known for the two-parameter CRP.

By now there is a solid theory for Polya urns. Finding the covariances is somewhat laborious. While these papers are “structural,” our purpose here is “computational.” We propose a practicable method for building the asymptotic covariance matrix in tenable balanced urn schemes, whereupon the asymptotic covariance matrix is obtained by solving a linear system of equations. We demonstrate the use of the method in growing tenable balanced irreducible schemes with a small index and in critical urns. In the critical case, the solution to the linear system of equations is explicit in terms of an eigenvector of the scheme.

In this paper, several properties of a class of trees presenting preferential attachment phenomenon—plane-oriented recursive trees (PORTs) are uncovered. Specifically, we investigate the degree profile of a PORT by determining the exact probability mass function of the degree of a node with a fixed label. We compute the expectation and the variance of degree variable via a Pólya urn approach. In addition, we study a topological index, Zagreb index, of this class of trees. We calculate the exact first two moments of the Zagreb index (of PORTs) by using recurrence methods. Lastly, we determine the limiting degree distribution in PORTs that grow in continuous time, where the embedding is done in a Poissonization framework. We show that it is exponential after proper scaling.

We consider a model of N interacting two-colour Friedman urns. The interaction model considered is such that the reinforcement of each urn depends on the fraction of balls of a particular colour in that urn as well as the overall fraction of balls of that colour in all the urns combined together. We show that the urns synchronize almost surely and that the fraction of balls of each colour converges to the deterministic limit of one-half, which matches with the limit known for a single Friedman urn. Furthermore, we use the notion of stable convergence to obtain limit theorems for fluctuations around the synchronization limit.

We investigate several aspects of a self-similar evolutionary process that builds a random bipolar network from building blocks that are themselves small bipolar networks. We characterize admissible outdegrees in the history of the evolution. We obtain the limit distribution of the polar degrees (when suitably scaled) characterized by its sequence of moments. We also obtain the asymptotic joint multivariate normal distribution of the number of nodes of small admissible outdegrees. Five possible substructures arise, and each has its own parameters (mean vector and covariance matrix) in the multivariate distribution. Several results are obtained by mapping bipolar networks into Pólya urns.

We investigate the degree profile and total weight in Apollonian networks. We study the distribution of the degrees of vertices as they age in the evolutionary process. Asymptotically, the (suitably-scaled) degree of a node with a fixed label has a Mittag-Leffler-like limit distribution. The degrees of nodes of later ages have different asymptotic distributions, influenced by the time of their appearance. The very late arrivals have a degenerate distribution. The result is obtained via triangular Pólya urns. Also, via the Bagchi–Pal urn, we show that the number of terminal nodes asymptotically follows a Gaussian law. We prove that the total weight of the network asymptotically follows a Gaussian law, obtained via martingale methods. Similar results carry over to the sister structure of the k-trees, with minor modification in the proof methods, done mutatis mutandis.

We study a class of tenable, irreducible, nondegenerate zero-balanced Pólya urn schemes. We give a full characterization of the class by sufficient and necessary conditions. Only forms with a certain cyclic structure in their replacement matrix are admissible. The scheme has a steady state into proportions governed by the principal (left) eigenvector of the average replacement matrix. We study the gradual change for any such urn containing n → ∞ balls from the initial condition to the steady state. We look at the status of an urn starting with an asymptotically positive proportion of each color after jn draws. We identify three phases of jn: the growing sublinear, the linear, and the superlinear. In the growing sublinear phase the number of balls of different colors has an asymptotic joint multivariate normal distribution, with mean and covariance structure that are influenced by the initial conditions. In the linear phase a different multivariate normal distribution kicks in, in which the influence of the initial conditions is attenuated. The steady state is not a good approximation until a certain superlinear amount of time has elapsed. We give interpretations for how the results in different phases conjoin at the ‘seam lines’. In fact, these Gaussian phases are all manifestations of one master theorem. The results are obtained via multivariate martingale theory. We conclude with some illustrating examples.

Spatial data sets can be analysed by counting the number of objects in equally sized bins. The bin counts are related to the Pólya urn process, where coloured balls (for example, white or black) are removed from the urn at random. If there are insufficient white or black balls for the prescribed number of trials, the Pólya urn process becomes untenable. In this case, we modify the Pólya urn process so that it continues to describe the removal of volume within a spatial distribution of objects. We determine when the standard formula for the variance of the standard Pólya distribution gives a good approximation to the true variance. The variance quantifies an index for assessing whether a spatial point data set is at its most randomly distributed state, called the complete spatial randomness (CSR) state. If the bin size is an order of magnitude larger than the size of the objects, then the standard formula for the CSR limit is indicative of when the CSR state has been attained. For the special case when the object size divides the bin size, the standard formula is in fact exact.

We introduce and motivate the study of (n + 1) × r arrays X with Bernoulli entries Xk,j and independently distributed rows. We study the distribution of which denotes the number of consecutive pairs of successes (or runs of length 2) when reading the array down the columns and across the rows. With the case r = 1 having been studied by several authors, and permitting some initial inferences for the general case r > 1, we examine various distributional properties and representations of Sn for the case r = 2, and, using a more explicit analysis, the case of multinomial and identically distributed rows. Applications are also given in cases where the array X arises from a Pólya sampling scheme.

Mallows and Shepp (2008) developed the following necklace processes. Start with a necklace consisting of one white bead and one black bead, and insert, one at a time, under a deterministic rule, a white bead or a black bead between a randomly chosen adjacent pair. They studied the statistical properties of the number of white beads by investigating the nature of the moments and the expected number of gaps of given length between white beads. In this note we study the number of white beads via Pólya urns and give a classification of necklace processes for some general rules. Additionally, we discuss the number of runs, i.e. the number of consecutive same color beads, instead of the number of gaps.

In a sequence of independent Bernoulli trials the probability of success in the kth trial is pk = a / (a + b + k − 1). An explicit formula for the binomial moments of the number of two consecutive successes in the first n trials is obtained and some consequences of it are derived.

We introduce a class of discrete-time stochastic processes generated by interacting systems of reinforced urns. We show that such processes are asymptotically partially exchangeable and we prove a strong law of large numbers. Examples and the analysis of particular cases show that interacting reinforced-urn systems are very flexible representations for modelling countable collections of dependent and asymptotically exchangeable sequences of random variables.

A sequence of independent, identically distributed random variables is observed. After a sample of m has been collected attention is fixed to a particular observation. In this paper the fluctuations of the rank of this observation, as sampling continues, will be studied.

The process can be modelled by a Pólya urn scheme, and new results are obtained which are of interest in both sequential rank and Pólya urn contexts.