Community detection is considered for a stochastic block model graph of n vertices, with K vertices in the planted community, edge probability p for pairs of vertices both in the community, and edge probability q for other pairs of vertices. The main focus of the paper is on weak recovery of the community based on the graph G, with o(K) misclassified vertices on average, in the sublinear regime n1-o(1) ≤ K ≤ o(n). A critical parameter is the effective signal-to-noise ratio λ = K2(p - q)2 / ((n - K)q), with λ = 1 corresponding to the Kesten–Stigum threshold. We show that a belief propagation (BP) algorithm achieves weak recovery if λ > 1 / e, beyond the Kesten–Stigum threshold by a factor of 1 / e. The BP algorithm only needs to run for log*n + O(1) iterations, with the total time complexity O(|E|log*n), where log*n is the iterated logarithm of n. Conversely, if λ ≤ 1 / e, no local algorithm can asymptotically outperform trivial random guessing. Furthermore, a linear message-passing algorithm that corresponds to applying a power iteration to the nonbacktracking matrix of the graph is shown to attain weak recovery if and only if λ > 1. In addition, the BP algorithm can be combined with a linear-time voting procedure to achieve the information limit of exact recovery (correctly classify all vertices with high probability) for all K ≥ (n / logn) (ρBP + o(1)), where ρBP is a function of p / q.

In this paper we relate the set of structure-preserving equivalent martingale measures ℳsp for financial models driven by semimartingales with conditionally independent increments to a set of measurable and integrable functions 𝒴. More precisely, we prove that ℳsp ≠ ∅ if and only if 𝒴 ≠ ∅, and connect the sets ℳsp and 𝒴 to the semimartingale characteristics of the driving process. As examples we consider integrated Lévy models with independent stochastic factors and time-changed Lévy models and derive mild conditions for ℳsp ≠ ∅.

We consider a simple model for the evolution of a limit order book in which limit orders of unit size arrive according to independent Poisson processes. The frequencies of buy limit orders below a given price level, respectively sell limit orders above a given level, are described by fixed demand and supply functions. Buy (respectively, sell) limit orders that arrive above (respectively, below) the current ask (respectively, bid) price are converted into market orders. There is no cancellation of limit orders. This model has been independently reinvented by several authors, including Stigler (1964), and Luckock (2003), who calculated the equilibrium distribution of the bid and ask prices. We extend the model by introducing market makers that simultaneously place both a buy and sell limit order at the current bid and ask price. We show that introducing market makers reduces the spread, which in the original model was unrealistically large. In particular, we calculate the exact rate at which market makers need to place orders in order to close the spread completely. If this rate is exceeded, we show that the price settles at a random level that, in general, does not correspond to the Walrasian equilibrium price.

Consider a sample 𝒳n={X1,…,Xn} of independent and identically distributed variables drawn with a probability distribution ℙX supported on a compact set M⊂ℝd. In this paper we mainly deal with the study of a natural estimator for the geodesic distance on M. Under rather general geometric assumptions on M, we prove a general convergence result. Assuming M to be a compact manifold of known dimension d′≤d, and under regularity assumptions on ℙX, we give an explicit convergence rate. In the case when M has no boundary, knowledge of the dimension d′ is not needed to obtain this convergence rate. The second part of the work consists in building an estimator for the Fréchet expectations on M, and proving its convergence under regularity conditions, applying the previous results.

We discuss weak convergence of the number of busy servers in a G/G/∞ queue in the J1-topology on the Skorokhod space. We prove two functional limit theorems with random and nonrandom centering, thereby solving two open problems stated in Mikosch and Resnick (2006). A new integral representation for the limit Gaussian process is given.

We consider an open problem of obtaining the optimal operational sequence for the 1-out-of-n system with warm standby. Using the virtual age concept and the cumulative exposure model, we show that the components should be activated in accordance with the increasing sequence of their lifetimes. Lifetimes of the components and the system are compared with respect to the stochastic precedence order and its generalization. Only specific cases of this optimal problem were considered in the literature previously.

The geometric structure of the nonparametric statistical model of all positive densities connected by an open exponential arc and its intimate relation to Orlicz spaces give new insights to well-known financial objects which arise in exponential utility maximization problems.

For all α > 0 and real random variables X, we establish sharp bounds for the smallest and the largest deviation of αX from the logarithmic distribution also known as Benford's law. In the case of uniform X, the value of the smallest possible deviation is determined explicitly. Our elementary calculation puts into perspective the recurring claims that a random variable conforms to Benford's law, at least approximately, whenever it has large spread.

An infinite convergent sum of independent and identically distributed random variables discounted by a multiplicative random walk is called perpetuity, because of a possible actuarial application. We provide three disjoint groups of sufficient conditions which ensure that the right tail of a perpetuity ℙ{X > x} is asymptotic to axce-bx as x → ∞ for some a, b > 0, and c ∈ ℝ. Our results complement those of Denisov and Zwart (2007). As an auxiliary tool we provide criteria for the finiteness of the one-sided exponential moments of perpetuities. We give several examples in which the distributions of perpetuities are explicitly identified.

