uu.seUppsala University Publications

Please wait ... |

Link to record
http://uu.diva-portal.org/smash/person.jsf?pid=authority-person:12438 $(function(){PrimeFaces.cw("InputTextarea","widget_formSmash_upper_j_idt124_recordDirectLink",{id:"formSmash:upper:j_idt124:recordDirectLink",widgetVar:"widget_formSmash_upper_j_idt124_recordDirectLink",autoResize:true});}); $(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_upper_j_idt124_j_idt126",{id:"formSmash:upper:j_idt124:j_idt126",widgetVar:"widget_formSmash_upper_j_idt124_j_idt126",target:"formSmash:upper:j_idt124:permLink",showEffect:"blind",hideEffect:"fade",my:"right top",at:"right bottom",showCloseIcon:true});});

Permanent link

Direct link

Janson, Svante

Open this publication in new window or tab >>Asymptotics Of Fluctuations In Crump-Mode-Jagers Processes: The Lattice Case### Janson, Svante

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_0_j_idt195_some",{id:"formSmash:j_idt191:0:j_idt195:some",widgetVar:"widget_formSmash_j_idt191_0_j_idt195_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_0_j_idt195_otherAuthors",{id:"formSmash:j_idt191:0:j_idt195:otherAuthors",widgetVar:"widget_formSmash_j_idt191_0_j_idt195_otherAuthors",multiple:true}); 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]

