Change search

Cite
Citation style
• apa
• ieee
• modern-language-association-8th-edition
• 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
On Directed Random Graphs and Greedy Walks on Point Processes
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Probability Theory.
2016 (English)Doctoral thesis, comprehensive summary (Other academic)
##### Abstract [en]

This thesis consists of an introduction and five papers, of which two contribute to the theory of directed random graphs and three to the theory of greedy walks on point processes.

We consider a directed random graph on a partially ordered vertex set, with an edge between any two comparable vertices present with probability p, independently of all other edges, and each edge is directed from the vertex with smaller label to the vertex with larger label. In Paper I we consider a directed random graph on ℤ2 with the vertices ordered according to the product order and we show that the limiting distribution of the centered and rescaled length of the longest path from (0,0) to (n, [na] ), a<3/14, is the Tracy-Widom distribution. In Paper II we show that, under a suitable rescaling, the closure of vertex 0 of a directed random graph on ℤ with edge probability n−1 converges in distribution to the Poisson-weighted infinite tree. Moreover, we derive limit theorems for the length of the longest path of the Poisson-weighted infinite tree.

The greedy walk is a deterministic walk on a point process that always moves from its current position to the nearest not yet visited point. Since the greedy walk on a homogeneous Poisson process on the real line, starting from 0, almost surely does not visit all points, in Paper III we find the distribution of the number of visited points on the negative half-line and the distribution of the index at which the walk achieves its minimum. In Paper IV we place homogeneous Poisson processes first on two intersecting lines and then on two parallel lines and we study whether the greedy walk visits all points of the processes. In Paper V we consider the greedy walk on an inhomogeneous Poisson process on the real line and we determine sufficient and necessary conditions on the mean measure of the process for the walk to visit all points.

##### Place, publisher, year, edition, pages
Uppsala: Department of Mathematics, 2016. , p. 28
##### Series
Uppsala Dissertations in Mathematics, ISSN 1401-2049 ; 97
##### Keyword [en]
Directed random graphs, Tracy-Widom distribution, Poisson-weighted infinite tree, Greedy walk, Point processes
##### National Category
Probability Theory and Statistics
##### Identifiers
ISBN: 978-91-506-2608-7 (print)OAI: oai:DiVA.org:uu-305859DiVA, id: diva2:1039330
##### Public defence
2016-12-09, Polhemsalen, Ångströmlaboratoriet, Lägerhyddsvägen 1, Uppsala, 13:15 (English)
##### Supervisors
Available from: 2016-11-15 Created: 2016-10-23 Last updated: 2016-11-15
##### List of papers
1. Convergence to the Tracy-Widom distribution for longest paths in a directed random graph
Open this publication in new window or tab >>Convergence to the Tracy-Widom distribution for longest paths in a directed random graph
2013 (English)In: Latin American Journal of Probability and Mathematical Statistics, ISSN 1980-0436, E-ISSN 1980-0436, Vol. 10, no 2, p. 711-730Article in journal (Refereed) Published
##### Abstract [en]

We consider a directed graph on the 2-dimensional integer lattice, placing a directed edge from vertex (i1,i2) to (j1,j2), whenever i1 ≤ j1, i2 ≤ j2, with probability p, independently for each such pair of vertices. Let Ln,m denote the maximum length of all paths contained in an n×m rectangle. We show that there is a positive exponent a, such that, if m/na→1, as n→∞, then a properly centered/rescaled version of Ln,m converges weakly to the Tracy-Widom distribution. A generalization to graphs with non-constant probabilities is also discussed.

##### Keyword
Random graph, last passage percolation, strong approximation, Tracy- Widom distribution
##### National Category
Probability Theory and Statistics
##### Identifiers
urn:nbn:se:uu:diva-304258 (URN)
Available from: 2016-10-03 Created: 2016-10-03 Last updated: 2017-11-30
2. Convergence of directed random graphs to the Poisson-weighted infinite tree
Open this publication in new window or tab >>Convergence of directed random graphs to the Poisson-weighted infinite tree
2016 (English)In: Journal of Applied Probability, ISSN 0021-9002, E-ISSN 1475-6072, Vol. 53, no 2, p. 463-474Article in journal (Refereed) Published
##### Abstract [en]

We consider a directed graph on the integers with a directed edge from vertex i to j present with probability n-1, whenever i<j, independently of all other edges. Moreover, to each edge (i,j) we assign weight n-1(j - i). We show that the closure of vertex 0 in such a weighted random graph converges in distribution to the Poisson-weighted infinite tree as n→∞. In addition, we derive limit theorems for the length of the longest path in the subgraph of the Poisson-weighted infinite tree which has all vertices at weighted distance of at most ρ from the root.

##### Keyword
Directed random graph, Poisson-weighted infinite tree, rooted geometric graph
##### National Category
Probability Theory and Statistics
##### Identifiers
urn:nbn:se:uu:diva-299908 (URN)10.1017/jpr.2016.13 (DOI)000378598700012 ()
Available from: 2016-07-29 Created: 2016-07-29 Last updated: 2017-11-28
3. Distribution of the smallest visited point in a greedy walk on the line
Open this publication in new window or tab >>Distribution of the smallest visited point in a greedy walk on the line
2016 (English)In: Journal of Applied Probability, ISSN 0021-9002, E-ISSN 1475-6072, Vol. 53, no 3, p. 880-887Article in journal (Refereed) Published
##### Abstract [en]

We consider a greedy walk on a Poisson process on the real line. It is known that the walk does not visit all points of the process. In this paper we first obtain some useful independence properties associated with this process which enable us to compute the distribution of the sequence of indices of visited points. Given that the walk tends to +∞, we find the distribution of the number of visited points in the negative half-line, as well as the distribution of the time at which the walk achieves its minimum.

##### National Category
Probability Theory and Statistics
##### Identifiers
urn:nbn:se:uu:diva-305791 (URN)10.1017/jpr.2016.46 (DOI)000386349900016 ()
Available from: 2016-10-21 Created: 2016-10-21 Last updated: 2017-11-29Bibliographically approved
4. Greedy walks on two lines
Open this publication in new window or tab >>Greedy walks on two lines
2016 (English)Article in journal (Other academic) Submitted
##### National Category
Probability Theory and Statistics
##### Identifiers
urn:nbn:se:uu:diva-305792 (URN)
Available from: 2016-10-21 Created: 2016-10-21 Last updated: 2016-10-23
5. The greedy walk on an inhomogeneous Poisson process
Open this publication in new window or tab >>The greedy walk on an inhomogeneous Poisson process
2016 (English)Article in journal (Other academic) Submitted
##### National Category
Probability Theory and Statistics
##### Identifiers
urn:nbn:se:uu:diva-305795 (URN)
Available from: 2016-10-21 Created: 2016-10-21 Last updated: 2016-10-28

#### Open Access in DiVA

##### File information
File name FULLTEXT01.pdfFile size 1204 kBChecksum SHA-512
ed30cf4dc34f82903c4f10176c37135a6d01341fc34df60b46824585378b4161c144818094c33a6c464ff6fb1e1fa61e84d29fa890e5c578b4f8092bef131120
Type fulltextMimetype application/pdf

#### Search in DiVA

Gabrysch, Katja
##### By organisation
Analysis and Probability Theory
##### On the subject
Probability Theory and Statistics

#### Search outside of DiVA

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
isbn
urn-nbn

#### Altmetric score

isbn
urn-nbn
Total: 1467 hits

Cite
Citation style
• apa
• ieee
• modern-language-association-8th-edition
• 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
v. 2.32.0
|