We introduce a large and flexible class of discrete tempered stable distributions, and analyze the domains of attraction for both this class and the related class of positive tempered stable distributions. Our results suggest that these are natural models for sums of independent and identically distributed random variables with tempered heavy tails, i.e. tails that appear to be heavy up to a point, but ultimately decay faster.

In their 1960 book on finite Markov chains, Kemeny and Snell established that a certain sum is invariant. The value of this sum has become known as Kemeny’s constant. Various proofs have been given over time, some more technical than others. We give here a very simple physical justification, which extends without a hitch to continuous-time Markov chains on a finite state space. For Markov chains with denumerably infinite state space, the constant may be infinite and even if it is finite, there is no guarantee that the physical argument will hold. We show that the physical interpretation does go through for the special case of a birth-and-death process with a finite value of Kemeny’s constant.

Under mild nondegeneracy assumptions on branching rates in each generation, we provide a criterion for almost sure extinction of a multi-type branching process with time-dependent branching rates. We also provide a criterion for the total number of particles (conditioned on survival and divided by the expectation of the resulting random variable) to approach an exponential random variable as time goes to ∞.

We consider positive zero-sum stochastic games with countable state and action spaces. For each player, we provide a characterization of those strategies that are optimal in every subgame. These characterizations are used to prove two simplification results. We show that if player 2 has an optimal strategy then he/she also has a stationary optimal strategy, and prove the same for player 1 under the assumption that the state space and player 2's action space are finite.

The study of finite approximations of probability measures has a long history. In Xu and Berger (2017), the authors focused on constrained finite approximations and, in particular, uniform ones in dimension d=1. In the present paper we give an elementary construction of a uniform decomposition of probability measures in dimension d≥1. We then use this decomposition to obtain upper bounds on the rate of convergence of the optimal uniform approximation error. These bounds appear to be the generalization of the ones obtained by Xu and Berger (2017) and to be sharp for generic probability measures.

Let X1, X2, . . . be independent copies of a random vector X with values in ℝd and a continuous distribution function. The random vector Xn is a complete record, if each of its components is a record. As we require X to have independent components, crucial results for univariate records clearly carry over. But there are substantial differences as well. While there are infinitely many records in the d = 1 case, they occur only finitely many times in the series if d ≥ 2. Consequently, there is a terminal complete record with probability 1. We compute the distribution of the random total number of complete records and investigate the distribution of the terminal record. For complete records, the sequence of waiting times forms a Markov chain, but unlike the univariate case now the state at ∞ is an absorbing element of the state space.

Exemplar models are a popular class of models used to describe language change. Here we study how limiting the memory capacity of an individual in these models affects the system's behaviour. In particular, we demonstrate the effect this change has on the extinction of categories. Previous work in exemplar dynamics has not addressed this question. In order to investigate this, we will inspect a simplified exemplar model. We will prove for the simplified model that all the sound categories but one will always become extinct, whether memory storage is limited or not. However, computer simulations show that changing the number of stored memories alters how fast categories become extinct.

We develop shock model theory in different scenarios for the ℳ-class of life distributions introduced by Klar and Müller (2003). We also study the cumulative damage model of A-Hameed and Proschan (1975) in the context of ℳ-class and establish analogous results. We obtain moment bounds and explore weak convergence issues within the ℳ-class of life distributions.

While max-stable processes are typically written as pointwise maxima over an infinite number of stochastic processes, in this paper, we consider a family of representations based on ℓp-norms. This family includes both the construction of the Reich–Shaby model and the classical spectral representation by de Haan (1984) as special cases. As the representation of a max-stable process is not unique, we present formulae to switch between different equivalent representations. We further provide a necessary and sufficient condition for the existence of an ℓp-norm-based representation in terms of the stable tail dependence function of a max-stable process. Finally, we discuss several properties of the represented processes such as ergodicity or mixing.

Bizarrely shaped voting districts are frequently lambasted as likely instances of gerrymandering. In order to systematically identify such instances, researchers have devised several tests for so-called geographic compactness (i.e. shape niceness). We demonstrate that under certain conditions, a party can gerrymander a competitive state into geographically compact districts to win an average of over 70% of the districts. Our results suggest that geometric features alone may fail to adequately combat partisan gerrymandering.

It is well known that assumptions of monotonicity in size-bias couplings may be used to prove simple, yet powerful, Poisson approximation results. Here we show how these assumptions may be relaxed, establishing explicit Poisson approximation bounds (depending on the first two moments only) for random variables which satisfy an approximate version of these monotonicity conditions. These are shown to be effective for models where an underlying random variable of interest is contaminated with noise. We also state explicit Poisson approximation bounds for sums of associated or negatively associated random variables. Applications are given to epidemic models, extremes, and random sampling. Finally, we also show how similar techniques may be used to relax the assumptions needed in a Poincaré inequality and in a normal approximation result.