uu.seUppsala University Publications
Change search
Link to record
Permanent link

Direct link
BETA
Janson, Svante
Publications (10 of 182) Show all publications
Janson, S. (2018). Asymptotics Of Fluctuations In Crump-Mode-Jagers Processes: The Lattice Case. Advances in Applied Probability, 50(A), 141-171
Open this publication in new window or tab >>Asymptotics Of Fluctuations In Crump-Mode-Jagers Processes: The Lattice Case
2018 (English)In: Advances in Applied Probability, ISSN 0001-8678, E-ISSN 1475-6064, Vol. 50, no A, p. 141-171Article in journal (Refereed) Published
Abstract [en]

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.

Keywords
Crump-Mode-Jagers process, age distribution
National Category
Probability Theory and Statistics
Identifiers
urn:nbn:se:uu:diva-377288 (URN)10.1017/apr.2018.76 (DOI)000457454600014 ()
Available from: 2019-02-18 Created: 2019-02-18 Last updated: 2019-02-18Bibliographically approved
Hatami, H., Janson, S. & Szegedy, B. (2018). Graph properties, graph limits, and entropy. Journal of Graph Theory, 87(2), 208-229
Open this publication in new window or tab >>Graph properties, graph limits, and entropy
2018 (English)In: Journal of Graph Theory, ISSN 0364-9024, E-ISSN 1097-0118, Vol. 87, no 2, p. 208-229Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
WILEY, 2018
Keywords
graph limit, growth rate, regularity lemma, AMS Subject Classification: 05C99
National Category
Mathematics
Identifiers
urn:nbn:se:uu:diva-338952 (URN)10.1002/jgt.22152 (DOI)000417854500006 ()
Funder
Knut and Alice Wallenberg Foundation
Available from: 2018-01-18 Created: 2018-01-18 Last updated: 2018-01-18Bibliographically approved
Janson, S. & Pouyanne, N. (2018). Moment convergence of balanced Polya processes. Electronic Journal of Probability, 23, Article ID 34.
Open this publication in new window or tab >>Moment convergence of balanced Polya processes
2018 (English)In: Electronic Journal of Probability, ISSN 1083-6489, E-ISSN 1083-6489, Vol. 23, article id 34Article in journal (Refereed) Published
Abstract [en]

It is known that in an irreducible small Polya urn process, the composition of the urn after suitable normalization converges in distribution to a normal distribution. We show that if the urn also is balanced, this normal convergence holds with convergence of all moments, thus giving asymptotics of (central) moments.

Keywords
Polya urns, Polya processes, moment convergence
National Category
Probability Theory and Statistics
Identifiers
urn:nbn:se:uu:diva-355480 (URN)10.1214/17-EJP80 (DOI)000431687400002 ()
Funder
Knut and Alice Wallenberg Foundation
Available from: 2018-06-29 Created: 2018-06-29 Last updated: 2018-06-29Bibliographically approved
Cai, X. S. & Janson, S. (2018). Non-fringe subtrees in conditioned Galton-Watson trees. The Electronic Journal of Combinatorics, 25(3), Article ID P3.40.
Open this publication in new window or tab >>Non-fringe subtrees in conditioned Galton-Watson trees
2018 (English)In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 25, no 3, article id P3.40Article in journal (Refereed) Published
Abstract [en]

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.

National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-365652 (URN)000444053700003 ()
Funder
Knut and Alice Wallenberg Foundation
Available from: 2018-11-14 Created: 2018-11-14 Last updated: 2018-11-14Bibliographically approved
Janson, S. (2018). On Edge Exchangeable Random Graphs. Journal of statistical physics, 173(3-4), 448-484
Open this publication in new window or tab >>On Edge Exchangeable Random Graphs
2018 (English)In: Journal of statistical physics, ISSN 0022-4715, E-ISSN 1572-9613, Vol. 173, no 3-4, p. 448-484Article in journal (Refereed) Published
Abstract [en]

We study a recent model for edge exchangeable random graphs introduced by Crane and Dempsey; in particular we study asymptotic properties of the random simple graph obtained by merging multiple edges. We study a number of examples, and show that the model can produce dense, sparse and extremely sparse random graphs. One example yields a power-law degree distribution. We give some examples where the random graph is dense and converges a.s. in the sense of graph limit theory, but also an example where a.s. every graph limit is the limit of some subsequence. Another example is sparse and yields convergence to a non-integrable generalized graphon defined on (0, infinity).

Keywords
Edge exchangeable random graphs, Graphons, Dense and sparse graph limits
National Category
Probability Theory and Statistics
Identifiers
urn:nbn:se:uu:diva-371552 (URN)10.1007/s10955-017-1832-9 (DOI)000450490500002 ()
Funder
Knut and Alice Wallenberg Foundation
Available from: 2018-12-21 Created: 2018-12-21 Last updated: 2018-12-21Bibliographically approved
Janson, S. & Warnke, L. (2018). On the critical probability in percolation. Electronic Journal of Probability, 23, Article ID 1.
Open this publication in new window or tab >>On the critical probability in percolation
2018 (English)In: Electronic Journal of Probability, ISSN 1083-6489, E-ISSN 1083-6489, Vol. 23, article id 1Article in journal (Refereed) Published
Abstract [en]

