Bivariate Issues in Leader Election Algorithms with Marshall-Olkin Limit Distribution

Most prior work in leader election algorithms deals with univariate statistics. We consider multivariate issues in a broad class of fair leader election algorithms. We investigate the joint distribution of the duration of two competing candidates. Under rather mild conditions on the splitting protocol, we prove the convergence of the joint distribution of the duration of any two contestants to a limit via convergence of distance (to 0) in a metric space on distributions. We then show that the limiting distribution is a Marshall-Olkin bivariate geometric distribution. Under the classic binomial splitting we are able to say a few more precise words about the exact joint distribution and exact covariance, and to explore (via Rice’s integral method) the oscillatory behavior of the diminishing covariance. We discuss several practical examples and present empirical observations on the rate of convergence of the covariance.     

Choices and intervals

We consider a random interval splitting process, in which the splitting rule depends on the empirical distribution of interval lengths. We show that this empirical distribution converges to a limit almost surely as the number of intervals goes to infinity. We give a characterization of this limit as a solution of an ODE and use this to derive precise tail estimates. The convergence is established by showing that the size-biased empirical distribution evolves in the limit according to a certain deterministic evolution equation. Although this equation involves a non-local, non-linear operator, it can be studied thanks to a carefully chosen norm with respect to which this operator is contractive.     

Symmetric random walk in random environment in one dimension

We give a new proof of the central limit theorem for one dimensional symmetric random walk in random environment. The proof is quite elementary and natural. We show the convergence of the generators and from this we conclude the convergence of the process. We also investigate the hydrodynamic limit (HDL) of one dimensional symmetric simple exclusion in random environment and prove stochastic convergence of the scaled density field. The macroscopic behaviour of this field is given by a linear heat equation. The diffusion coefficient is the same as that of the corresponding random walk. This revised version was published online in June 2006 with corrections to the Cover Date.     

The asymmetric leader election algorithm: Number of survivors near the end of the game

The following classical asymmetric leader election algorithm has obtained quite a bit of attention lately. Starting with n players, each one throws a coin, and the k of them which have each thrown a head (with probability q) go on, and the leader will be found amongst them, using the same strategy. Should nobody advance, the party will repeat the procedure. One of the most interesting parameter here is the number J (n) of rounds until a leader has been identified. In this paper we investigate, in the classical leader election algorithm, what happens near the end of the game, namely we fix an integer κ and we study the behaviour of the number of survivors L at level J (n) ? κ. In our asymptotic analysis (for n → ∞) we are focusing on the limiting distribution functions. We also investigate what happens, if the parameter p = 1 ? q gets small (p → 0) or large (p → 1). We use three e?cient tools: an urn model, a Mellin-Laplace technique for harmonic sums and some asymptotic distributions related to one of the extreme-value distributions: the Gumbel law. This study was motivated by a recent paper by Kalpathy, Mahmoud and Rosenkrantz, where they consider the number of survivors S_n,t, after t election rounds, in a broad class of fair leader election algorithms starting with n candidates.     

Player splitting in extensive form games

By a player splitting we mean a mechanism that distributes the information sets of a player among so-called agents. A player splitting is called independent if each path in the game tree contains at most one agent of every player. Following Mertens (1989), a solution is said to have the player splitting property if, roughly speaking, the solution of an extensive form game does not change by applying independent player splittings. We show that Nash equilibria, perfect equilibria, Kohlberg-Mertens stable sets and Mertens stable sets have the player splitting property. An example is given to show that the proper equilibrium concept does not satisfy the player splitting property. Next, we give a definition of invariance under (general) player splittings which is an extension of the player splitting property to the situation where we also allow for dependent player splittings. We come to the conclusion that, for any given dependent player splitting, each of the above solutions is not invariant under this player splitting. The results are used to give several characterizations of the class of independent player splittings and the class of single appearance structures by means of invariance of solution concepts under player splittings. Received: December 1996/Revised Version: January 2000     

Random methods in 3-manifold theory

The surface map arising from a random walk on the mapping class group may be used as the gluing map for a Heegaard splitting, and the resulting 3-manifold is known as a random Heegaard splitting. We show that the splitting distance of random Heegaard splittings grows linearly in the length of the random walk, with an exponential decay estimate for the proportion with slower growth. We use this to obtain the limiting distribution of Casson invariants of random Heegaard splittings.     

Log-Convexity of Counting Processes Evaluated at a Random end of Observation Time with Applications to Queueing Models

We consider a counting processes with independent inter-arrival times evaluated at a random end of observation time T, independent of the process. For instance, this situation can arise in a queueing model when we evaluate the number of arrivals after a random period which can depend on the process of service times. Provided that T has log-convex density, we give conditions for the inter-arrival times in the counting process so that the observed number of arrivals inherits this property. For exponential inter-arrival times (pure-birth processes) we provide necessary and sufficient conditions. As an application, we give conditions such that the stationary number of customers waiting in a queue is a log-convex random variable. We also study bounds in the approximation of log-convex discrete random variables by a geometric distribution.     

一类强极限定理与矩母函数方法

本文利用似然比的概念，研究离散随机变量序列的极限性质，得到了一类用不等式表示的强极限定理．证明中结合区间剖分法，提出了将矩母函数的工具应用于强极限定理的研究的一种途径．     

