We study the community detection problem on a Gaussian mixture model, in which vertices are divided into $k\geq 2$ distinct communities. The major difference in our model is that the intensities for Gaussian perturbations are different for different entries in the observation matrix, and we do not assume that every community has the same number of vertices. We explicitly find the necessary and sufficient conditions for the exact recovery of the maximum likelihood estimation, which can give a sharp phase transition for the exact recovery even though the Gaussian perturbations are not identically distributed; see Section 7. Applications include the community detection on hypergraphs.

We calculate the mean throughput, number of collisions, successes, and idle slots for random tree algorithms with successive interference cancellation. Except for the case of the throughput for the binary tree, all the results are new. We furthermore disprove the claim that only the binary tree maximizes throughput. Our method works with many observables and can be used as a blueprint for further analysis.

In this paper we analyze a simple spectral method (EIG1) for the problem of matrix alignment, consisting in aligning their leading eigenvectors: given two matrices A and B, we compute two corresponding leading eigenvectors $v_1$ and $v'_{\!\!1}$ . The algorithm returns the permutation $\hat{\pi}$ such that the rank of coordinate $\hat{\pi}(i)$ in $v_1$ and that of coordinate i in $v'_{\!\!1}$ (up to the sign of $v'_{\!\!1}$ ) are the same.

We consider a model of weighted graphs where the adjacency matrix A belongs to the Gaussian orthogonal ensemble of size $N \times N$ , and B is a noisy version of A where all nodes have been relabeled according to some planted permutation $\pi$ ; that is, $B= \Pi^T (A+\sigma H) \Pi $ , where $\Pi$ is the permutation matrix associated with $\pi$ and H is an independent copy of A. We show the following zero–one law: with high probability, under the condition $\sigma N^{7/6+\epsilon} \to 0$ for some $\epsilon>0$ , EIG1 recovers all but a vanishing part of the underlying permutation $\pi$ , whereas if $\sigma N^{7/6-\epsilon} \to \infty$ , this method cannot recover more than o(N) correct matches.

This result gives an understanding of the simplest and fastest spectral method for matrix alignment (or complete weighted graph alignment), and involves proof methods and techniques which could be of independent interest.

Coupling-from-the-past (CFTP) methods have been used to generate perfect samples from finite Gibbs hard-sphere models, an important class of spatial point processes consisting of a set of spheres with the centers on a bounded region that are distributed as a homogeneous Poisson point process (PPP) conditioned so that spheres do not overlap with each other. We propose an alternative importance-sampling-based rejection methodology for the perfect sampling of these models. We analyze the asymptotic expected running time complexity of the proposed method when the intensity of the reference PPP increases to infinity while the (expected) sphere radius decreases to zero at varying rates. We further compare the performance of the proposed method analytically and numerically with that of a naive rejection algorithm and of popular dominated CFTP algorithms. Our analysis relies upon identifying large deviations decay rates of the non-overlapping probability of spheres whose centers are distributed as a homogeneous PPP.

We analyse the behaviour of the Euclidean algorithm applied to pairs (g,f) of univariate nonconstant polynomials over a finite field $\mathbb{F}_{q}$ of q elements when the highest degree polynomial g is fixed. Considering all the elements f of fixed degree, we establish asymptotically optimal bounds in terms of q for the number of elements f that are relatively prime with g and for the average degree of $\gcd(g,f)$ . We also exhibit asymptotically optimal bounds for the average-case complexity of the Euclidean algorithm applied to pairs (g,f) as above.

We consider the problem of computing the partition function $\sum _x e^{f(x)}$ , where $f: \{-1, 1\}^n \longrightarrow {\mathbb R}$ is a quadratic or cubic polynomial on the Boolean cube $\{-1, 1\}^n$ . In the case of a quadratic polynomial f, we show that the partition function can be approximated within relative error $0 < \epsilon < 1$ in quasi-polynomial $n^{O(\ln n - \ln \epsilon )}$ time if the Lipschitz constant of the non-linear part of f with respect to the $\ell ^1$ metric on the Boolean cube does not exceed $1-\delta $ , for any $\delta>0$ , fixed in advance. For a cubic polynomial f, we get the same result under a somewhat stronger condition. We apply the method of polynomial interpolation, for which we prove that $\sum _x e^{\tilde {f}(x)} \ne 0$ for complex-valued polynomials $\tilde {f}$ in a neighborhood of a real-valued f satisfying the above mentioned conditions. The bounds are asymptotically optimal. Results on the zero-free region are interpreted as the absence of a phase transition in the Lee–Yang sense in the corresponding Ising model. The novel feature of the bounds is that they control the total interaction of each vertex but not every single interaction of sets of vertices.

The Orthogonal Least Squares (OLS) algorithm is an efficient sparse recovery algorithm that has received much attention in recent years. On one hand, this paper considers that the OLS algorithm recovers the supports of sparse signals in the noisy case. We show that the OLS algorithm exactly recovers the support of $K$-sparse signal $\boldsymbol{x}$ from $\boldsymbol{y}=\boldsymbol{\unicode[STIX]{x1D6F7}}\boldsymbol{x}+\boldsymbol{e}$ in $K$ iterations, provided that the sensing matrix $\boldsymbol{\unicode[STIX]{x1D6F7}}$ satisfies the restricted isometry property (RIP) with restricted isometry constant (RIC) $\unicode[STIX]{x1D6FF}_{K+1}<1/\sqrt{K+1}$, and the minimum magnitude of the nonzero elements of $\boldsymbol{x}$ satisfies some constraint. On the other hand, this paper demonstrates that the OLS algorithm exactly recovers the support of the best $K$-term approximation of an almost sparse signal $\boldsymbol{x}$ in the general perturbations case, which means both $\boldsymbol{y}$ and $\boldsymbol{\unicode[STIX]{x1D6F7}}$ are perturbed. We show that the support of the best $K$-term approximation of $\boldsymbol{x}$ can be recovered under reasonable conditions based on the restricted isometry property (RIP).

We present an average-case analysis of a variant of dual-pivot quicksort. We show that the algorithmic partitioning strategy used is optimal, that is, it minimizes the expected number of key comparisons. For the analysis, we calculate the expected number of comparisons exactly as well as asymptotically; in particular, we provide exact expressions for the linear, logarithmic and constant terms.

An essential step is the analysis of zeros of lattice paths in a certain probability model. Along the way a combinatorial identity is proved.

One of the easiest randomized greedy optimization algorithms is the following evolutionary algorithm which aims at maximizing a function f: {0,1}n → ℝ. The algorithm starts with a random search point ξ ∈ {0,1}n, and in each round it flips each bit of ξ with probability c/n independently at random, where c > 0 is a fixed constant. The thus created offspring ξ' replaces ξ if and only if f(ξ') ≥ f(ξ). The analysis of the runtime of this simple algorithm for monotone and for linear functions turned out to be highly non-trivial. In this paper we review known results and provide new and self-contained proofs of partly stronger results.

