Change search
ReferencesLink to record
Permanent link

Direct link
Recursive Methods in Urn Models and First-Passage Percolation
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Mathematical Statistics.
2011 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

This PhD thesis consists of a summary and four papers which deal with stochastic approximation algorithms and first-passage percolation.

Paper I deals with the a.s. limiting properties of bounded stochastic approximation algorithms in relation to the equilibrium points of the drift function. Applications are given to some generalized Pólya urn processes.

Paper II continues the work of Paper I and investigates under what circumstances one gets asymptotic normality from a properly scaled algorithm. The algorithms are shown to converge in some other circumstances, although the limiting distribution is not identified.

Paper III deals with the asymptotic speed of first-passage percolation on a graph called the ladder when the times associated to the edges are independent, exponentially distributed with the same intensity.

Paper IV generalizes the work of Paper III in allowing more edges in the graph as well as not having all intensities equal.

Place, publisher, year, edition, pages
Uppsala: Department of Mathematics , 2011. , 30 p.
Series
Uppsala Dissertations in Mathematics, ISSN 1401-2049 ; 69
Keyword [en]
stochastic approximation algorithm, generalized Polya urn, limit theorem, first-passage percolation, rate of percolation, time constant
National Category
Probability Theory and Statistics
Research subject
Mathematical Statistics
Identifiers
URN: urn:nbn:se:uu:diva-145430ISBN: 978-91-506-2190-7OAI: oai:DiVA.org:uu-145430DiVA: diva2:396187
Public defence
2011-03-25, Häggsalen, Ångströmlaboratoriet, Lägerhyddsvägen 1, Uppsala, 13:15 (English)
Opponent
Supervisors
Available from: 2011-03-04 Created: 2011-02-09 Last updated: 2011-03-04
List of papers
1. Generalized Pólya Urns via Stochastic Approximation
Open this publication in new window or tab >>Generalized Pólya Urns via Stochastic Approximation
2009 (English)Licentiate thesis, monograph (Other academic)
Place, publisher, year, edition, pages
Uppsala: Department of Mathematics, Uppsala University, 2009
Series
U.U.D.M. report / Uppsala University, Department of Mathematics, ISSN 1101-3591 ; 2009:7
Keyword
stochastic approximation, unstable equilibrium, stable equilibrium, touchpoint, generalized pólya urns
National Category
Mathematics
Research subject
Mathematics
Identifiers
urn:nbn:se:uu:diva-106522 (URN)
Presentation
64119, Ångström Lab., Uppsala (Swedish)
Opponent
Supervisors
Available from: 2009-06-25 Created: 2009-06-25 Last updated: 2012-07-26Bibliographically approved
2. Limit theorems for stochastic approximation algorithms.
Open this publication in new window or tab >>Limit theorems for stochastic approximation algorithms.
2011 (English)Report (Other academic)
Abstract [en]

We prove a central limit theorem applicable to one dimensional stochastic approximation algorithms that converge to a point where the error terms of the algorithm do not vanish. We show how this applies to a certain class of these algorithms that in particular covers a generalized Pólya urn model, which is also discussed.  In addition, we  show how to scale these algorithms in some cases where we cannot determine the limiting distribution but expect it to be non-normal.

26 p.
Series
, U.U.D.M, 2011:6
Keyword
stochastic approximation algorithms, central limit theorem, generalized Polya urn
National Category
Probability Theory and Statistics
Research subject
Mathematical Statistics
Identifiers
urn:nbn:se:uu:diva-145343 (URN)
Available from: 2011-02-09 Created: 2011-02-08 Last updated: 2011-02-14Bibliographically approved
3. First-Passage Percolation with Exponential Times on a Ladder
Open this publication in new window or tab >>First-Passage Percolation with Exponential Times on a Ladder
2010 (English)In: Combinatorics, probability & computing, ISSN 0963-5483, E-ISSN 1469-2163, Vol. 19, no 4, 593-601 p.Article in journal (Refereed) Published
Abstract [en]

We consider first-passage percolation on a ladder, i.e., the graph N x {0, 1}, where nodes at distance 1 are joined by an edge, and the times are exponentially i.i.d. with mean 1. We find an appropriate Markov chain to calculate an explicit expression for the time constant whose numerical value is approximate to 0.6827. This time constant is the long-term average inverse speed of the process. We also calculate the average residual time.

National Category
Mathematics
Identifiers
urn:nbn:se:uu:diva-136164 (URN)10.1017/S0963548310000052 (DOI)000279038700007 ()
Available from: 2010-12-10 Created: 2010-12-10 Last updated: 2011-03-01Bibliographically approved
4. First-passage percolation on ladder-like graphs with heterogeneous exponential times.
Open this publication in new window or tab >>First-passage percolation on ladder-like graphs with heterogeneous exponential times.
2011 (English)Report (Other academic)
Abstract [en]

We determine the asymptotic speed of the first-passage percolation process on some ladder-like graphs (or width-2 stretches) when the times associated with different edges are independent and exponentially distributed but not necessarily all with the same mean. The method uses a particular Markov chain associated with the first-passage percolation process and properties of its stationary distribution.

25 p.
Series
, U.U.D.M, 2011:5
Keyword
first-passage percolation, rate of percolation
National Category
Probability Theory and Statistics
Research subject
Mathematical Statistics
Identifiers
urn:nbn:se:uu:diva-145340 (URN)
Available from: 2011-02-09 Created: 2011-02-08 Last updated: 2011-02-14Bibliographically approved

Open Access in DiVA

fulltext(957 kB)390 downloads
File information
File name FULLTEXT01.pdfFile size 957 kBChecksum SHA-512
7c5566901b339ac9a3d79b36d8498fb468952094be4fcdaae9ac851ec73f140b15420479a4d35be7a4fdbabd98b4c4354426308aea3da6a2c9f9e5735e56bcb4
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Renlund, Henrik
By organisation
Mathematical Statistics
Probability Theory and Statistics

Search outside of DiVA

GoogleGoogle Scholar
Total: 390 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 443 hits
ReferencesLink to record
Permanent link

Direct link