BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Joel Spencer

Joel Spencer appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.PRmath.CODiscrete Mathematicscond-mat.stat-mechmath.LONetworking and Internet ArchitecturePerformance

Catalog footprint

What is connected

9works
7topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

9 published item(s)

preprint2018arXiv

Preferential Attachment When Stable

We study an urn process with two urns, initialized with a ball each. Balls are added sequentially, the urn being chosen independently with probability proportional to the $α^{th}$ power $(α>1)$ of the existing number of balls. We study the (rare) event that the urn compositions are balanced after the addition of $2n-2$ new balls. We derive precise asymptotics of the probability of this event by embedding the process in continuous time. Quite surprisingly, a fine control on this probability may be leveraged to derive a lower tail Large Deviation Principle (LDP) for $L = \sum_{i=1}^{n} \frac{S_i^2}{i^2}$, where $\{S_n : n \geq 0\}$ is a simple symmetric random walk started at zero. We provide an alternate proof of the LDP via coupling to Brownian motion, and subsequent derivation of the LDP for a continuous time analogue of $L$. Finally, we turn our attention back to the urn process conditioned to be balanced, and provide a functional limit law describing the trajectory of the urn process.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

First Order Probabilities For Galton-Watson Trees

In the regime of Galton-Watson trees, first order logic statements are roughly equivalent to examining the presence of specific finite subtrees. We consider the space of all trees with Poisson offspring distribution and show that such finite subtrees will be almost surely present when the tree is infinite. Introducing the notion of universal trees, we show that all first order sentences of quantifier depth $k$ depend only on local neighbourhoods of the root of sufficiently large radius depending on $k$. We compute the probabilities of these neighbourhoods conditioned on the tree being infinite. We give an almost sure theory for infinite trees.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Galton-Watson Probability Contraction

We are concerned with exploring the probabilities of first order statements for Galton-Watson trees with $Poisson(c)$ offspring distribution. Fixing a positive integer $k$, we exploit the $k$-move Ehrenfeucht game on rooted trees for this purpose. Let $Σ$, indexed by $1 \leq j \leq m$, denote the finite set of equivalence classes arising out of this game, and $D$ the set of all probability distributions over $Σ$. Let $x_{j}(c)$ denote the true probability of the class $j \in Σ$ under $Poisson(c)$ regime, and $\vec{x}(c)$ the true probability vector over all the equivalence classes. Then we are able to define a natural recursion function $Γ$, and a map $Ψ= Ψ_{c}: D \rightarrow D$ such that $\vec{x}(c)$ is a fixed point of $Ψ_{c}$, and starting with any distribution $\vec{x} \in D$, we converge to this fixed point via $Ψ$ because it is a contraction. We show this both for $c \leq 1$ and $c > 1$, though the techniques for these two ranges are quite different.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Heat diffusion with frozen boundary

Consider "Frozen Random Walk" on $\mathbb{Z}$: $n$ particles start at the origin. At any discrete time, the leftmost and rightmost $\lfloor{\frac{n}{4}}\rfloor$ particles are "frozen" and do not move. The rest of the particles in the "bulk" independently jump to the left and right uniformly. The goal of this note is to understand the limit of this process under scaling of mass and time. To this end we study the following deterministic mass splitting process: start with mass $1$ at the origin. At each step the extreme quarter mass on each side is "frozen". The remaining "free" mass in the center evolves according to the discrete heat equation. We establish diffusive behavior of this mass evolution and identify the scaling limit under the assumption of its existence. It is natural to expect the limit to be a truncated Gaussian. A naive guess for the truncation point might be the $1/4$ quantile points on either side of the origin. We show that this is not the case and it is in fact determined by the evolution of the second moment of the mass distribution.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Queuing with future information

We study an admissions control problem, where a queue with service rate $1-p$ receives incoming jobs at rate $λ\in(1-p,1)$, and the decision maker is allowed to redirect away jobs up to a rate of $p$, with the objective of minimizing the time-average queue length. We show that the amount of information about the future has a significant impact on system performance, in the heavy-traffic regime. When the future is unknown, the optimal average queue length diverges at rate $\sim\log_{1/(1-p)}\frac{1}{1-λ}$, as $λ\to 1$. In sharp contrast, when all future arrival and service times are revealed beforehand, the optimal average queue length converges to a finite constant, $(1-p)/p$, as $λ\to1$. We further show that the finite limit of $(1-p)/p$ can be achieved using only a finite lookahead window starting from the current time frame, whose length scales as $\mathcal{O}(\log\frac{1}{1-λ})$, as $λ\to1$. This leads to the conjecture of an interesting duality between queuing delay and the amount of information about the future.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

