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

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
The dominating colour of an infinite Pólya urn model
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Probability Theory.ORCID iD: 0000-0002-0592-1808
2016 (English)In: Journal of Applied Probability, ISSN 0021-9002, E-ISSN 1475-6072, Vol. 53, no 3, p. 914-924Article in journal (Refereed) Published
Abstract [en]

We study a Pólya-type urn model defined as follows. Start at time 0 with a single ball of some colour. Then, at each time n≥1, choose a ball from the urn uniformly at random. With probability ½<p<1, return the ball to the urn along with another ball of the same colour. With probability 1−p, recolour the ball to a new colour and then return it to the urn. This is equivalent to the supercritical case of a random graph model studied by Backhausz and Móri (2015), (2016) and Thörnblad (2015). We prove that, with probability 1, there is a dominating colour, in the sense that, after some random but finite time, there is a colour that always has the most number of balls. A crucial part of the proof is the analysis of an urn model with two colours, in which the observed ball is returned to the urn along with another ball of the same colour with probability p, and removed with probability 1−p. Our results here generalise a classical result about the Pólya urn model (which corresponds to p=1).

Place, publisher, year, edition, pages
2016. Vol. 53, no 3, p. 914-924
National Category
Probability Theory and Statistics
Identifiers
URN: urn:nbn:se:uu:diva-274483DOI: 10.1017/jpr.2016.49ISI: 000386349900019OAI: oai:DiVA.org:uu-274483DiVA, id: diva2:896568
Available from: 2016-01-21 Created: 2016-01-21 Last updated: 2018-01-17Bibliographically approved
In thesis
1. Asymptotics of a Random Graph Model
Open this publication in new window or tab >>Asymptotics of a Random Graph Model
2016 (English)Licentiate thesis, comprehensive summary (Other academic)
Publisher
p. 32
Series
U.U.D.M. report / Uppsala University, Department of Mathematics, ISSN 1101-3591 ; 2016:3
National Category
Probability Theory and Statistics
Identifiers
urn:nbn:se:uu:diva-273524 (URN)
Opponent
Supervisors
Available from: 2016-01-25 Created: 2016-01-15 Last updated: 2016-01-25Bibliographically approved
2. Degrees in Random Graphs and Tournament Limits
Open this publication in new window or tab >>Degrees in Random Graphs and Tournament Limits
2018 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

This thesis consists of an introduction and six papers on the topics of degree distributions in random graphs and tournaments and their limits.

The first two papers deal with a dynamic random graph, evolving in time through duplication and deletion of vertices and edges. In Paper I we study the degree densities of this model. We show that these densities converge almost surely and determine their limiting values exactly as well as asymptotically for large degrees. In Paper II we study the evolution of the maximum degree and provide a precise growth rate thereof.

Paper III deals with a dynamic random tree model known as the vertex-splitting tree model. We show that the degree densities converge almost surely and find an infinite linear system of equations which they must satisfy. Unfortunately we are not able to show that this system has a unique solution except in special cases.

Paper IV is about self-converse generalised tournaments. A self-converse generalised tournament can be seen as a matrix whose entries take values in [0,1] and whose diagonally opposite elements sum to 1. We characterise completely the marginals of such a matrix, and show that such marginals can always be realised by a self-converse generalised tournament.

In Paper V, we define and develop the theory of tournament limits and tournament kernels. We characterise transitive and irreducible tournament limits and kernels, and prove that any tournament limit and kernel has an essentially unique decomposition into irreducible tournament limits or kernels interlaced by a transitive part.

In Paper VI, we study the degree distributions of tournament limits, or equivalently, the marginals of tournament kernels. We describe precisely which distributions on [0,1] which may appear as degree distributions of tournament limits and which functions from [0,1] to [0,1] may appear as the marginals of tournament kernels. Moreover, we show that any distribution or marginal on this form may be realised by a tournament limit or tournament kernel. We also study those distributions and marginals which can be realised by a unique tournament limit or kernel, and find that only the transitive tournament limit/kernel gives rise to a degree distribution or marginal with this property.

Place, publisher, year, edition, pages
Uppsala: Department of Mathematics, 2018. p. 26
Series
Uppsala Dissertations in Mathematics, ISSN 1401-2049 ; 105
Keyword
Random graphs, degree distributions, degree sequences, graph limits, tournaments
National Category
Mathematics
Research subject
Mathematics
Identifiers
urn:nbn:se:uu:diva-339025 (URN)978-91-506-2677-3 (ISBN)
Public defence
2018-03-09, Polhemssalen, Ångströmlaboratoriet, Lägerhyddsvägen 1, Uppsala, 13:15 (English)
Opponent
Supervisors
Available from: 2018-02-14 Created: 2018-01-17 Last updated: 2018-02-14

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Authority records BETA

Thörnblad, Erik

Search in DiVA

By author/editor
Thörnblad, Erik
By organisation
Analysis and Probability Theory
In the same journal
Journal of Applied Probability
Probability Theory and Statistics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 325 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf