SwePub - sökning: WFRF:(Janson Svante 1955 )

Numrering	Referens	Omslagsbild	Hitta
1.	Janson, Svante, 1955-, et al. (författare) Proportionella val inom kommunfullmäktige 2019 Rapport (övrigt vetenskapligt/konstnärligt)abstract Vi diskuterar två olika problem som kan uppstå vid proportionella val i kommunfullmäktige och regionfullmäktige når ett parti försöker en kupp genom att utan samtycke gå i kartell med ett annat parti vid val till nämnd eller styrelse, vilket aktualiserades i åtminstone ett par fall hösten 2018. Det första problemet är vad sådana oönskade valkarteller kan få för effekter, och vilka möjligheter det finns för ett parti att skydda sig från att bli del i en oönskad valkartell. Det andra problemet är att i en sådan valkartell kan ett parti genom att splittra upp sina kandidater strategiskt på flera olika valsedlar få fler platser i en nämnd är vad som är proportionellt. Detta andra problem bottnar i att lagen om proportionella val stipulerar att Thieles metod skall användas för fördelning inom kartellen. På detta problem finns en enkel matematisk lösning och vi argumenterar för att man skall byta till Phragméns metod som används för motsvarande val till utskott i riksdagen.
2.	Ahlberg, Daniel, et al. (författare) Competing first passage percolation on random graphs with finite variance degrees 2019 Ingår i: Random structures & algorithms (Print). - : Wiley. - 1042-9832 .- 1098-2418. ; 55:3, s. 545-559 Tidskriftsartikel (refereegranskat)abstract We study the growth of two competing infection types on graphs generated by the configuration model with a given degree sequence. Starting from two vertices chosen uniformly at random, the infection types spread via the edges in the graph in that an uninfected vertex becomes type 1 (2) infected at rate lambda(1) (lambda(2)) times the number of nearest neighbors of type 1 (2). Assuming (essentially) that the degree of a randomly chosen vertex has finite second moment, we show that if lambda(1) = lambda(2), then the fraction of vertices that are ultimately infected by type 1 converges to a continuous random variable V is an element of (0,1), as the number of vertices tends to infinity. Both infection types hence occupy a positive (random) fraction of the vertices. If lambda(1) not equal lambda(2), on the other hand, then the type with the larger intensity occupies all but a vanishing fraction of the vertices. Our results apply also to a uniformly chosen simple graph with the given degree sequence.
3.	Ahlberg, Daniel, et al. (författare) Competition in growth and urns 2019 Ingår i: Random structures & algorithms (Print). - : Wiley. - 1042-9832 .- 1098-2418. ; 54:2, s. 211-227 Tidskriftsartikel (refereegranskat)abstract We study survival among two competing types in two settings: a planar growth model related to two-neighbor bootstrap percolation, and a system of urns with graph-based interactions. In the planar growth model, uncolored sites are given a color at rate 0, 1 or infinity, depending on whether they have zero, one, or at least two neighbors of that color. In the urn scheme, each vertex of a graph G has an associated urn containing some number of either blue or red balls ( but not both). At each time step, a ball is chosen uniformly at random from all those currently present in the system, a ball of the same color is added to each neighboring urn, and balls in the same urn but of different colors annihilate on a one-for-one basis. We show that, for every connected graph G and every initial configuration, only one color survives almost surely. As a corollary, we deduce that in the two-type growth model on Z(2), one of the colors only infects a finite number of sites with probability one. We also discuss generalizations to higher dimensions and multi-type processes, and list a number of open problems and conjectures.
4.	Ahlberg, Daniel, et al. (författare) To fixate or not to fixate in two-type annihilating branching random walks 2021 Ingår i: Annals of Probability. - : Institute of Mathematical Statistics. - 0091-1798 .- 2168-894X. ; 49:5, s. 2637-2667 Tidskriftsartikel (refereegranskat)abstract We study a model of competition between two types evolving as branching random walks on Z(d). The two types are represented by red and blue balls, respectively, with the rule that balls of different colour annihilate upon contact. We consider initial configurations in which the sites of Z(d) contain one ball each which are independently coloured red with probability p and blue otherwise. We address the question of fixation, referring to the sites and eventually settling for a given colour or not. Under a mild moment condition on the branching rule, we prove that the process will fixate almost surely for p not equal 1/2 and that every site will change colour infinitely often almost surely for the balanced initial condition p = 1/2.
5.	Bandyopadhyay, Antar, et al. (författare) Strong convergence of infinite color balanced urns under uniform ergodicity 2020 Ingår i: Journal of Applied Probability. - : Cambridge University Press (CUP). - 0021-9002 .- 1475-6072. ; 57:3, s. 853-865 Tidskriftsartikel (refereegranskat)abstract We consider the generalization of the Polya urn scheme with possibly infinitely many colors, as introduced in [37], [4], [5], and [6]. For countably many colors, we prove almost sure convergence of the urn configuration under theuniform ergodicityassumption on the associated Markov chain. The proof uses a stochastic coupling of the sequence of chosen colors with abranching Markov chainon a weightedrandom recursive treeas described in [6], [31], and [26]. Using this coupling we estimate the covariance between any two selected colors. In particular, we re-prove the limit theorem for the classical urn models with finitely many colors.
6.	Barbour, Andrew, et al. (författare) A functional combinatorial central limit theorem 2009 Ingår i: Electronic Journal of Probability. - 1083-6489. ; 14, s. 2352-2370 Tidskriftsartikel (refereegranskat)abstract The paper establishes a functional version of the Hoeffding combinatorial central limit theorem. First, a pre-limiting Gaussian process approximation is defined, and is shown to be at a distance of the order of the Lyapounov ratio from the original random process. Distance is measured by comparison of expectations of smooth functionals of the processes, and the argument is by way of Stein's method. The pre-limiting process is then shown, under weak conditions, to converge to a Gaussian limit process. The theorem is used to describe the shape of random permutation tableaux.
7.	Berzunza Ojeda, Gabriel, et al. (författare) The distance profile of rooted and unrooted simply generated trees 2022 Ingår i: Combinatorics, probability & computing. - : Cambridge University Press. - 0963-5483 .- 1469-2163. ; 31:3, s. 368-410 Tidskriftsartikel (refereegranskat)abstract It is well known that the height profile of a critical conditioned Galton-Watson tree with finite offspring variance converges, after a suitable normalisation, to the local time of a standard Brownian excursion. In this work, we study the distance profile, defined as the profile of all distances between pairs of vertices. We show that after a proper rescaling the distance profile converges to a continuous random function that can be described as the density of distances between random points in the Brownian continuum random tree. We show that this limiting function a.s. is Holder continuous of any order alpha < 1, and that it is a.e. differentiable. We note that it cannot be differentiable at 0, but leave as open questions whether it is Lipschitz, and whether it is continuously differentiable on the half-line (0, infinity). The distance profile is naturally defined also for unrooted trees contrary to the height profile that is designed for rooted trees. This is used in our proof, and we prove the corresponding convergence result for the distance profile of random unrooted simply generated trees. As a minor purpose of the present work, we also formalize the notion of unrooted simply generated trees and include some simple results relating them to rooted simply generated trees, which might be of independent interest.
8.	Bhattacharya, Bhaswar B., et al. (författare) Fluctuations of subgraph counts in graphon based random graphs 2023 Ingår i: Combinatorics, probability & computing. - : Cambridge University Press. - 0963-5483 .- 1469-2163. ; 32:3, s. 428-464 Tidskriftsartikel (refereegranskat)abstract Given a graphon W and a finite simple graph H, with vertex set V(H), denote by X-n(H, W) the number of copies of H in a W-random graph on n vertices. The asymptotic distribution of X-n(H, W) was recently obtained by Hladky, Pelekis, and Sileikis [17] in the case where H is a clique. In this paper, we extend this result to any fixed graph H. Towards this we introduce a notion of H-regularity of graphons and show that if the graphon W is not H-regular, then Xn(H, W) has Gaussian fluctuations with scaling n(V(H)-1/2). On the other hand, if W is H-regular, then the fluctuations are of order n(V(H)-1) and the limiting distribution of X-n(H, W) can have both Gaussian and non-Gaussian components, where the non-Gaussian component is a (possibly) infinite weighted sum of centred chi-squared random variables with the weights determined by the spectral properties of a graphon derived from W. Our proofs use the asymptotic theory of generalised U-statistics developed by Janson and Nowicki [22]. We also investigate the structure of H-regular graphons for which either the Gaussian or the non-Gaussian component of the limiting distribution (but not both) is degenerate. Interestingly, there are also H-regular graphons W for which both the Gaussian or the non-Gaussian components are degenerate, that is, X-n(H, W) has a degenerate limit even under the scaling n(\|V(H)\|-1). We give an example of this degeneracy with H = K-1,K-3 (the 3-star) and also establish non-degeneracy in a few examples. This naturally leads to interesting open questions on higher order degeneracies.
9.	Björklund, Johan, et al. (författare) Approximation of subgraph counts in the uniform attachment model Annan publikation (övrigt vetenskapligt/konstnärligt)
10.	Bollobás, Béla, et al. (författare) Line-of-sight percolation 2009 Ingår i: Combinatorics, probability & computing. - 0963-5483 .- 1469-2163. ; 18:1-2, s. 83-106 Tidskriftsartikel (refereegranskat)abstract Given omega >= 1, let Z((omega))(2) be the graph with vertex Set Z(2) in which two vertices are joined if they agree in one coordinate and differ by at most omega in the other. (Thus Z((1))(2) is precisely Z(2).) Let p(c)(omega) be the critical probability for site percolation on Z((omega))(2) Extending recent results of Frieze, Kleinberg, Ravi and Debany, we show that lim(omega ->infinity) omega p(c)(omega) = log(3/2). We also prove analogues of this result for the n-by-n grid and in higher dimensions, the latter involving interesting connections to Gilbert's continuum percolation model. To prove our results, we explore the component of the origin in a certain non-standard way, and show that this exploration is well approximated by a certain branching random walk.
11.	Bollobás, Béla, et al. (författare) Monotone graph limits and quasimonotone graphs 2012 Ingår i: Internet Mathematics. - 1542-7951 .- 1944-9488. ; 8, s. 187-231 Tidskriftsartikel (refereegranskat)
12.	Bollobas, Bela, et al. (författare) Packing Random Graphs and Hypergraphs 2017 Ingår i: Random structures & algorithms (Print). - : WILEY. - 1042-9832 .- 1098-2418. ; 51:1, s. 3-13 Tidskriftsartikel (refereegranskat)abstract We determine to within a constant factor the threshold for the property that two random k-uniform hypergraphs with edge probability p have an edge-disjoint packing into the same vertex set. More generally, we allow the hypergraphs to have different densities. In the graph case, we prove a stronger result, on packing a random graph with a fixed graph.
13.	Brightwell, Graham, et al. (författare) The Greedy Independent Set in a Random Graph with Given Degrees 2017 Ingår i: Random structures & algorithms (Print). - : Wiley. - 1042-9832 .- 1098-2418. ; 51:4, s. 565-586 Tidskriftsartikel (refereegranskat)abstract We analyse the size of an independent set in a random graph on n vertices with specified vertex degrees, constructed via a simple greedy algorithm: order the vertices arbitrarily, and, for each vertex in turn, place it in the independent set unless it is adjacent to some vertex already chosen. We find the limit of the expected proportion of vertices in the greedy independent set as n (the jamming constant), expressed as an integral whose upper limit is defined implicitly, valid whenever the second moment of a random vertex degree is uniformly bounded. We further show that the random proportion of vertices in the independent set converges in probability to the jamming constant as n. The results hold under weaker assumptions in a random multigraph with given degrees constructed via the configuration model.
14.	Brill, Markus, et al. (författare) Phragmen's Voting Methods and Justified Representation 2017 Ingår i: Thirty-First AAAI Conference On Artificial Intelligence. - : Assoc Advancement Artificial Intelligence. ; , s. 406-413 Konferensbidrag (refereegranskat)abstract In the late 19th century, Lars Edvard Phragmen proposed a load-balancing approach for selecting committees based on approval ballots. We consider three committee voting rules resulting from this approach: two optimization variants-one minimizing the maximal load and one minimizing the variance of loads-and a sequential variant. We study Phragmen's methods from an axiomatic point of view, focussing on justified representation and related properties that have recently been introduced by Aziz et al. (2015a) and Sanchez-Fernandez et al. (2017). We show that the sequential variant satisfies proportional justified representation, making it the first known polynomial-time computable method with this property. Moreover, we show that the optimization variants satisfy perfect representation. We also analyze the computational complexity of Phragmen's methods and provide mixed- integer programming based algorithms for computing them.
15.	Brill, Markus, et al. (författare) Phragmén's voting methods and justified representation 2024 Ingår i: Mathematical programming. - : Springer. - 0025-5610 .- 1436-4646. ; 203:1-2, s. 47-76 Tidskriftsartikel (refereegranskat)abstract In the late 19th century, Swedish mathematician Edvard Phragmén proposed a load-balancing approach for selecting committees based on approval ballots. We consider three committee voting rules resulting from this approach: two optimization variants—one minimizing the maximum load and one minimizing the variance of loads—and a sequential variant. We study Phragmén's methods from an axiomatic point of view, focusing on properties capturing proportional representation. We show that the sequential variant satisfies proportional justified representation, which is a rare property for committee monotonic methods. Moreover, we show that the optimization variants satisfy perfect representation. We also analyze the computational complexity of Phragmén's methods and provide mixed-integer programming based algorithms for computing them.
16.	Cai, Xing Shi, et al. (författare) Inversions in Split Trees and Conditional Galton-Watson Treest 2019 Ingår i: Combinatorics, probability & computing. - 0963-5483 .- 1469-2163. ; 28:3, s. 335-364 Tidskriftsartikel (refereegranskat)abstract We study I(T), the number of inversions in a tree T with its vertices labelled uniformly at random, which is a generalization of inversions in permutations. We first show that the cumulants of I(T) have explicit formulas involving the k-total common ancestors of T (an extension of the total path length). Then we consider X-n, the normalized version of I(T-n), for a sequence of trees T-n. For fixed T-n's, we prove a sufficient condition for X-n to converge in distribution. As an application, we identify the limit of X-n for complete b-ary trees. For T(n )being split trees [16], we show that X-n converges to the unique solution of a distributional equation. Finally, when T-n's are conditional Galton-Watson trees, we show that X-n converges to a random variable defined in terms of Brownian excursions. By exploiting the connection between inversions and the total path length, we are able to give results that significantly strengthen and broaden previous work by Panholzer and Seitz [46].
17.	Cai, Xing Shi, et al. (författare) Non-fringe subtrees in conditioned Galton-Watson trees 2018 Ingår i: The Electronic Journal of Combinatorics. - 1097-1440 .- 1077-8926. ; 25:3 Tidskriftsartikel (refereegranskat)abstract We study S(T-n), the number of subtrees in a conditioned Galton-Watson tree of size n. With two very different methods, we show that log(S(T-n)) has a Central Limit Law and that the moments of S(T-n) are of exponential scale.
18.	Diaconis, Persi, et al. (författare) Threshold graph limits and random threshold graphs 2008 Ingår i: Internet Mathematics. - 1542-7951. ; 5:3, s. 267-320 Tidskriftsartikel (refereegranskat)
19.	Drmota, Michael, et al. (författare) A functional limit theorem for the profile of search trees 2008 Ingår i: The Annals of Applied Probability. - 1050-5164 .- 2168-8737. ; 18:1, s. 288-233 Tidskriftsartikel (refereegranskat)abstract We study the profile X-n,X-k of random search trees including binary search trees and m-ary search trees. Our main result is a functional limit theorem of the normalized profile X-n,X-k/EXn,k for k = [alpha logn] in a certain range of alpha. A central feature of the proof is the use of the contraction method to prove convergence in distribution of certain random analytic functions in a complex domain. This is based on a general theorem concerning the contraction method for random variables in an infinite-dimensional Hilbert space. As part of the proof, we show that the Zolotarev metric is complete for a Hilbert space.
20.	Fill, James Allen, et al. (författare) Precise logarithmic asymptotics for the right tails of some limit random variables for random trees 2009 Ingår i: Annals of Combinatorics. - : Springer Science and Business Media LLC. - 0218-0006 .- 0219-3094. ; 12:4, s. 403-416 Tidskriftsartikel (refereegranskat)abstract For certain random variables that arise as limits of functionals of random finite trees, we obtain precise asymptotics for the logarithm of the right-hand tail. Our results are based on the facts (i) that the random variables we study can be represented as functionals of a Brownian excursion and (ii) that a large deviation principle with good rate function is known explicitly for Brownian excursion. Examples include limit distributions of the total path length and of the Wiener index in conditioned Galton-Watson trees (also known as simply generated trees). In the case of Wiener index (where we recover results proved by Svante Janson and Philippe Chassaing by a different method) and for some other examples, a key constant is expressed as the solution to a certain optimization problem, but the constant's precise value remains unknown.
21.	Fill, James Allen, et al. (författare) The sum of powers of subtree sizes for conditioned Galton-Watson trees 2022 Ingår i: Electronic Journal of Probability. - : Institute of Mathematical Statistics. - 1083-6489. ; 27 Tidskriftsartikel (refereegranskat)abstract We study the additive functional X-n(alpha) on conditioned Galton-Watson trees given, for arbitrary complex alpha, by summing the alpha th power of all subtree sizes. Allowing complex alpha is advantageous, even for the study of real alpha, since it allows us to use powerful results from the theory of analytic functions in the proofs. For Re alpha < 0, we prove that Xn(alpha), suitably normalized, has a complex normal limiting distribution; moreover, as processes in alpha, the weak convergence holds in the space of analytic functions in the left half-plane. We establish, and prove similar process-convergence extensions of, limiting distribution results for alpha in various regions of the complex plane. We focus mainly on the case where Re alpha > 0, for which X-n(alpha), suitably normalized, has a limiting distribution that is not normal but does not depend on the offspring distribution xi of the conditioned Galton-Watson tree, assuming only that E xi = 1 and 0 < Var xi < oo. Under a weak extra moment assumption on xi, we prove that the convergence extends to moments, ordinary and absolute and mixed, of all orders. At least when Re alpha > 21, the limit random variable Y(alpha) can be expressed as a function of a normalized Brownian excursion.
22.	Grimmett, Geoffrey, et al. (författare) Random even graphs 2009 Ingår i: The Electronic Journal of Combinatorics. - 1097-1440 .- 1077-8926. ; 16:1, s. R46- Tidskriftsartikel (refereegranskat)abstract We study a random even subgraph of a finite graph G with a general edge-weight p is an element of (0, 1). We demonstrate how it may be obtained from a certain random-cluster measure on G, and we propose a sampling algorithm based on coupling from the past. A random even subgraph of a planar lattice undergoes a phase transition at the parameter-value 1/2p(c), where p(c) is the critical point of the q = 2 random-cluster model on the dual lattice. The properties of such a graph are discussed, and are related to Schramm-Lowner evolutions (SLE).
23.	Hatami, Hamed, et al. (författare) Graph properties, graph limits, and entropy 2018 Ingår i: Journal of Graph Theory. - : WILEY. - 0364-9024 .- 1097-0118. ; 87:2, s. 208-229 Tidskriftsartikel (refereegranskat)abstract We study the relation between the growth rate of a graph property and the entropy of the graph limits that arise from graphs with that property. In particular, for hereditary classes we obtain a new description of the coloring number, which by well-known results describes the rate of growth. We study also random graphs and their entropies. We show, for example, that if a hereditary property has a unique limiting graphon with maximal entropy, then a random graph with this property, selected uniformly at random from all such graphs with a given order, converges to this maximizing graphon as the order tends to infinity.
24.	Hitczenko, Pawel, et al. (författare) Asymptotic normality of statistics on permutation tableaux 2010 Ingår i: Algorithmic Probability and Combinatorics. - Providence, RI : American Math. Society. ; , s. 83-104 Konferensbidrag (refereegranskat)
25.	Holmgren, Cecilia, 1984-, et al. (författare) Fringe trees, Crump-Mode-Jagers branching processes and m-ary search trees 2017 Ingår i: Probability Surveys. - 1549-5787. ; 14, s. 53-154 Tidskriftsartikel (refereegranskat)abstract This survey studies asymptotics of random fringe trees and extended fringe trees in random trees that can be constructed as family trees of a Crump-Mode-Jagers branching process, stopped at a suitable time. This includes random recursive trees, preferential attachment trees, fragmentation trees, binary search trees and (more generally) m-ary search trees, as well as some other classes of random trees.We begin with general results, mainly due to Aldous (1991) and Jagers and Nerman (1984). The general results are applied to fringe trees and extended fringe trees for several particular types of random trees, where the theory is developed in detail. In particular, we consider fringe trees of m-ary search trees in detail; this seems to be new.Various applications are given, including degree distribution, protected nodes and maximal clades for various types of random trees. Again, we emphasise results for m-ary search trees, and give for example new results on protected nodes in m-ary search trees.A separate section surveys results on the height of the random trees due to Devroye (1986), Biggins (1995, 1997) and others.This survey contains well-known basic results together with some additional general results as well as many new examples and applications for various classes of random trees.
26.	Holmgren, Cecilia, 1984-, et al. (författare) Multivariate normal limit laws for the numbers of fringe subtrees in m-ary search trees and preferential attachment trees 2017 Ingår i: The Electronic Journal of Combinatorics. - : ELECTRONIC JOURNAL OF COMBINATORICS. - 1097-1440 .- 1077-8926. ; 24:2 Tidskriftsartikel (refereegranskat)abstract We study fringe subtrees of random m-ary search trees and of preferential attachment trees, by putting them in the context of generalised Polya urns. In particular we show that for the random m-ary search trees with m <= 26 and for the linear preferential attachment trees, the number of fringe subtrees that are isomorphic to an arbitrary fixed tree T converges to a normal distribution; more generally, we also prove multivariate normal distribution results for random vectors of such numbers for different fringe subtrees. Furthermore, we show that the number of protected nodes in random m-ary search trees for m <= 26 has asymptotically a normal distribution.
27.	Holroyd, Alexander E., et al. (författare) Minimal matchings of point processes 2022 Ingår i: Probability Theory and Related Fields. - : Springer Science and Business Media LLC. - 0178-8051 .- 1432-2064. ; 184:1-2, s. 571-611 Tidskriftsartikel (refereegranskat)abstract Suppose that red and blue points form independent homogeneous Poisson processes of equal intensity in R-d. For a positive (respectively, negative) parameter gamma we consider red-blue matchings that locally minimize (respectively, maximize) the sum of gamma th powers of the edge lengths, subject to locally minimizing the number of unmatched points. The parameter can be viewed as a measure of fairness. The limit gamma -> -infinity is equivalent to Gale-Shapley stable matching. We also consider limits as gamma approaches 0, 1-, 1+ and infinity. We focus on dimension d = 1. We prove that almost surely no such matching has unmatched points. (This question is open for higher d). For each gamma < 1 we establish that there is almost surely a unique such matching, and that it can be expressed as a finitary factor of the points. Moreover, its typical edge length has finite rth moment if and only if r < 1 /2. In contrast, for gamma = 1 there are uncountably many matchings, while for gamma > 1 there are countably many, but it is impossible to choose one in a translation-invariant way. We obtain existence results in higher dimensions (covering many but not all cases). We address analogous questions for one-colour matchings also.
28.	Hwang, Hsien-Kuei, et al. (författare) Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half : Theory and Applications 2017 Ingår i: ACM Transactions on Algorithms. - : ASSOC COMPUTING MACHINERY. - 1549-6325 .- 1549-6333. ; 13:4 Tidskriftsartikel (refereegranskat)abstract Divide-and-conquer recurrences of the form f (n) = f(left perpendicular n/2 right perpendicular) + f(vertical bar n/2 vertical bar) + g(n) (n >= 2), with g(n) and f(1) given, appear very frequently in the analysis of computer algorithms and related areas. While most previous methods and results focus on simpler crude approximation to the solution, we show that the solution always satisfies the simple identity f(n) = nP(log(2) n) - Q(n) under an optimum (iff) condition on g(n). This form is not only an identity but also an asymptotic expansion because Q(n) is of a smaller order than linearity. Explicit forms for the continuous periodic function P are provided. We show how our results can be easily applied to many dozens of concrete examples collected from the literature and how they can be extended in various directions. Our method of proof is surprisingly simple and elementary but leads to the strongest types of results for all examples to which our theory applies.
29.	Hwang, Hsien-Kuei, et al. (författare) Identities and periodic oscillations of divide-and-conquer recurrences splitting at half 2024 Ingår i: Advances in Applied Mathematics. - : Elsevier. - 0196-8858 .- 1090-2074. ; 155 Tidskriftsartikel (refereegranskat)abstract We study divide-and-conquer recurrences of the form f(n) = alpha f ([n/2]) + beta f(n/2) + g(n) (n >= 2), with g(n) and f (1) given, where alpha, beta >= 0 with alpha + beta > 0; such recurrences appear often in the analysis of computer algorithms, numeration systems, combinatorial sequences, and related areas. We show under an optimum (iff) condition on g(n) that the solution f always satisfies a simple identity f(n) = n(log2(alpha+beta)) P(log(2) n) - Q(n), where P is a periodic function and Q(n) is of a smaller order than the dominant term. This form is thus not only an identity but also an asymptotic expansion. Explicit forms for the continuity of the periodic function P are provided, together with a few other smoothness properties. We show how our results can be easily applied to many dozens of concrete examples collected from the literature, and how they can be extended in various directions. Our method of proof is surprisingly simple and elementary, but leads to the strongest types of results for all examples to which our theory applies. (c) 2023 Elsevier Inc. All rights reserved.
30.	Hwang, Hsien-Kuei, et al. (författare) Local limit theorems for finite and infinite urn models 2008 Ingår i: Annals of Probability. - 0091-1798 .- 2168-894X. ; 36:3, s. 992-1022 Tidskriftsartikel (refereegranskat)abstract Local limit theorems are derived for the number of occupied urns in general finite and infinite urn models under the minimum condition that the variance tends to infinity. Our results represent an optimal improvement over previous ones for normal approximation.
31.	Janson, Svante, 1955- (författare) A graphon counter example 2020 Ingår i: Discrete Mathematics. - : ELSEVIER. - 0012-365X .- 1872-681X. ; 343:6 Tidskriftsartikel (refereegranskat)abstract We give an example of a graphon such that there is no equivalent graphon with a degree function that is (weakly) increasing.
32.	Janson, Svante, 1955-, et al. (författare) A modified bootstrap percolation on a random graph coupled with a lattice 2019 Ingår i: Discrete Applied Mathematics. - : Elsevier BV. - 0166-218X .- 1872-6771. ; 258, s. 152-165 Tidskriftsartikel (refereegranskat)abstract In this paper a random graph model G(ZN2.pd) is introduced, which is a combination of fixed torus grid edges in (z/NZ)(2) and some additional random ones. The random edges are called long, and the probability of having a long edge between vertices u, v is an element of (Z/NZ)(2) with graph distance d on the torus grid is p(d) = c/Nd, where c is some constant. We show that, whp, the diameter D(G(zN2.pd)) = Theta(log N). Moreover, we consider a modified non-monotonous bootstrap percolation on G(ZN2.pd). We prove the presence of phase transitions in mean-field approximation and provide Fairly sharp bounds on the error of the critical parameters.
33.	Janson, Svante, 1955-, et al. (författare) A new approach to the giant component problem 2009 Ingår i: Random structures & algorithms (Print). - : Wiley. - 1042-9832 .- 1098-2418. ; 34:2, s. 197-216 Tidskriftsartikel (refereegranskat)abstract We study the largest component of a random (multi)graph on n vertices with a given degree sequence. We let n → ∞. Then, under some regularity conditions on the degree sequences, we give conditions on the asymptotic shape of the degree sequence that imply that with high probability all the components are small, and other conditions that imply that with high probability there is a giant component and the sizes of its vertex and edge sets satisfy a law of large numbers; under suitable assumptions these are the only two possibilities. In particular, we recover the results by Molloy and Reed on the size of the largest component in a random graph with a given degree sequence. We further obtain a new sharp result for the giant component just above the threshold, generalizing the case of G(n,p) with np = 1 + ω(n)n−1/3, where ω(n) → ∞ arbitrarily slowly. Our method is based on the properties of empirical distributions of independent random variables, and leads to simple proofs
34.	Janson, Svante, 1955-, et al. (författare) A piecewise contractive dynamical system and Phragmèn's election method 2019 Ingår i: Bulletin de la Société Mathématique de France. - : FRENCH MATHEMATICAL SOC. - 0037-9484 .- 2102-622X. ; 147:3, s. 395-441 Tidskriftsartikel (refereegranskat)abstract We prove some basic results for a dynamical system given by a piece-wise linear and contractive map on the unit interval that takes two possible values at a point of discontinuity. We prove that there exists a universal limit cycle in the non-exceptional cases, and that the exceptional parameter set is very tiny in terms of gauge functions. The exceptional two-dimensional parameter is shown to have Hausdorff-dimension one. We also study the invariant sets and the limit sets; these are sometimes different and there are several cases to consider. In addition, we prove the existence of a unique invariant measure. We apply some of our results for the dynamical system, involving a study of rational and irrational rotation numbers, to a combinatorial problem involving an election method suggested by Phragmen, and we show that the proportion of elected seats for each party converges to a limit, which is a rational number except for a very small exceptional set of parameters.
35.	Janson, Svante, 1955- (författare) A.s. convergence for infinite colour Pólya urns associated with random walks 2021 Ingår i: Arkiv för matematik. - : INT PRESS BOSTON, INC. - 0004-2080 .- 1871-2487. ; 59:1, s. 87-123 Tidskriftsartikel (refereegranskat)abstract We consider Polya urns with infinitely many colours that are of a random walk type, in two related versions. We show that the colour distribution a.s., after rescaling, converges to a normal distribution, assuming only second moments on the offset distribution. This improves results by Bandyopadhyay and Thacker (2014-2017; convergence in probability), and Mailler and Marckert (2017; a.s. convergence assuming exponential moment).
36.	Janson, Svante, 1955-, et al. (författare) Absolutely continuous compensators 2011 Ingår i: International Journal of Theoretical and Applied Finance. - 0219-0249. ; 14, s. 335-351 Tidskriftsartikel (refereegranskat)
37.	Janson, Svante, 1955-, et al. (författare) An example of graph limits of growing sequences of random graphs 2013 Ingår i: Journal of Combinatorics. - 2156-3527 .- 2150-959X. ; 4:1, s. 67-80 Tidskriftsartikel (refereegranskat)
38.	Janson, Svante, 1955- (författare) Asymptotic normality for M-dependent and constrained U -statistics, with applications to pattern matching in random strings and permutations 2023 Ingår i: Advances in Applied Probability. - : Cambridge University Press. - 0001-8678 .- 1475-6064. ; 55:3, s. 841-894 Tidskriftsartikel (refereegranskat)abstract We study (asymmetric) -statistics based on a stationary sequence of -dependent variables; moreover, we consider constrained -statistics, where the defining multiple sum only includes terms satisfying some restrictions on the gaps between indices. Results include a law of large numbers and a central limit theorem, together with results on rate of convergence, moment convergence, functional convergence, and a renewal theory version.Special attention is paid to degenerate cases where, after the standard normalization, the asymptotic variance vanishes; in these cases non-normal limits occur after a different normalization.The results are motivated by applications to pattern matching in random strings and permutations. We obtain both new results and new proofs of old results.
39.	Janson, Svante, 1955- (författare) Asymptotic normality in random graphs with given vertex degrees 2020 Ingår i: Random structures & algorithms (Print). - : John Wiley & Sons. - 1042-9832 .- 1098-2418. ; 56:4, s. 1070-1116 Tidskriftsartikel (refereegranskat)abstract We consider random graphs with a given degree sequence and show, under weak technical conditions, asymptotic normality of the number of components isomorphic to a given tree, first for the random multigraph given by the configuration model and then, by a conditioning argument, for the simple uniform random graph with the given degree sequence. Such conditioning is standard for convergence in probability, but much less straightforward for convergence in distribution as here. The proof uses the method of moments, and is based on a new estimate of mixed cumulants in a case of weakly dependent variables. The result on small components is applied to give a new proof of a recent result by Barbour and Rollin on asymptotic normality of the size of the giant component in the random multigraph; moreover, we extend this to the random simple graph.
40.	Janson, Svante, 1955- (författare) Asymptotics Of Fluctuations In Crump-Mode-Jagers Processes : The Lattice Case 2018 Ingår i: Advances in Applied Probability. - : Cambridge University Press (CUP). - 0001-8678 .- 1475-6064. ; 50:A, s. 141-171 Tidskriftsartikel (refereegranskat)abstract Consider a supercritical Crump-Mode-Jagers process in which all births are at integer times (the lattice case). Let (mu) over cap (z) be the generating function of the intensity of the offspring process, and consider the complex roots of (mu) over cap (z) = 1. The root of smallest absolute value is e(-alpha) = 1/m, where alpha > 0 is the Malthusian parameter; let gamma* be the root of second smallest absolute value. Subject to some technical conditions, the second-order fluctuations of the age distribution exhibit one of three types of behaviour: (i) when gamma* > e(-alpha/2) = m(-1/2), they are asymptotically normal; (ii) when gamma* = e(-alpha/2), they are still asymptotically normal, but with a larger variance; and (iii) when gamma* < e(-alpha/2), the fluctuations are in general oscillatory and (degenerate cases excluded) do not converge in distribution. This trichotomy is similar to what has been observed in related situations, such as some other branching processes and for Polya urns. The results lead to a symbolic calculus describing the limits. The asymptotic results also apply to the total of other (random) characteristics of the population.
41.	Janson, Svante, 1955- (författare) Central limit theorems for additive functionals and fringe trees in tries 2022 Ingår i: Electronic Journal of Probability. - : Institute of Mathematical Statistics. - 1083-6489. ; 27, s. 1-63 Tidskriftsartikel (refereegranskat)abstract We give general theorems on asymptotic normality for additive functionals of random tries generated by a sequence of independent strings. These theorems are applied to show asymptotic normality of the distribution of random fringe trees in a random trie. Formulas for asymptotic mean and variance are given. In particular, the proportion of fringe trees of size k (defined as number of keys) is asymptotically, ignoring oscillations, c/(k(k - 1)) for k >= 2, where c = 1/(1 + H) with H the entropy of the letters. Another application gives asymptotic normality of the number of k-protected nodes in a random trie. For symmetric tries, it is shown that the asymptotic proportion of k-protected nodes (ignoring oscillations) decreases geometrically as k -> infinity.
42.	Janson, Svante, 1955-, et al. (författare) Continuous-time digital search tree and a border aggregation model 2022 Ingår i: Bernoulli. - : Bernoulli Society for Mathematical Statistics and Probability. - 1350-7265 .- 1573-9759. ; 28:4, s. 2563-2577 Tidskriftsartikel (övrigt vetenskapligt/konstnärligt)abstract We consider the continuous-time version of the random digital search tree, and construct a coupling with a border aggregation model as studied in Thacker and Volkov (Ann. Appl. Probab. 28 (2018) 1604???1633), showing a relation between the height of the tree and the time required for aggregation. This relation carries over to the corresponding discrete-time models. As a consequence we find a very precise asymptotic result for the time to aggregation, using recent results by Drmota et al. (Random Structures Algorithms 58 (2021) 430???467) for the digital search tree.
43.	Janson, Svante, 1955-, et al. (författare) Dismantling sparse random graphs 2008 Ingår i: Combinatorics, probability & computing. - 0963-5483 .- 1469-2163. ; 17:02, s. 259-264 Tidskriftsartikel (refereegranskat)abstract We consider the number of vertices that must be removed from a graph G in order that the remaining subgraph have no component with more than k vertices. Our principal observation is that, if G is a sparse random graph or a random regular graph on n vertices with n -> infinity, then the number in question is essentially the same for all values of k that satisfy both k -> infinity and k = o(n).
44.	Janson, Svante, 1955-, et al. (författare) Estimating global subgraph counts by sampling 2023 Ingår i: The Electronic Journal of Combinatorics. - : ELECTRONIC JOURNAL OF COMBINATORICS. - 1097-1440 .- 1077-8926. ; 30:2 Tidskriftsartikel (refereegranskat)abstract We give a simple proof of a generalization of an inequality for homomorphism counts by Sidorenko. A special case of our inequality says that if dv denotes the degree of a vertex v in a graph G and hom increment (H, G) denotes the number of homo-morphisms from a connected graph H on h vertices to G which map a particular vertex of H to a vertex v in G with dv ! increment , then ! hom increment (H, G) " v is an element of G dh-1 v 1dv! increment . We use this inequality to study the minimum sample size needed to estimate the number of copies of H in G by sampling vertices of G at random.
45.	Janson, Svante, 1955- (författare) Euler-Frobenius numbers and rounding 2013 Ingår i: Online Journal of Analytic Combinatorics. - 1931-3365. ; 8:5 Tidskriftsartikel (refereegranskat)
46.	Janson, Svante, 1955-, et al. (författare) Fluctuations of balanced urns with infinitely many colours 2023 Ingår i: Electronic Journal of Probability. - : Institute of Mathematical Statistics. - 1083-6489. ; 28, s. 1-72 Tidskriftsartikel (refereegranskat)abstract In this paper, we prove convergence and fluctuation results for measure-valued Polya processes (MVPPs, also known as Polya urns with infinitely-many colours). Our convergence results hold almost surely and in L2. Our fluctuation results are the first second-order results in the literature on MVPPs; they generalise classical fluctuation results from the literature on finitely-many-colour Polya urns. As in the finitely-manycolour case, the order and shape of the fluctuations depend on whether the "spectral gap is small or large". To prove these results, we show that MVPPs are stochastic approximations taking values in the set of measures on a measurable space E (the colour space). We then use martingale methods and standard operator theory to prove convergence and fluctuation results for these stochastic approximations.
47.	Janson, Svante, 1955-, et al. (författare) Graph limits and exchangeable random graphs 2008 Ingår i: Rendiconti di Matematica e delle sue Applicazioni. Serie VII. - 1120-7183. ; , s. 33-61 Tidskriftsartikel (refereegranskat)
48.	Janson, Svante, 1955- (författare) Graphons, cut norm and distance, couplings and rearrangements 2013 Ingår i: New York Journal of Mathematics. - 1076-9803. Tidskriftsartikel (refereegranskat)
49.	Janson, Svante, 1955-, et al. (författare) Hidden Words Statistics for Large Patterns 2021 Ingår i: The Electronic Journal of Combinatorics. - : ELECTRONIC JOURNAL OF COMBINATORICS. - 1097-1440 .- 1077-8926. ; 28:2 Tidskriftsartikel (refereegranskat)abstract We study here the so called subsequence pattern matching also known as hidden pattern matching in which one searches for a given pattern w of length m as a subsequence in a random text of length n. The quantity of interest is the number of occurrences of w as a subsequence (i.e., occurring in not necessarily consecutive text locations). This problem finds many applications from intrusion detection, to trace reconstruction, to deletion channel, and to DNA-based storage systems. In all of these applications, the pattern w is of variable length. To the best of our knowledge this problem was only tackled for a fixed length m = O(1). In our main result we prove that for m = o(n(1/3)) the number of subsequence occurrences is normally distributed. In addition, we show that under some constraints on the structure of w the asymptotic normality can be extended to m = o(root n). For a special pattern w consisting of the same symbol, we indicate that for m = o(n) the distribution of number of subsequences is either asymptotically normal or asymptotically log normal. After studying some special patterns (e.g., alternating) we conjecture that this dichotomy is true for all patterns. We use Hoeffding's projection method for U-statistics to prove our findings.
50.	Janson, Svante, 1955-, et al. (författare) Higher moments of Banach space valued random variables 2015 Ingår i: Memoirs of the American Mathematical Society. - : American Mathematical Society (AMS). - 0065-9266 .- 1947-6221. ; 238:1127, s. 1-110 Tidskriftsartikel (refereegranskat)abstract We define the k:th moment of a Banach space valued random variable as the expectation of its k: th tensor power; thus the moment (if it exists) is an element of a tensor power of the original Banach space. We study both the projective and injective tensor products, and their relation. Moreover, in order to be general and flexible, we study three different types of expectations: Bochner integrals, Pettis integrals and Dunford integrals. One of the problems studied is whether two random variables with the same injective moments (of a given order) necessarily have the same projective moments; this is of interest in applications. We show that this holds if the Banach space has the approximation property, but not in general. Several chapters are devoted to results in special Banach spaces, including Hilbert spaces, C(K) and D[0,1]. The latter space is non-separable, which complicates the arguments, and we prove various preliminary results on e.g. measurability in D[0,1] that we need. One of the main motivations of this paper is the application to Zolotarev metrics and their use in the contraction method. This is sketched in an appendix.

Skapa referenser, mejla, bekava och länka

Länka till träfflistan

Träfflista för sökning "WFRF:(Janson Svante 1955 ) "

Avgränsa träffmängd

År