The Bohman-Frieze Process Near Criticality

The Erdős-Rényi process begins with an empty graph on n vertices and edges are added randomly one at a time to a graph. A classical result of Erdős and Rényi states that the Erdős-Rényi process undergoes a phase transition, which takes place when the number of edges reaches n/2 (we say at time 1) and a giant component emerges. Since this seminal work of Erdős and Rényi, various random graph models have been introduced and studied. In this paper we study the so-called Bohman-Frieze process, a simple modification of the Erdős-Rényi process. The Bohman-Frieze process begins with an empty graph on n vertices. At each step two random edges are present and if the first edge would join two isolated vertices, it is added to a graph; otherwise the second edge is added. We present several new results on the phase transition of the Bohman-Frieze random graph process. We show that the Bohman-Frieze process has a qualitatively similar phase transition to the Erdős-Rényi process in terms of the size and structure of the components near the critical point. We prove that all components at time t_c-\eps (that is, when the number of edges are (t_c-\eps) n/2) are trees or unicyclic components and that the largest component is of size Ω(\eps^{-2} \log n). Further, at t_c + \eps, all components apart from the giant component are trees or unicyclic and the size of the second-largest component is Θ(\eps^{-2} \log n). Each of these results corresponds to an analogous well-known result for the Erdős-Rényi process. Our methods include combinatorial arguments and a combination of the differential equation method for random processes with singularity analysis of generating functions which satisfy quasi-linear partial differential equations.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Deterministic Random Walks on Regular Trees

Jim Propp's rotor router model is a deterministic analogue of a random walk on a graph. Instead of distributing chips randomly, each vertex serves its neighbors in a fixed order. Cooper and Spencer (Comb. Probab. Comput. (2006)) show a remarkable similarity of both models. If an (almost) arbitrary population of chips is placed on the vertices of a grid $\Z^d$ and does a simultaneous walk in the Propp model, then at all times and on each vertex, the number of chips on this vertex deviates from the expected number the random walk would have gotten there by at most a constant. This constant is independent of the starting configuration and the order in which each vertex serves its neighbors. This result raises the question if all graphs do have this property. With quite some effort, we are now able to answer this question negatively. For the graph being an infinite $k$-ary tree ($k \ge 3$), we show that for any deviation $D$ there is an initial configuration of chips such that after running the Propp model for a certain time there is a vertex with at least $D$ more chips than expected in the random walk model. However, to achieve a deviation of $D$ it is necessary that at least $\exp(Ω(D^2))$ vertices contribute by being occupied by a number of chips not divisible by $k$ at a certain time.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Phase transitions for modified Erdös-Rényi processes

A fundamental and very well studied region of the Erdös-Rényi process is the phase transition at n/2 edges in which a giant component suddenly appears. We examine the process beginning with an initial graph. We further examine the Bohman-Frieze process in which edges between isolated vertices are more likely. While the positions of the phase transitions vary, the three processes belong, roughly speaking, to the same universality class. In particular, the growth of the giant component in the barely supercritical region is linear in all cases.

0 citations0 reviewsNo code linkedOpen access
preprint1994arXiv

Can you feel the double jump?

Paul Erdős and Alfred Renyi considered the evolution of the random graph G(n,p) as p ``evolved'' from 0 to 1. At p=1/n a sudden and dramatic change takes place in G. When p=c/n with c<1 the random G consists of small components, the largest of size Theta(log n). But by p=c/n with c>1 many of the components have ``congealed'' into a ``giant component'' of size Theta (n). Erdős and Renyi called this the double jump, the terms phase transition (from the analogy to percolation) and Big Bang have also been proferred. Now imagine an observer who can only see G through a logical fog. He may refer to graph theoretic properties A within a limited logical language. Will he be able to detect the double jump? The answer depends on the strength of the language. Our rough answer to this rough question is: the double jump is not detectible in the First Order Theory of Graphs but it is detectible in the Second Order Monadic Theory of Graphs.

0 citations0 reviewsNo code linkedOpen access