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

Robin Pemantle

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

ResearcherUnclaimed source record
math.PRmath.COMethodologymath-phmath.MPSymbolic ComputationData Structures and Algorithmsmath.CVhep-thInformation Theorymath.AGmath.GTmath.ITmath.STMultiagent SystemsStatistics Theory

Catalog footprint

What is connected

27works
16topics
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

27 published item(s)

preprint2022arXiv

Asymptotics of multivariate sequences in the presence of a lacuna

We explain a discontinuous drop in the exponential growth rate for certain multivariate generating functions at a critical parameter value, in even dimensions d at least 4. This result depends on computations in the homology of the algebraic variety where the generating function has a pole. These computations are similar to, and inspired by, a thread of research in applications of complex algebraic geometry to hyperbolic PDEs, going back to Leray, Petrowski, Atiyah, Bott and Garding. As a consequence, we give a topological explanation for certain asymptotic phenomenon appearing in the combinatorics and number theory literature. Furthermore, we show how to combine topological methods with symbolic algebraic computation to determine explicitly the dominant asymptotics for such multivariate generating functions, giving a significant new tool to attack the so-called connection problem for asymptotics of P-recursive sequences. This in turn enables the rigorous determination of integer coefficients in the Morse-Smale complex, which are difficult to determine using direct geometric methods.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Stationary points at infinity for analytic combinatorics

On complex algebraic varieties, height functions arising in combinatorial applications fail to be proper. This complicates the description and computation via Morse theory of key topological invariants. Here we establish checkable conditions under which the behavior at infinity may be ignored, and the usual theorems of classical and stratified Morse theory may be applied. This allows for simplified arguments in the field of analytic combinatorics in several variables, and forms the basis for new methods applying to problems beyond the reach of previous techniques.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Distributed Corruption Detection in Networks

We consider the problem of distributed corruption detection in networks. In this model, each vertex of a directed graph is either truthful or corrupt. Each vertex reports the type (truthful or corrupt) of each of its outneighbors. If it is truthful, it reports the truth, whereas if it is corrupt, it reports adversarially. This model, first considered by Preparata, Metze, and Chien in 1967, motivated by the desire to identify the faulty components of a digital system by having the other components checking them, became known as the PMC model. The main known results for this model characterize networks in which \emph{all} corrupt (that is, faulty) vertices can be identified, when there is a known upper bound on their number. We are interested in networks in which the identity of a \emph{large fraction} of the vertices can be identified. It is known that in the PMC model, in order to identify all corrupt vertices when their number is $t$, all indegrees have to be at least $t$. In contrast, we show that in $d$ regular-graphs with strong expansion properties, a $1-O(1/d)$ fraction of the corrupt vertices, and a $1-O(1/d)$ fraction of the truthful vertices can be identified, whenever there is a majority of truthful vertices. We also observe that if the graph is very far from being a good expander, namely, if the deletion of a small set of vertices splits the graph into small components, then no corruption detection is possible even if most of the vertices are truthful. Finally, we discuss the algorithmic aspects and the computational hardness of the problem.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Subpolynomial trace reconstruction for random strings and arbitrary deletion probability

The insertion-deletion channel takes as input a bit string ${\bf x}\in\{0,1\}^{n}$, and outputs a string where bits have been deleted and inserted independently at random. The trace reconstruction problem is to recover $\bf x$ from many independent outputs (called "traces") of the insertion-deletion channel applied to $\bf x$. We show that if $\bf x$ is chosen uniformly at random, then $\exp(O(\log^{1/3} n))$ traces suffice to reconstruct $\bf x$ with high probability. For the deletion channel with deletion probability $q < 1/2$ the earlier upper bound was $\exp(O(\log^{1/2} n))$. The case of $q\geq 1/2$ or the case where insertions are allowed has not been previously analyzed, and therefore the earlier upper bound was as for worst-case strings, i.e., $\exp(O( n^{1/3}))$. We also show that our reconstruction algorithm runs in $n^{1+o(1)}$ time. A key ingredient in our proof is a delicate two-step alignment procedure where we estimate the location in each trace corresponding to a given bit of $\bf x$. The alignment is done by viewing the strings as random walks and comparing the increments in the walk associated with the input string and the trace, respectively.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Multivariate CLT follows from strong Rayleigh property