##### 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 ()
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_0_j_idt195_j_idt367",{id:"formSmash:j_idt191:0:j_idt195:j_idt367",widgetVar:"widget_formSmash_j_idt191_0_j_idt195_j_idt367",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_0_j_idt195_j_idt373",{id:"formSmash:j_idt191:0:j_idt195:j_idt373",widgetVar:"widget_formSmash_j_idt191_0_j_idt195_j_idt373",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_0_j_idt195_j_idt379",{id:"formSmash:j_idt191:0:j_idt195:j_idt379",widgetVar:"widget_formSmash_j_idt191_0_j_idt195_j_idt379",multiple:true});
#####

Available from: 2019-02-18 Created: 2019-02-18 Last updated: 2019-02-18Bibliographically approved

Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Probability Theory.

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.

Open this publication in new window or tab >>Graph properties, graph limits, and entropy### Hatami, Hamed

### Janson, Svante

### Szegedy, Balazs

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_1_j_idt195_some",{id:"formSmash:j_idt191:1:j_idt195:some",widgetVar:"widget_formSmash_j_idt191_1_j_idt195_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_1_j_idt195_otherAuthors",{id:"formSmash:j_idt191:1:j_idt195:otherAuthors",widgetVar:"widget_formSmash_j_idt191_1_j_idt195_otherAuthors",multiple:true}); 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]

##### 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 ()
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_1_j_idt195_j_idt367",{id:"formSmash:j_idt191:1:j_idt195:j_idt367",widgetVar:"widget_formSmash_j_idt191_1_j_idt195_j_idt367",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_1_j_idt195_j_idt373",{id:"formSmash:j_idt191:1:j_idt195:j_idt373",widgetVar:"widget_formSmash_j_idt191_1_j_idt195_j_idt373",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_1_j_idt195_j_idt379",{id:"formSmash:j_idt191:1:j_idt195:j_idt379",widgetVar:"widget_formSmash_j_idt191_1_j_idt195_j_idt379",multiple:true});
#####

##### Funder

Knut and Alice Wallenberg Foundation
Available from: 2018-01-18 Created: 2018-01-18 Last updated: 2018-01-18Bibliographically approved

McGill Univ, Sch Comp Sci, Montreal, PQ, Canada..

Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Probability Theory.

Univ Toronto, Dept Math, St George St 40, Toronto, ON M5R 2E4, Canada..

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.

Open this publication in new window or tab >>Moment convergence of balanced Polya processes### Janson, Svante

### Pouyanne, Nicolas

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_2_j_idt195_some",{id:"formSmash:j_idt191:2:j_idt195:some",widgetVar:"widget_formSmash_j_idt191_2_j_idt195_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_2_j_idt195_otherAuthors",{id:"formSmash:j_idt191:2:j_idt195:otherAuthors",widgetVar:"widget_formSmash_j_idt191_2_j_idt195_otherAuthors",multiple:true}); 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]

##### 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 ()
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_2_j_idt195_j_idt367",{id:"formSmash:j_idt191:2:j_idt195:j_idt367",widgetVar:"widget_formSmash_j_idt191_2_j_idt195_j_idt367",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_2_j_idt195_j_idt373",{id:"formSmash:j_idt191:2:j_idt195:j_idt373",widgetVar:"widget_formSmash_j_idt191_2_j_idt195_j_idt373",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_2_j_idt195_j_idt379",{id:"formSmash:j_idt191:2:j_idt195:j_idt379",widgetVar:"widget_formSmash_j_idt191_2_j_idt195_j_idt379",multiple:true});
#####

##### Funder

Knut and Alice Wallenberg Foundation
Available from: 2018-06-29 Created: 2018-06-29 Last updated: 2018-06-29Bibliographically approved

Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.

Univ Paris Saclay, CNRS, UVSQ, Lab Math Versailles, F-78035 Versailles, France.

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.

Open this publication in new window or tab >>Non-fringe subtrees in conditioned Galton-Watson trees### Cai, Xing Shi

### Janson, Svante

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_3_j_idt195_some",{id:"formSmash:j_idt191:3:j_idt195:some",widgetVar:"widget_formSmash_j_idt191_3_j_idt195_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_3_j_idt195_otherAuthors",{id:"formSmash:j_idt191:3:j_idt195:otherAuthors",widgetVar:"widget_formSmash_j_idt191_3_j_idt195_otherAuthors",multiple:true}); 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]

##### National Category

Computer Sciences
##### Identifiers

urn:nbn:se:uu:diva-365652 (URN)000444053700003 ()
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_3_j_idt195_j_idt367",{id:"formSmash:j_idt191:3:j_idt195:j_idt367",widgetVar:"widget_formSmash_j_idt191_3_j_idt195_j_idt367",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_3_j_idt195_j_idt373",{id:"formSmash:j_idt191:3:j_idt195:j_idt373",widgetVar:"widget_formSmash_j_idt191_3_j_idt195_j_idt373",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_3_j_idt195_j_idt379",{id:"formSmash:j_idt191:3:j_idt195:j_idt379",widgetVar:"widget_formSmash_j_idt191_3_j_idt195_j_idt379",multiple:true});
#####

##### Funder

Knut and Alice Wallenberg Foundation
Available from: 2018-11-14 Created: 2018-11-14 Last updated: 2018-11-14Bibliographically approved

Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.

Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Probability Theory.

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.

Open this publication in new window or tab >>On Edge Exchangeable Random Graphs### Janson, Svante

Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Probability Theory.PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_4_j_idt195_some",{id:"formSmash:j_idt191:4:j_idt195:some",widgetVar:"widget_formSmash_j_idt191_4_j_idt195_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_4_j_idt195_otherAuthors",{id:"formSmash:j_idt191:4:j_idt195:otherAuthors",widgetVar:"widget_formSmash_j_idt191_4_j_idt195_otherAuthors",multiple:true}); 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]

##### 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 ()
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_4_j_idt195_j_idt367",{id:"formSmash:j_idt191:4:j_idt195:j_idt367",widgetVar:"widget_formSmash_j_idt191_4_j_idt195_j_idt367",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_4_j_idt195_j_idt373",{id:"formSmash:j_idt191:4:j_idt195:j_idt373",widgetVar:"widget_formSmash_j_idt191_4_j_idt195_j_idt373",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_4_j_idt195_j_idt379",{id:"formSmash:j_idt191:4:j_idt195:j_idt379",widgetVar:"widget_formSmash_j_idt191_4_j_idt195_j_idt379",multiple:true});
#####

##### Funder

Knut and Alice Wallenberg Foundation
Available from: 2018-12-21 Created: 2018-12-21 Last updated: 2018-12-21Bibliographically approved

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).

Open this publication in new window or tab >>On the critical probability in percolation### Janson, Svante

Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Probability Theory.### Warnke, Lutz

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_5_j_idt195_some",{id:"formSmash:j_idt191:5:j_idt195:some",widgetVar:"widget_formSmash_j_idt191_5_j_idt195_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_5_j_idt195_otherAuthors",{id:"formSmash:j_idt191:5:j_idt195:otherAuthors",widgetVar:"widget_formSmash_j_idt191_5_j_idt195_otherAuthors",multiple:true}); 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]

##### 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 ()
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_5_j_idt195_j_idt367",{id:"formSmash:j_idt191:5:j_idt195:j_idt367",widgetVar:"widget_formSmash_j_idt191_5_j_idt195_j_idt367",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_5_j_idt195_j_idt373",{id:"formSmash:j_idt191:5:j_idt195:j_idt373",widgetVar:"widget_formSmash_j_idt191_5_j_idt195_j_idt373",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_5_j_idt195_j_idt379",{id:"formSmash:j_idt191:5:j_idt195:j_idt379",widgetVar:"widget_formSmash_j_idt191_5_j_idt195_j_idt379",multiple:true});
#####

##### Funder

Knut and Alice Wallenberg Foundation
Available from: 2018-02-21 Created: 2018-02-21 Last updated: 2018-02-21Bibliographically approved

Georgia Inst Technol, Sch Math, Atlanta, GA 30332 USA.;Univ Cambridge Peterhouse, Cambridge CB2 1RD, England..

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.

Open this publication in new window or tab >>Renewal theory for asymmetric U-statistics### Janson, Svante

Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Probability Theory.PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_6_j_idt195_some",{id:"formSmash:j_idt191:6:j_idt195:some",widgetVar:"widget_formSmash_j_idt191_6_j_idt195_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_6_j_idt195_otherAuthors",{id:"formSmash:j_idt191:6:j_idt195:otherAuthors",widgetVar:"widget_formSmash_j_idt191_6_j_idt195_otherAuthors",multiple:true}); 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]

##### 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 ()
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_6_j_idt195_j_idt367",{id:"formSmash:j_idt191:6:j_idt195:j_idt367",widgetVar:"widget_formSmash_j_idt191_6_j_idt195_j_idt367",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_6_j_idt195_j_idt373",{id:"formSmash:j_idt191:6:j_idt195:j_idt373",widgetVar:"widget_formSmash_j_idt191_6_j_idt195_j_idt373",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_6_j_idt195_j_idt379",{id:"formSmash:j_idt191:6:j_idt195:j_idt379",widgetVar:"widget_formSmash_j_idt191_6_j_idt195_j_idt379",multiple:true});
#####

##### Funder

Knut and Alice Wallenberg Foundation
Available from: 2019-01-11 Created: 2019-01-11 Last updated: 2019-01-11Bibliographically approved

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.

Open this publication in new window or tab >>Sesqui-type branching processes### Janson, Svante

Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Probability Theory.### Riordan, Oliver

### Warnke, Lutz

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_7_j_idt195_some",{id:"formSmash:j_idt191:7:j_idt195:some",widgetVar:"widget_formSmash_j_idt191_7_j_idt195_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_7_j_idt195_otherAuthors",{id:"formSmash:j_idt191:7:j_idt195:otherAuthors",widgetVar:"widget_formSmash_j_idt191_7_j_idt195_otherAuthors",multiple:true}); 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]

##### 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 ()
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_7_j_idt195_j_idt367",{id:"formSmash:j_idt191:7:j_idt195:j_idt367",widgetVar:"widget_formSmash_j_idt191_7_j_idt195_j_idt367",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_7_j_idt195_j_idt373",{id:"formSmash:j_idt191:7:j_idt195:j_idt373",widgetVar:"widget_formSmash_j_idt191_7_j_idt195_j_idt373",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_7_j_idt195_j_idt379",{id:"formSmash:j_idt191:7:j_idt195:j_idt379",widgetVar:"widget_formSmash_j_idt191_7_j_idt195_j_idt379",multiple:true});
#####

##### Funder

Knut and Alice Wallenberg Foundation
Available from: 2019-01-07 Created: 2019-01-07 Last updated: 2019-01-07Bibliographically approved

Univ Oxford, Math Inst, Radcliffe Observ Quarter, Woodstock Rd, Oxford OX2 6GG, England.

Georgia Inst Technol, Sch Math, Atlanta, GA 30332 USA;Univ Cambridge Peterhouse, Cambridge CB2 1RD, England.

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.

Open this publication in new window or tab >>Tail bounds for sums of geometric and exponential variables### Janson, Svante

Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Probability Theory.PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_8_j_idt195_some",{id:"formSmash:j_idt191:8:j_idt195:some",widgetVar:"widget_formSmash_j_idt191_8_j_idt195_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_8_j_idt195_otherAuthors",{id:"formSmash:j_idt191:8:j_idt195:otherAuthors",widgetVar:"widget_formSmash_j_idt191_8_j_idt195_otherAuthors",multiple:true}); 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]

##### 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 ()
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_8_j_idt195_j_idt367",{id:"formSmash:j_idt191:8:j_idt195:j_idt367",widgetVar:"widget_formSmash_j_idt191_8_j_idt195_j_idt367",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_8_j_idt195_j_idt373",{id:"formSmash:j_idt191:8:j_idt195:j_idt373",widgetVar:"widget_formSmash_j_idt191_8_j_idt195_j_idt373",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_8_j_idt195_j_idt379",{id:"formSmash:j_idt191:8:j_idt195:j_idt379",widgetVar:"widget_formSmash_j_idt191_8_j_idt195_j_idt379",multiple:true});
#####

##### Funder

Knut and Alice Wallenberg Foundation
Available from: 2018-04-04 Created: 2018-04-04 Last updated: 2018-04-04Bibliographically approved

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

Open this publication in new window or tab >>Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications### Hwang, Hsien-Kuei

### Janson, Svante

### Tsai, Tsung-Hsi

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_9_j_idt195_some",{id:"formSmash:j_idt191:9:j_idt195:some",widgetVar:"widget_formSmash_j_idt191_9_j_idt195_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_9_j_idt195_otherAuthors",{id:"formSmash:j_idt191:9:j_idt195:otherAuthors",widgetVar:"widget_formSmash_j_idt191_9_j_idt195_otherAuthors",multiple:true}); 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]

##### 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 ()
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_9_j_idt195_j_idt367",{id:"formSmash:j_idt191:9:j_idt195:j_idt367",widgetVar:"widget_formSmash_j_idt191_9_j_idt195_j_idt367",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_9_j_idt195_j_idt373",{id:"formSmash:j_idt191:9:j_idt195:j_idt373",widgetVar:"widget_formSmash_j_idt191_9_j_idt195_j_idt373",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_9_j_idt195_j_idt379",{id:"formSmash:j_idt191:9:j_idt195:j_idt379",widgetVar:"widget_formSmash_j_idt191_9_j_idt195_j_idt379",multiple:true});
#####

Available from: 2018-01-31 Created: 2018-01-31 Last updated: 2018-01-31Bibliographically approved

Acad Sinica, Inst Stat Sci, 128,Sec 2,Acad Rd, Taipei 11529, Taiwan..

Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.

Acad Sinica, Inst Stat Sci, 128,Sec 2,Acad Rd, Taipei 11529, Taiwan..

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.