Source author record

Jean-François Marckert

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.PR math.CO Discrete Mathematics math.MG Distributed, Parallel, and Cluster Computing hep-th math-ph math.MP math.ST Statistics Theory

Catalog footprint

Research overview

16works

10topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

A combinatorial proof of Aldous-Broder theorem for general Markov chains

Aldous-Broder algorithm is a famous algorithm used to sample a uniform spanning tree of any finite connected graph $G$ , but it is more general: given an irreducible and reversible Markov chain $M$ on $G$ started at $r$ , the tree rooted at $r$ formed by the first entrance steps in each node (different from the root) has a probability proportional to $\prod_{e=(e^-,e^+)\in {\sf Edges}(t,r)} M_{e^{-},e^+}$ , where the edges are directed toward $r$ . In this paper we give proofs of Aldous-Broder theorem in the general case, where the kernel $M$ is irreducible but not assumed to be reversible (this generalized version appeared recently in Hu, Lyons and Tang )

preprint2020arXiv

Iterated foldings of discrete spaces and their limits: candidates for the role of Brownian map in higher dimensions

In this last decade, an important stochastic model emerged: the Brownian map. It is the limit of various models of random combinatorial maps after rescaling: it is a random metric space with Hausdorff dimension 4, almost surely homeomorphic to the 2-sphere, and possesses some deep connections with Liouville quantum gravity in 2D. In this paper, we present a sequence of random objects that we call $D$ th-random feuilletages (denoted by ${\bf r}[D]$ ), indexed by a parameter $D\geq 0$ and which are candidate to play the role of the Brownian map in dimension $D$ . The construction relies on some objects that we name iterated Brownian snakes, which are branching analogues of iterated Brownian motions, and which are moreover limits of iterated discrete snakes. In the planar $D=2$ case, the family of discrete snakes considered coincides with some family of (random) labeled trees known to encode planar quadrangulations. Iterating snakes provides a sequence of random trees $({\bf t}^{(j)}, j\geq 1)$ . The $D$ th-random feuilletage ${\bf r}[D]$ is built using $({\bf t}^{(1)},\cdots,{\bf t}^{(D)})$ : ${\bf r}[0]$ is a deterministic circle, ${\bf r}[1]$ is Aldous' continuum random tree, ${\bf r}[2]$ is the Brownian map, and somehow, ${\bf r}[D]$ is obtained by quotienting ${\bf t}^{(D)}$ by ${\bf r}[D-1]$ . A discrete counterpart to ${\bf r}[D]$ is introduced and called the $D$ th random discrete feuilletage with $n+D$ nodes ( ${\bf r}_n[D]$ ). The proof of the convergence of ${\bf r}_n[D]$ to ${\bf r}[D]$ after appropriate rescaling in some functional space is provided (however, the convergence obtained is too weak to imply the Gromov-Hausdorff convergence). An upper bound on the diameter of ${\bf r}_{n}[D]$ is $n^{1/2^{D}}$ . Some elements allowing to conjecture that the Hausdorff dimension of ${\bf r}[D]$ is $2^D$ are given.

preprint2020arXiv

The combinatorics of the colliding bullets problem

The finite colliding bullets problem is the following simple problem: consider a gun, whose barrel remains in a fixed direction; let $(V_i)_{1\le i\le n}$ be an i.i.d.\ family of random variables with uniform distribution on $[0,1]$ ; shoot $n$ bullets one after another at times $1,2,\dots, n$ , where the $i$ th bullet has speed $V_i$ . When two bullets collide, they both annihilate. We give the distribution of the number of surviving bullets, and in some generalisation of this model. While the distribution is relatively simple (and we found a number of bold claims online), our proof is surprisingly intricate and mixes combinatorial and geometric arguments; we argue that any rigorous argument must very likely be rather elaborate.

preprint2015arXiv

Around Sylvester's question in the plane

Pick $n$ points $Z_0,...,Z_{n-1}$ uniformly and independently at random in a compact convex set $H$ with non empty interior of the plane, and let $Q^n_H$ be the probability that the $Z_i$ 's are the vertices of a convex polygon. Blaschke 1917 \cite{Bla} proved that $Q^4_T\leq Q^4_H\leq Q^4_D$ , where $D$ is a disk and $T$ a triangle. In the present paper we prove $Q^5_T\leq Q^5_H\leq Q^5_D$ . One of the main ingredients of our approach is a new formula for $Q^n_H$ which permits to prove that Steiner symmetrization does not decrease $Q^5_H$ , and that shaking does not increases it (this is the method Blaschke used in the $n=4$ case). We conjecture that the new formula we provide will lead in the future to the complete proof that $Q^n_T\leq Q^n_H\leq Q^n_D$ , for any $n$ .