For percolation on finite transitive graphs, Nachmias and Peres suggested a characterization of the critical probability based on the logarithmic derivative of the susceptibility. As a first test-case, we study their suggestion for the Erdos-Renyi random graph G(n,p), and confirm that the logarithmic derivative has the desired properties: (i) its maximizer lies inside the critical window p = 1/n + Theta(n(-4/3)), and (ii) the inverse of its maximum value coincides with the Theta(n(-4/3))-width of the critical window. We also prove that the maximizer is not located at p = 1/n or p = 1/(n - 1), refuting a speculation of Peres.

Place, publisher, year, edition, pages
UNIV WASHINGTON, DEPT MATHEMATICS, 2018
Keywords
random graph, percolation, phase transition, critical probability, critical window
National Category
Probability Theory and Statistics
Identifiers
urn:nbn:se:uu:diva-342453 (URN)10.1214/17-EJP52 (DOI)000422878600001 ()
Funder
Knut and Alice Wallenberg Foundation
Available from: 2018-02-21 Created: 2018-02-21 Last updated: 2018-02-21Bibliographically approved
Janson, S. (2018). Renewal theory for asymmetric U-statistics. Electronic Journal of Probability, 23, Article ID 129.
Open this publication in new window or tab >>Renewal theory for asymmetric U-statistics
2018 (English)In: Electronic Journal of Probability, ISSN 1083-6489, E-ISSN 1083-6489, Vol. 23, article id 129Article in journal (Refereed) Published
Abstract [en]

We extend a functional limit theorem for symmetric U-statistics [Miller and Sen, 1972] to asymmetric U-statistics, and use this to show some renewal theory results for asymmetric U-statistics. Some applications are given.

Place, publisher, year, edition, pages
UNIV WASHINGTON, DEPT MATHEMATICS, 2018
Keywords
U-statistics, renewal theory, functional limit theorems
National Category
Probability Theory and Statistics
Identifiers
urn:nbn:se:uu:diva-372907 (URN)10.1214/18-EJP252 (DOI)000453825700001 ()
Funder
Knut and Alice Wallenberg Foundation
Available from: 2019-01-11 Created: 2019-01-11 Last updated: 2019-01-11Bibliographically approved
Janson, S., Riordan, O. & Warnke, L. (2018). Sesqui-type branching processes. Stochastic Processes and their Applications, 128(11), 3628-3655
Open this publication in new window or tab >>Sesqui-type branching processes
2018 (English)In: Stochastic Processes and their Applications, ISSN 0304-4149, E-ISSN 1879-209X, Vol. 128, no 11, p. 3628-3655Article in journal (Refereed) Published
Abstract [en]

We consider branching processes consisting of particles (individuals) of two types (type L and type S) in which only particles of type L have offspring, proving estimates for the survival probability and the (tail of) the distribution of the total number of particles. Such processes are in some sense closer to single than to multi-type branching processes. Nonetheless, the second, barren, type complicates the analysis significantly. The results proved here (about point and survival probabilities) are a key ingredient in the analysis of bounded-size Achlioptas processes in a recent paper by the last two authors.

Keywords
Sesqui-type branching processes, Survival probability, Point probability
National Category
Probability Theory and Statistics
Identifiers
urn:nbn:se:uu:diva-370017 (URN)10.1016/j.spa.2017.12.007 (DOI)000447816800002 ()
Funder
Knut and Alice Wallenberg Foundation
Available from: 2019-01-07 Created: 2019-01-07 Last updated: 2019-01-07Bibliographically approved
Janson, S. (2018). Tail bounds for sums of geometric and exponential variables. Statistics and Probability Letters, 135, 1-6
Open this publication in new window or tab >>Tail bounds for sums of geometric and exponential variables
2018 (English)In: Statistics and Probability Letters, ISSN 0167-7152, E-ISSN 1879-2103, Vol. 135, p. 1-6Article in journal (Refereed) Published
Abstract [en]

We give explicit bounds for the tail probabilities for sums of independent geometric or exponential variables, possibly with different parameters.

Place, publisher, year, edition, pages
ELSEVIER SCIENCE BV, 2018
Keywords
Geometric distribution, Exponential distribution, Tail bounds
National Category
Probability Theory and Statistics
Identifiers
urn:nbn:se:uu:diva-347533 (URN)10.1016/j.spl.2017.11.017 (DOI)000424959400001 ()
Funder
Knut and Alice Wallenberg Foundation
Available from: 2018-04-04 Created: 2018-04-04 Last updated: 2018-04-04Bibliographically approved
Hwang, H.-K., Janson, S. & Tsai, T.-H. (2017). Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications. ACM Transactions on Algorithms, 13(4), Article ID 47.
Open this publication in new window or tab >>Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications
2017 (English)In: ACM Transactions on Algorithms, ISSN 1549-6325, E-ISSN 1549-6333, Vol. 13, no 4, article id 47Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
ASSOC COMPUTING MACHINERY, 2017
Keywords
Analysis of algorithms, recurrence relation, asymptotic linearity, periodic oscillation, identity, master theorems, functional equation, asymptotic approximation, uniform continuity, additivity, sensitivity analysis
National Category
Computer Sciences Mathematics
Identifiers
urn:nbn:se:uu:diva-340477 (URN)10.1145/3127585 (DOI)000419242000004 ()
Available from: 2018-01-31 Created: 2018-01-31 Last updated: 2018-01-31Bibliographically approved
Organisations

Search in DiVA

Show all publications