We study the number of random permutations needed to invariably generate the symmetric group Sn when the distribution of cycle counts has the strong α-logarithmic property. The canonical example is the Ewens sampling formula, for which the special case α = 1 corresponds to uniformly random permutations.

For strong α-logarithmic measures and almost every α, we show that precisely ⌈(1−αlog2)−1⌉ permutations are needed to invariably generate Sn with asymptotically positive probability. A corollary is that for many other probability measures on Sn no fixed number of permutations will invariably generate Sn with positive probability. Along the way we generalize classic theorems of Erdős, Tehran, Pyber, Łuczak and Bovey to permutations obtained from the Ewens sampling formula.

The generalized orthogonal matching pursuit $\left( \text{gOMP} \right)$ algorithm has received much attention in recent years as a natural extension of the orthogonal matching pursuit $\left( \text{OMP} \right)$. It is used to recover sparse signals in compressive sensing. In this paper, a new bound is obtained for the exact reconstruction of every $K$-sparse signal via the $\text{gOMP}$ algorithm in the noiseless case. That is, if the restricted isometry constant $\left( \text{RIC} \right)$${{\delta }_{NK+1}}$ of the sensing matrix $A$ satisfies

${{\delta }_{NK+1}}\,<\frac{1}{\sqrt{\frac{K}{N}+\,1}},$

then the $\text{gOMP}$ can perfectly recover every $K$-sparse signal $x$ from $y\,=\,Ax$. Furthermore, the bound is proved to be sharp. In the noisy case, the above bound on $\text{RIC}$ combining with an extra condition on the minimum magnitude of the nonzero components of $K$-sparse signals can guarantee that the $\text{gOMP}$ selects all of the support indices of the $K$-sparse signals.

We study the size and the external path length of random tries and show that they are asymptotically independent in the asymmetric case but strongly dependent with small periodic fluctuations in the symmetric case. Such an unexpected behavior is in sharp contrast to the previously known results on random tries, that the size is totally positively correlated to the internal path length and that both tend to the same normal limit law. These two dependence examples provide concrete instances of bivariate normal distributions (as limit laws) whose components have correlation either zero or one or periodically oscillating. Moreover, the same type of behavior is also clarified for other classes of digital trees such as bucket digital trees and Patricia tries.

We study how to sample paths of a random walk up to the first time it crosses a fixed barrier, in the setting where the step sizes are independent and identically distributed with negative mean and have a regularly varying right tail. We introduce a desirable property for a change of measure to be suitable for exact simulation. We study whether the change of measure of Blanchet and Glynn (2008) satisfies this property and show that it does so if and only if the tail index α of the right tail lies in the interval (1, 3/2).