A limit theorem for particle numbers in bounded domains of a branching diffusion process

We shall study the asymptotic behavior of the particle numbers in bounded domains of a binary splitting one-dimensional branching diffusion process. We shall give a Yaglom type limit theorem in the so-called locally subcritical case, and almost sure convergence of the normalized particle number in the locally supercritical case.     

Ellipticity criteria for ballistic behavior of random walks in random environment

We introduce ellipticity criteria for random walks in i.i.d. random environments under which we can extend the ballisticity conditions of Sznitman and the polynomial effective criteria of Berger, Drewitz and Ramírez originally defined for uniformly elliptic random walks. We prove under them the equivalence of Sznitman’s \((T')\) condition with the polynomial effective criterion \((P)_M\) , for \(M\) large enough. We furthermore give ellipticity criteria under which a random walk satisfying the polynomial effective criterion, is ballistic, satisfies the annealed central limit theorem or the quenched central limit theorem.     

The Markov chain asymptotics of random mapping graphs

In this paper the limit behavior of random mappings with n vertices is investigated. We first compute the asymptotic probability that a fixed class of finite non-intersected subsets of vertices are located in different components and use this result to construct a scheme of allocating particles with a related Markov chain. We then prove that the limit behavior of random mappings is actually embedded in such a scheme in a certain way. As an application, we shall give the asymptotic moments of the size of the largest component.     

Gauss sums and multinomial coefficients

Consider a Gauss sum for a finite field of characteristic p, where p is an odd prime. When such a sum (or a product of such sums) is a p-adic integer we show how it can be realized as a p-adic limit of a sequence of multinomial coefficients. As an application we generalize some congruences of Hahn and Lee to exhibit p-adic limit formulae, in terms of multinomial coefficients, for certain algebraic integers in imaginary quadratic fields related to the splitting of rational primes. We also give an example illustrating how such congruences arise from a p-integral formal group law attached to the p-adic unit part of a product of Gauss sums.     

Law of large numbers for weighted inductive means in a Hadamard space

We first study the law of large numbers for weighted inductive means of independent identically distributed random variables taking values in a Hadamard space. Secondly, we give a sharp asymptotic estimate for the limit of (non‐weighed) inductive means for the p‐Schatten class.     

On perfect nonlinear functions

An Erratum has been published for this article in Journal of Combinatorial Designs 14: 82–82, 2006 . We give the equivalence between perfect nonlinear functions and appropriate splitting semi‐regular relative difference sets, construct a class of splitting relative difference sets by using Galois rings and bent functions, and prove that there exists a 4‐phase perfect nonlinear function if and only if the number of input variables is at least twice the number of output variables. © 2005 Wiley Periodicals, Inc.     

Occupation Time Fluctuations of Weakly Degenerate Branching Systems

We establish limit theorems for rescaled occupation time fluctuations of a sequence of branching particle systems in ? ^d with anisotropic space motion and weakly degenerate splitting ability. In the case of large dimensions, our limit processes lead to a new class of operator-scaling Gaussian random fields with nonstationary increments. In the intermediate and critical dimensions, the limit processes have spatial structures analogous to (but more complicated than) those arising from the critical branching particle system without degeneration considered by Bojdecki et?al. (Stoch. Process. Appl. 116:1?C18 and 19?C35, 2006). Due to the weakly degenerate branching ability, temporal structures of the limit processes in all three cases are different from those obtained by Bojdecki et?al. (Stoch. Process. Appl. 116:1?C18 and 19?C35, 2006).     

A New Criterion for Controlling the Number of Limit Cycles of Some Generalized Liénard Equations

We consider a class of planar differential equations which include the Liénard differential equations. By applying the Bendixson-Dulac Criterion for ?-connected sets we reduce the study of the number of limit cycles for such equations to the condition that a certain function of just one variable does not change sign. As an application, this method is used to give a sharp upper bound for the number of limit cycles of some Liénard differential equations. In particular, we present a polynomial Liénard system with exactly three limit cycles.     

Generalized random recursive constructions and geometric properties of random fractals

We study random recursive constructions in which the contracting vectors have different distributions at different stages. With such constructions, the one parameter family of martingales are introduced and the probabilistic behaviours of the limit random objects (not identically distributed) are discussed. We prove that the random fractal associated with such construction has a constant Hausdorff dimension almost surely and give an explicit formula to determine it. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Dynamic adjustment: an electoral method for relaxed double proportionality

We describe an electoral system for distributing seats in a parliament. It gives proportionality for the political parties and close to proportionality for constituencies. The system suggested here is a version of the system used in Sweden and other Nordic countries with permanent seats in each constituency and adjustment seats to give proportionality on the national level. In the national election of 2010 the current Swedish system failed to give proportionality between parties. We examine here one possible cure for this unwanted behavior. The main difference compared to the current Swedish system is that the number of adjustment seats is not fixed, but rather dynamically determined to be as low as possible and still insure proportionality between parties.     

Common stabilizations of Heegaard splittings of link exteriors

We give a condition for a pair of unknotting tunnels of a non-trivial tunnel number one link to give a genus three Heegaard splitting of the link complement and show that every 2-bridge link has such a pair of unknotting tunnels.