An edge flipping is a non-reversible Markov chain on a given connected graph, as defined in Chung and Graham (2012). In the same paper, edge flipping eigenvalues and stationary distributions for some classes of graphs were identified. We further study edge flipping spectral properties to show a lower bound for the rate of convergence in the case of regular graphs. Moreover, we show by a coupling argument that a cutoff occurs at $\frac{1}{4} n \log n$ for the edge flipping on the complete graph.

In this study, we consider a class of multiple-drawing opposite-reinforcing urns with time-dependent replacement rules. The class has the symmetric property of a Friedman-type urn. We divide the class into a small-increment regime and a large-increment regime. For small-increment schemes, we prove almost-sure convergence and a central limit theorem for the proportion of white balls by stochastic approximation. For large-increment schemes, by assuming the affinity condition, we show almost-sure convergence of the proportion of white balls by martingale theory and present a way to identify the limit distribution of the proportion of white balls.

We investigate various variable martingale Hardy spaces corresponding to variable Lebesgue spaces $\mathcal {L}_{p(\cdot )}$ defined by rearrangement functions. In particular, we show that the dual of martingale variable Hardy space $\mathcal {H}_{p(\cdot )}^{s}$ with $0<p_{-}\leq p_{+}\leq 1$ can be described as a BMO-type space and establish martingale inequalities among these martingale Hardy spaces. Furthermore, we give an application of martingale inequalities in stochastic integral with Brownian motion.

In this paper, we investigate noncommutative symmetric and asymmetric maximal inequalities associated with martingale transforms and fractional integrals. Our proofs depend on some recent advances on algebraic atomic decomposition and the noncommutative Gundy decomposition. We also prove several fractional maximal inequalities.

A new network evolution model is introduced in this paper. The model is based on cooperations of N units. The units are the nodes of the network and the cooperations are indicated by directed links. At each evolution step N units cooperate, which formally means that they form a directed N-star subgraph. At each step either a new unit joins the network and it cooperates with N − 1 old units, or N old units cooperate. During the evolution both preferential attachment and uniform choice are applied. Asymptotic power law distributions are obtained both for in-degrees and for out-degrees.

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.

We study a weighted maximal weak-type inequality for Haar multipliers that can be regarded as a dual problem of Muckenhoupt and Wheeden. More precisely, if Tε is the Haar multiplier associated with the sequence ε with values in [−1, 1], and is the r-maximal operator, then for any weight w and any function f on [0, 1) we have

for some constant Cr depending only on r. We also show that the analogous result does not hold if we replace by the dyadic maximal operator Md. The proof rests on the Bellman function method; using this technique we establish related weighted Lp estimates for p close to 1, and then deduce the main result by extrapolation arguments.

In two recent works, Kuba and Mahmoud (2015a) and (2015b) introduced the family of two-color affine balanced Pólya urn schemes with multiple drawings. We show that, in large-index urns (urn index between ½ and 1) and triangular urns, the martingale tail sum for the number of balls of a given color admits both a Gaussian central limit theorem as well as a law of the iterated logarithm. The laws of the iterated logarithm are new, even in the standard model when only one ball is drawn from the urn in each step (except for the classical Pólya urn model). Finally, we prove that the martingale limits exhibit densities (bounded under suitable assumptions) and exponentially decaying tails. Applications are given in the context of node degrees in random linear recursive trees and random circuits.

We consider a variant of the randomly reinforced urn where more balls can be simultaneously drawn out and balls of different colors can be simultaneously added. More precisely, at each time-step, the conditional distribution of the number of extracted balls of a certain color, given the past, is assumed to be hypergeometric. We prove some central limit theorems in the sense of stable convergence and of almost sure conditional convergence, which are stronger than convergence in distribution. The proven results provide asymptotic confidence intervals for the limit proportion, whose distribution is generally unknown. Moreover, we also consider the case of more urns subjected to some random common factors.

Famously, a d-dimensional, spatially homogeneous random walk whose increments are nondegenerate, have finite second moments, and have zero mean is recurrent if d∈{1,2}, but transient if d≥3. Once spatial homogeneity is relaxed, this is no longer true. We study a family of zero-drift spatially nonhomogeneous random walks (Markov processes) whose increment covariance matrix is asymptotically constant along rays from the origin, and which, in any ambient dimension d≥2, can be adjusted so that the walk is either transient or recurrent. Natural examples are provided by random walks whose increments are supported on ellipsoids that are symmetric about the ray from the origin through the walk's current position; these elliptic random walks generalize the classical homogeneous Pearson‒Rayleigh walk (the spherical case). Our proof of the recurrence classification is based on fundamental work of Lamperti.

Let $\mathcal{M}$ and G denote, respectively, the maximal operator and the geometric maximal operator associated with the dyadic lattice on $\mathbb{R}^d$.

1. (i) We prove that for any 0 < p < ∞, any weight w on $\mathbb{R}^d$ and any measurable f on $\mathbb{R}^d$, we have Fefferman–Stein-type estimate

   $$\begin{equation*} ||G(f)||_{L^p(w)}\leq e^{1/p}||f||_{L^p(\mathcal{M}w)}. \end{equation*} $$
   For each p, the constant e1/p is the best possible.