preprint2015arXiv

Election algorithms with random delays in trees

The election is a classical problem in distributed algorithmic. It aims to design and to analyze a distributed algorithm choosing a node in a graph, here, in a tree. In this paper, a class of randomized algorithms for the election is studied. The election amounts to removing leaves one by one until the tree is reduced to a unique node which is then elected. The algorithm assigns to each leaf a probability distribution (that may depends on the information transmitted by the eliminated nodes) used by the leaf to generate its remaining random lifetime. In the general case, the probability of each node to be elected is given. For two categories of algorithms, close formulas are provided.

preprint2015arXiv

Markovianity of the invariant distribution of probabilistic cellular automata on the line

We revisit the problem of finding the conditions under which synchronous probabilistic cellular automata indexed by the line $\mathbb{Z}$ , or the periodic line $\cyl{n}$, depending on 2 neighbours, admit as invariant distribution the law of a space-indexed Markov chain. Our advances concerns PCA defined on a finite alphabet, where most of existing results concern size 2 alphabet. A part of the paper is also devoted to the comparison of different structures ( $\mathbb{Z}$ , $\cyl{n}$, and also some structures constituted with two consecutive lines of the space time diagram) with respect to the property to possess a Markovian invariant distribution.

preprint2015arXiv

Processes iterated ad libitum

Consider the $n$ th iterated Brownian motion $I^{(n)}=B_n \circ\cdots \circ B_1$ . Curien and Konstantopoulos proved that for any distinct numbers $t_i\neq 0$ , $(I^{(n)}(t_1),\dots,I^{(n)}(t_k))$ converges in distribution to a limit $I[k]$ independent of the $t_i$ 's, exchangeable, and gave some elements on the limit occupation measure of $I^{(n)}$ . Here, we prove under some conditions, finite dimensional distributions of $n$ th iterated two-sided stable processes converge, and the same holds the reflected Brownian motions. We give a description of the law of $I[k]$ , of the finite dimensional distributions of $I^{(n)}$ , as well as those of the iterated reflected Brownian motion iterated ad libitum.

preprint2014arXiv

A new encoding of coalescent processes. Applications to the additive and multiplicative cases

We revisit the discrete additive and multiplicative coalescents, starting with $n$ particles with unit mass. These cases are known to be related to some "combinatorial coalescent processes": a time reversal of a fragmentation of Cayley trees or a parking scheme in the additive case, and the random graph process $(G(n,p))_p$ in the multiplicative case. Time being fixed, encoding these combinatorial objects in real-valued processes indexed by the line is the key to describing the asymptotic behaviour of the masses as $n\to +\infty$ . We propose to use the Prim order on the vertices instead of the classical breadth-first (or depth-first) traversal to encode the combinatorial coalescent processes. In the additive case, this yields interesting connections between the different representations of the process. In the multiplicative case, it allows one to answer to a stronger version of an open question of Aldous [Ann. Probab., vol. 25, pp. 812--854, 1997]: we prove that not only the sequence of (rescaled) masses, seen as a process indexed by the time $λ$ , converges in distribution to the reordered sequence of lengths of the excursions above the current minimum of a Brownian motion with parabolic drift $(B_t+λt - t^2/2, t\geq 0)$ , but we also construct a version of the standard augmented multiplicative coalescent of Bhamidi, Budhiraja and Wang [Probab. Theory Rel., to appear] using an additional Poisson point process.

preprint2014arXiv

Compact convex sets of the plane and probability theory

The Gauss-Minkowski correspondence in $\mathbb{R}^2$ states the existence of a homeomorphism between the probability measures $μ$ on $[0,2π]$ such that $\int_0^{2π} e^{ix}dμ(x)=0$ and the compact convex sets (CCS) of the plane with perimeter~1. In this article, we bring out explicit formulas relating the border of a CCS to its probability measure. As a consequence, we show that some natural operations on CCS -- for example, the Minkowski sum -- have natural translations in terms of probability measure operations, and reciprocally, the convolution of measures translates into a new notion of convolution of CCS. Additionally, we give a proof that a polygonal curve associated with a sample of $n$ random variables (satisfying $\int_0^{2π} e^{ix}dμ(x)=0$ ) converges to a CCS associated with $μ$ at speed $\sqrt{n}$ , a result much similar to the convergence of the empirical process in statistics. Finally, we employ this correspondence to present models of smooth random CCS and simulations.

preprint2014arXiv

Probability that n random points in a disk are in convex position

In this paper we give a formula for the probability that $n$ random points chosen under the uniform distribution in a disk are in convex position. While close, the formula is recursive and is totally explicit only for the first values of $n$ .

preprint2013arXiv

A functional central limit theorem for the partial sums of sorted i.i.d. random variables