Let $(X_1 , \ldots , X_d)$ be random variables taking nonnegative integer values and let $f(z_1, \ldots , z_d)$ be the probability generating function. Suppose that $f$ is real stable; equivalently, suppose that the polarization of this probability distribution is strong Rayleigh. In specific examples, such as occupation counts of disjoint sets by a determinantal point process, it is known~\cite{soshnikov02} that the joint distribution must approach a multivariate Gaussian distribution. We show that this conclusion follows already from stability of $f$.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Non-universality for longest increasing subsequence of a random walk

The longest increasing subsequence of a random walk with mean zero and finite variance is known to be $n^{1/2 + o(1)}$. We show that this is not universal for symmetric random walks. In particular, the symmetric Ultra-fat tailed random walk has a longest increasing subsequence that is asymptotically at least $n^{0.690}$ and at most $n^{0.815}$. An exponent strictly greater than $1/2$ is also shown for the symmetric stable-$α$ distribution when $α$ is sufficiently small.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Partial Information Framework: Model-Based Aggregation of Estimates from Diverse Information Sources

Prediction polling is an increasingly popular form of crowdsourcing in which multiple participants estimate the probability or magnitude of some future event. These estimates are then aggregated into a single forecast. Historically, randomness in scientific estimation has been generally assumed to arise from unmeasured factors which are viewed as measurement noise. However, when combining subjective estimates, heterogeneity stemming from differences in the participants' information is often more important than measurement noise. This paper formalizes information diversity as an alternative source of such heterogeneity and introduces a novel modeling framework that is particularly well-suited for prediction polls. A practical specification of this framework is proposed and applied to the task of aggregating probability and point estimates from two real-world prediction polls. In both cases our model outperforms standard measurement-error-based aggregators, hence providing evidence in favor of information diversity being the more important source of heterogeneity.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Coarsening in one dimension: invariant and asymptotic states

We study a coarsening process of one-dimensional cell complexes. We show that if cell boundaries move with velocities proportional to the difference in size of neighboring cells, then the average cell size grows at a prescribed exponential rate and the Poisson distribution is precisely invariant for the distribution of the whole process, rescaled in space by its average growth rate. We present numerical evidence toward the following universality conjecture: starting from any finite mean stationary renewal process, the system when rescaled by $e^{-2t}$ converges to a Poisson point process. For a limited case, this makes precise what has been observed previously in experiments and simulations, and lays the foundation for a theory of universal asymptotic states of dynamical cell complexes.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Combining Probability Forecasts and Understanding Probability Extremizing through Information Diversity

Randomness in scientific estimation is generally assumed to arise from unmeasured or uncontrolled factors. However, when combining subjective probability estimates, heterogeneity stemming from people's cognitive or information diversity is often more important than measurement noise. This paper presents a novel framework that uses partially overlapping information sources. A specific model is proposed within that framework and applied to the task of aggregating the probabilities given by a group of forecasters who predict whether an event will occur or not. Our model describes the distribution of information across forecasters in terms of easily interpretable parameters and shows how the optimal amount of extremizing of the average probability forecast (shifting it closer to its nearest extreme) varies as a function of the forecasters' information overlap. Our model thus gives a more principled understanding of the historically ad hoc practice of extremizing average forecasts.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Modeling Probability Forecasts via Information Diversity

Randomness in scientific estimation is generally assumed to arise from unmeasured or uncontrolled factors. However, when combining subjective probability estimates, heterogeneity stemming from people's cognitive or information diversity is often more important than measurement noise. This paper presents a novel framework that models the heterogeneity arising from experts that use partially overlapping information sources, and applies that model to the task of aggregating the probabilities given by a group of experts who forecast whether an event will occur or not. Our model describes the distribution of information across experts in terms of easily interpretable parameters and shows how the optimal amount of extremizing of the average probability forecast (shifting it closer to its nearest extreme) varies as a function of the experts' information overlap. Our model thus gives a more principled understanding of the historically ad hoc practice of extremizing average forecasts.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Four Random Permutations Conjugated by an Adversary Generate $S_n$ with High Probability