2. (ii) We show that for any weight w on $\mathbb{R}^d$ and any measurable f on $\mathbb{R}^d$,

   $$\begin{equation*} \int_{\mathbb{R}^d} G(f)^{1/\mathcal{M}w}w\mbox{d}x\leq e\int_{\mathbb{R}^d} |f|^{1/w}w\mbox{d}x \end{equation*} $$
   and prove that the constant e is optimal.

We consider a branching random walk. Biggins and Kyprianou (2004) proved that, in the boundary case, the associated derivative martingale converges almost surely to a finite nonnegative limit, whose law serves as a fixed point of a smoothing transformation (Mandelbrot's cascade). In this paper, we give a necessary and sufficient condition for the nontriviality of the limit in this boundary case.

We deal with a random graph model evolving in discrete time steps by duplicating and deleting the edges of randomly chosen vertices. We prove the existence of an almost surely asymptotic degree distribution, with stretched exponential decay; more precisely, the proportion of vertices of degree d tends to some positive number cd > 0 almost surely as the number of steps goes to ∞, and cd ~ (eπ)1/2d1/4e-2√d holds as d → ∞.

We propose a two-urn model of Pólya type as follows. There are two urns, urn A and urn B. At the beginning, urn A contains rA red and wA white balls and urn B contains rB red and wB white balls. We first draw m balls from urn A and note their colors, say i red and m - i white balls. The balls are returned to urn A and bi red and b(m - i) white balls are added to urn B. Next, we draw ℓ balls from urn B and note their colors, say j red and ℓ - j white balls. The balls are returned to urn B and aj red and a(ℓ - j) white balls are added to urn A. Repeat the above action n times and let Xn be the fraction of red balls in urn A and Yn the fraction of red balls in urn B. We first show that the expectations of Xn and Yn have the same limit, and then use martingale theory to show that Xn and Yn converge almost surely to the same limit.

Consider a sequence of Markov-dependent trials where each trial produces a letter of a finite alphabet. Given a collection of patterns, we look at this sequence until one of these patterns appears as a run. We show how the method of gambling teams can be employed to compute the probability that a given pattern is the first pattern to occur.

This note contains two main results. (i) (Discrete time) Suppose that S is a martingale whose marginal laws agree with a geometric simple random walk. (In financial terms, let S be a risk-neutral asset price and suppose that the initial option prices agree with the Cox-Ross-Rubinstein binomial tree model.) Then S is a geometric simple random walk. (ii) (Continuous time) Suppose that S=S0eσ X-σ2〈 X〉/2 is a continuous martingale whose marginal laws agree with a geometric Brownian motion. (In financial terms, let S be a risk-neutral asset price and suppose that the initial option prices agree with the Black-Scholes model with volatility σ>0.) Then there exists a Brownian motion W such that Xt=Wt+o(t1/4+ ε) as t↑∞ for any ε> 0.

We introduce and analyze a random tree model associated to Hoppe's urn. The tree is built successively by adding nodes to the existing tree when starting with the single root node. In each step a node is added to the tree as a child of an existing node, where these parent nodes are chosen randomly with probabilities proportional to their weights. The root node has weight ϑ>0, a given fixed parameter, all other nodes have weight 1. This resembles the stochastic dynamic of Hoppe's urn. For ϑ=1, the resulting tree is the well-studied random recursive tree. We analyze the height, internal path length, and number of leaves of the Hoppe tree with n nodes as well as the depth of the last inserted node asymptotically as n→∞. Mainly expectations, variances, and asymptotic distributions of these parameters are derived.

We consider the question of an optimal transaction between two investors to minimize their risks. We define a dynamic entropic risk measure using backward stochastic differential equations related to a continuous-time single jump process. The inf-convolution of dynamic entropic risk measures is a key transformation in solving the optimization problem.

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.

The ‘coupon collection problem’ refers to a class of occupancy problems in which j identical items are distributed, independently and at random, to n cells, with no restrictions on multiple occupancy. Identifying the cells as coupons, a coupon is ‘collected’ if the cell is occupied by one or more of the distributed items; thus, some coupons may never be collected, whereas others may be collected once or twice or more. We call the number of coupons collected exactly r times coupons of type r. The coupon collection model we consider is general, in that a random number of purchases occurs at each stage of collecting a large number of coupons; the sample sizes at each stage are independent and identically distributed according to a sampling distribution. The joint behavior of the various types is an intricate problem. In fact, there is a variety of joint central limit theorems (and other limit laws) that arise according to the interrelation between the mean, variance, and range of the sampling distribution, and of course the phase (how far we are in the collection processes). According to an appropriate combination of the mean of the sampling distribution and the number of available coupons, the phase is sublinear, linear, or superlinear. In the sublinear phase, the normalization that produces a Gaussian limit law for uncollected coupons can be used to obtain a multivariate central limit law for at most two other types — depending on the rates of growth of the mean and variance of the sampling distribution, we may have a joint central limit theorem between types 0 and 1, or between types 0, 1, and 2. In the linear phase we have a multivariate central limit theorem among the types 0, 1,…, k for any fixed k.