We consider community detection in degree-corrected stochastic block models. We propose a spectral clustering algorithm based on a suitably normalized adjacency matrix. We show that this algorithm consistently recovers the block membership of all but a vanishing fraction of nodes, in the regime where the lowest degree is of order log(n) or higher. Recovery succeeds even for very heterogeneous degree distributions. The algorithm does not rely on parameters as input. In particular, it does not need to know the number of communities.

A class of games for finding a leader among a group of candidates is studied in detail. This class covers games based on coin tossing and rock-paper-scissors as special cases and its complexity exhibits similar stochastic behaviors: either of logarithmic mean and bounded variance or of exponential mean and exponential variance. Many applications are also discussed.

In this paper, a new stopping rule is proposed for orthogonal multi-matching pursuit (OMMP). We show that, for ℓ2 bounded noise case, OMMP with the new stopping rule can recover the true support of any K-sparse signal x from noisy measurements y = Фx + e in at most K iterations, provided that all the nonzero components of x and the elements of the matrix Ф satisfy certain requirements. The proposed method can improve the existing result. In particular, for the noiseless case, OMMP can exactly recover any K-sparse signal under the same RIP condition.

The depth of a trie has been deeply studied when the source which produces the words is a simple source (a memoryless source or a Markov chain). When a source is simple but not an unbiased memoryless source, the expectation and the variance are both of logarithmic order and their dominant terms involve characteristic objects of the source, for instance the entropy. Moreover, there is an asymptotic Gaussian law, even though the speed of convergence towards the Gaussian law has not yet been precisely estimated. The present paper describes a ‘natural’ class of general sources, which does not contain any simple source, where the depth of a random trie, built on a set of words independently drawn from the source, has the same type of probabilistic behaviour as for simple sources: the expectation and the variance are both of logarithmic order and there is an asymptotic Gaussian law. There are precise asymptotic expansions for the expectation and the variance, and the speed of convergence toward the Gaussian law is optimal. The paper first provides analytical conditions on the Dirichlet series of probabilities of a general source under which this Gaussian law can be derived: a pole-free region where the series is of polynomial growth. In a second step, the paper focuses on sources associated with dynamical systems, called dynamical sources, where the Dirichlet series of probabilities is expressed with the transfer operator of the dynamical system. Then, the paper extends results due to Dolgopyat, already generalized by Baladi and Vallée, and shows that the previous analytical conditions are fulfilled for ‘most’ dynamical sources, provided that they ‘strongly differ’ from simple sources. Finally, the present paper describes a class of sources not containing any simple source, where the trie depth has the same type of probabilistic behaviour as for simple sources, even with more precise estimates.

We describe a general framework for realistic analysis of sorting algorithms, and we apply it to the average-case analysis of three basic sorting algorithms (QuickSort, InsertionSort, BubbleSort). Usually the analysis deals with the mean number of key comparisons, but here we view keys as words produced by the same source, which are compared via their symbols in lexicographic order. The ‘realistic’ cost of the algorithm is now the total number of symbol comparisons performed by the algorithm, and, in this context, the average-case analysis aims to provide estimates for the mean number of symbol comparisons used by the algorithm. For sorting algorithms, and with respect to key comparisons, the average-case complexity of QuickSort is asymptotic to 2n log n, InsertionSort to n2/4 and BubbleSort to n2/2. With respect to symbol comparisons, we prove that their average-case complexity becomes Θ (n log2n), Θ(n2), Θ (n2 log n). In these three cases, we describe the dominant constants which exhibit the probabilistic behaviour of the source (namely entropy and coincidence) with respect to the algorithm.

This paper studies a special type of binomial splitting process. Such a process can be used to model a high dimensional corner parking problem as well as determining the depth of random PATRICIA (practical algorithm to retrieve information coded in alphanumeric) tries, which are a special class of digital tree data structures. The latter also has natural interpretations in terms of distinct values in independent and identically distributed geometric random variables and the occupancy problem in urn models. The corresponding distribution is marked by a logarithmic mean and a bounded variance, which is oscillating, if the binomial parameter p is not equal to ½, and asymptotic to one in the unbiased case. Also, the limiting distribution does not exist as a result of the periodic fluctuations.

We consider redundant binary joint digital expansions of integer vectors. The redundancy is used to minimize the Hamming weight, i.e., the number of non-zero digit vectors. This leads to efficient linear combination algorithms in abelian groups, which are used in elliptic curve cryptography, for instance.

If the digit set is a set of contiguous integers containing zero, a special syntactical condition is known to minimize the weight. We analyse the optimal weight of all non-negative integer vectors with maximum entry less than N. The expectation and the variance are given with a main term and a periodic fluctuation in the second-order term. Finally, we prove asymptotic normality.