We prove a conjecture dating back to a 1978 paper of D.R.\ Musser~\cite{musserirred}, namely that four random permutations in the symmetric group $\mathcal{S}_n$ generate a transitive subgroup with probability $p_n > ε$ for some $ε> 0$ independent of $n$, even when an adversary is allowed to conjugate each of the four by a possibly different element of $§_n$ (in other words, the cycle types already guarantee generation of $\mathcal{S}_n$). This is closely related to the following random set model. A random set $M \subseteq \mathbb{Z}^+$ is generated by including each $n \geq 1$ independently with probability $1/n$. The sumset $\text{sumset}(M)$ is formed. Then at most four independent copies of $\text{sumset}(M)$ are needed before their mutual intersection is no longer infinite.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Principal minors and rhombus tilings

The algebraic relations between the principal minors of an $n\times n$ matrix are somewhat mysterious, see e.g. [lin-sturmfels]. We show, however, that by adding in certain \emph{almost} principal minors, the relations are generated by a single relation, the so-called hexahedron relation, which is a composition of six cluster mutations. We give in particular a Laurent-polynomial parameterization of the space of $n\times n$ matrices, whose parameters consist of certain principal and almost principal minors. The parameters naturally live on vertices and faces of the tiles in a rhombus tiling of a convex $2n$-gon. A matrix is associated to an equivalence class of tilings, all related to each other by Yang-Baxter-like transformations. By specializing the initial data we can similarly parametrize the space of Hermitian symmetric matrices over $\mathbb R, \mathbb C$ or $\mathbb H$ the quaternions. Moreover by further specialization we can parametrize the space of \emph{positive definite} matrices over these rings.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Concentration of Lipschitz functionals of determinantal and other strong Rayleigh measures

Let X_1 ,..., X_n be a collection of binary valued random variables and let f : {0,1}^n -> R be a Lipschitz function. Under a negative dependence hypothesis known as the {\em strong Rayleigh} condition, we show that f - E f satisfies a concentration inequality generalizing the classical Gaussian concentration inequality for sums of independent Bernoullis: P (S_n - E S_n > a) < exp (-2 a^2 / n). The class of strong Rayleigh measures includes determinantal measures, weighted uniform matroids and exclusion measures; some familiar examples from these classes are generalized negative binomials and spanning tree measures. For instance, the number of vertices of odd degree in a uniform random spanning tree of a graph satisfies a Gaussian concentration inequality with n replaced by |V|, the number of vertices. We also prove a continuous version for concentration of Lipschitz functionals of a determinantal point process.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Double-dimers, the Ising model and the hexahedron recurrence

We define and study a recurrence relation in ${\mathbb Z}^3$, called the hexahedron recurrence, which is similar to the octahedron recurrence (Hirota bilinear difference equation) and cube recurrence (Miwa equation). Like these examples, solutions to the hexahedron recurrence are partition sums for edge configurations on a certain graph, and have a natural interpretation in terms of cluster algebras. We give an explicit correspondence between monomials in the Laurent expansions arising in the recurrence with certain double-dimer configurations of a graph. We compute limit shapes for the corresponding double-dimer configurations. The Kashaev difference equation arising in the Ising model star-triangle relation is a special case of the hexahedron recurrence. In particular this reveals the cluster nature underlying the Ising model. The above relation allows us to prove a Laurent phenomenon for the Kashaev difference equation.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Automatic asymptotics for coefficients of smooth, bivariate rational functions