Let $(X_i,i\geq 1)$ be a sequence of i.i.d. random variables with values in $[0,1]$ , and $f$ be a function such that $`E(f(X_1)^2)<+\infty$ . We show a functional central limit theorem for the process $t\mapsto \sum_{i=1}^n f(X_i)1_{X_i\leq t}$ .

preprint2012arXiv

A natural stochastic extension of the sandpile model on a graph

We introduce a new model of a stochastic sandpile on a graph $G$ containing a sink. When unstable, a site sends one grain to each of its neighbours independently with probability $p \in (0,1]$ . For $p=1$ , this coincides with the standard Abelian sandpile model. In general, for $p\in(0,1)$ , the set of recurrent configurations of this sandpile model is different from that of the Abelian sandpile model. We give a characterisation of this set in terms of orientations of the graph $G$ . We also define the lacking polynomial $L_G$ as the generating function counting this set according to the number of grains, and show that this polynomial satisfies a recurrence which resembles that of the Tutte polynomial.

preprint2012arXiv

Asymptotics of trees with a prescribed degree sequence and applications

Let $t$ be a rooted tree and $n_i(t)$ the number of nodes in $t$ having $i$ children. The degree sequence $(n_i(t),i\geq 0)$ of $t$ satisfies $\sum_{i\ge 0} n_i(t)=1+\sum_{i\ge 0} in_i(t)=|t|$ , where $|t|$ denotes the number of nodes in $t$ . In this paper, we consider trees sampled uniformly among all trees having the same degree sequence $\ds$; we write $`P_\ds$ for the corresponding distribution. Let $\ds(κ)=(n_i(κ),i\geq 0)$ be a list of degree sequences indexed by $κ$ corresponding to trees with size $\nk\to+\infty$. We show that under some simple and natural hypotheses on $(\ds(κ),κ>0)$ the trees sampled under $`P_{\ds(κ)}$ converge to the Brownian continuum random tree after normalisation by $\nk^{1/2}$. Some applications concerning Galton--Watson trees and coalescence processes are provided.

preprint2012arXiv

Directed animals, quadratic and rewriting systems

A directed animal is a percolation cluster in the directed site percolation model. The aim of this paper is to exhibit a strong relation between the problem of computing the generating function $\G$ of directed animals on the square lattice, counted according to the area and the perimeter, and the problem of solving a system of quadratic equations involving unknown matrices. We present some solid evidence that some infinite explicit matrices, the fixed points of a rewriting like system are the natural solutions to this system of equations: some strong evidence is given that the problem of finding $\G$ reduces to the problem of finding an eigenvector to an explicit infinite matrix. Similar properties are shown for other combinatorial questions concerning directed animals, and for different lattices.

preprint2012arXiv

Many empty triangles have a common edge

Given a finite point set $X$ in the plane, the degree of a pair $\{x,y\} \subset X$ is the number of empty triangles $t=conv\{x,y,z\}$ , where empty means $t\cap X=\{x,y,z\}$ . Define $deg X$ as the maximal degree of a pair in $X$ . Our main result is that if $X$ is a random sample of $n$ independent and uniform points from a fixed convex body, then $deg X \ge cn/\ln n$ in expectation.

preprint2011arXiv

Asymptotic of geometrical navigation on a random set of points of the plane

A navigation on a set of points $S$ is a rule for choosing which point to move to from the present point in order to progress toward a specified target. We study some navigations in the plane where $S$ is a non uniform Poisson point process (in a finite domain) with intensity going to $+\infty$ . We show the convergence of the traveller path lengths, the number of stages done, and the geometry of the traveller trajectories, uniformly for all starting points and targets, for several navigations of geometric nature. Other costs are also considered. This leads to asymptotic results on the stretch factors of random Yao-graphs and random $θ$ -graphs.

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.

Jean-François Marckert

Research overview

Is this your work?

16 publications

A combinatorial proof of Aldous-Broder theorem for general Markov chains

Iterated foldings of discrete spaces and their limits: candidates for the role of Brownian map in higher dimensions

The combinatorics of the colliding bullets problem

Around Sylvester's question in the plane

Election algorithms with random delays in trees

Markovianity of the invariant distribution of probabilistic cellular automata on the line

Processes iterated ad libitum

A new encoding of coalescent processes. Applications to the additive and multiplicative cases

Compact convex sets of the plane and probability theory

Probability that n random points in a disk are in convex position

A functional central limit theorem for the partial sums of sorted i.i.d. random variables

A natural stochastic extension of the sandpile model on a graph

Asymptotics of trees with a prescribed degree sequence and applications

Directed animals, quadratic and rewriting systems

Many empty triangles have a common edge

Asymptotic of geometrical navigation on a random set of points of the plane

See the researcher in context

Building this map preview