We consider a bivariate rational generating function F(x,y) = P(x,y) / Q(x,y) = sum_{r, s} a_{r,s} x^r y^s under the assumption that the complex algebraic curve $\sing$ on which $Q$ vanishes is smooth. Formulae for the asymptotics of the coefficients a_{rs} were derived by Pemantle and Wilson (2002). These formulae are in terms of algebraic and topological invariants of the pole variety, but up to now these invariants could be computed only under a minimality hypothesis, namely that the dominant saddle lies on the boundary of the domain of convergence. In the present paper, we give an effective method for computing the topological invariants, and hence the asymptotics of the values a_{r,s}, without the minimality assumption. This leads to a theoretically rigorous algorithm, whose implementation is in progress at http://www.mathemagix.org .

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Asymptotics of multivariate sequences, part III: quadratic points

We consider a number of combinatorial problems in which rational generating functions may be obtained, whose denominators have factors with certain singularities. Specifically, there exist points near which one of the factors is asymptotic to a nondegenerate quadratic. We compute the asymptotics of the coefficients of such a generating function. The computation requires some topological deformations as well as Fourier-Laplace transforms of generalized functions. We apply the results of the theory to specific combinatorial problems, such as Aztec diamond tilings, cube groves, and multi-set permutations.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

The distribution of zeros of the derivative of a random polynomial

In this note we initiate the probabilistic study of the critical points of polynomials of large degree with a given distribution of roots. Namely, let f be a polynomial of degree n whose zeros are chosen IID from a probability measure mu on the complex numbers. We conjecture that the zero set of f' always converges in distribution to mu as n goes to infinity. We prove this for measures with finite one-dimensional energy. When mu is uniform on the unit circle this condition fails. In this special case the zero set of f' converges in distribution to that the IID Gaussian random power series, a well known determinantal point process.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

The critical Ising model on trees, concave recursions and nonlinear capacity

We consider the Ising model on a general tree under various boundary conditions: all plus, free and spin-glass. In each case, we determine when the root is influenced by the boundary values in the limit as the boundary recedes to infinity. We obtain exact capacity criteria that govern behavior at critical temperatures. For plus boundary conditions, an $L^3$ capacity arises. In particular, on a spherically symmetric tree that has $n^αb^n$ vertices at level $n$ (up to bounded factors), we prove that there is a unique Gibbs measure for the ferromagnetic Ising model at the relevant critical temperature if and only if $α\le1/2$. Our proofs are based on a new link between nonlinear recursions on trees and $L^p$ capacities.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Two-dimensional quantum random walk

We analyze several families of two-dimensional quantum random walks. The feasible region (the region where probabilities do not decay exponentially with time) grows linearly with time, as is the case with one-dimensional QRW. The limiting shape of the feasible region is, however, quite different. The limit region turns out to be an algebraic set, which we characterize as the rational image of a compact algebraic variety. We also compute the probability profile within the limit region, which is essentially a negative power of the Gaussian curvature of the same algebraic variety. Our methods are based on analysis of the space-time generating function, following the methods of Pemantle and Wilson (2002).

0 citations0 reviewsNo code linkedOpen access
preprint2004arXiv

Robust Phase Transitions for Heisenberg and Other Models on General Trees

We study several statistical mechanical models on a general tree. Particular attention is devoted to the classical Heisenberg models, where the state space is the d-dimensional unit sphere and the interactions are proportional to the cosines of the angles between neighboring spins. The phenomenon of interest here is the classification of phase transition (non-uniqueness of the Gibbs state) according to whether it is robust. In many cases, including all of the Heisenberg and Potts models, occurrence of robust phase transition is determined by the geometry (branching number) of the tree in a way that parallels the situation with independent percolation and usual phase transition for the Ising model. The critical values for robust phase transition for the Heisenberg and Potts models are also calculated exactly. In some cases, such as the q>=3 Potts model, robust phase transition and usual phase transition do not coincide, while in other cases, such as the Heisenberg models, we conjecture that robust phase transition and usual phase transition are equivalent. In addition, we show that symmetry breaking is equivalent to the existence of a phase transition, a fact believed but not known for the rotor model on Z^2.

0 citations0 reviewsNo code linkedOpen access