Notice
A notion of entropy for limits of sparse marked graphs (workshop ERC Nemo Processus ponctuels et graphes aléatoires unimodulaires)
- document 1 document 2 document 3
- niveau 1 niveau 2 niveau 3
Descriptif
Bordenave and Caputo (2014) defined a notion of entropy for probability distributions on rooted graphs with finite expected degree at the root. When such a probability distribution \rho has finite BC entropy \Sigma(\rho), the growth in the number of vertices n of the number of graphs on n vertices whose associated rooted graph distribution is close to \rho is as d/2 n \log n + \Sigma(\rho) n + o(n), where d is expected degree of the root under \rho. We develop the parallel result for probability distributions on marked rooted graphs. Our graphs have vertex marks drawn from a finite set and directed edge marks, one towards each vertex, drawn from a finite set. The talk will focus on presenting an overview of the technical details of this extension We are motivated by the interpretation of a discrete time stochastic process taking values in a finite set \Theta as the local weak limit of long strings of symbols from \Theta. We argue that probability distributions on marked rooted graphs are the natural analogs of stochastic process models for *graphical data*, by which we mean data indexed by the vertices and edges of a sparse graph rather than by linearly ordered time. Our extension of the BC entropy can then be argued to be the natural extension, in the world of graphical data, of the Shannon entropy rate in the world of time series. We illustrate this viewpoint by proving a lossless data compression theorem analogous to the basic lossless data compression theorem for time series. Joint work with Payam Delgosha.
Thème
Documentation
Documents pédagogiques
Dans la même collection
-
On the notion of dimension of unimodular discrete spaces (workshop ERC Nemo Processus ponctuels et …
KhezeliAliIn this talk we will define notions of dimension for unimodular random graphs and point-stationary point processes. These notions are in spirit similar to the Minkowski dimension and the
-
-
Stein-Malliavin method for discrete alpha stable point processes (workshop ERC Nemo Processus ponct…
DecreusefondLaurentThe notion of discrete alpha-stable point processes generalizes to point processes the notion of stable distribution. It has been introduced and studied by Davydov, Molchanov and Zuyev a few
-
Strict monotonicity of percolation thresholds under covering maps (workshop ERC Nemo Processus ponc…
MartineauSébastienPercolation is a model for propagation in porous media that as introduced in 1957 by Broadbent and Hammersley. An infinite graph G models the geometry of the situation and a parameter p
-
Sampling cluster point processes: a review (workshop ERC Nemo Processus ponctuels et graphes aléato…
BrémaudPierreThe theme of this talk is the sampling of cluster and iterated cluster point processes. It is partially a review, mainly of the Brix–Kendall exact sampling method for cluster point processes and
-
Eternal family trees and dynamics on unimodular random graphs (workshop ERC Nemo Processus ponctuel…
Haji MirsadeghiMir OmidThis talk is centered on covariant dynamics on unimodular random graphs and random networks (marked graphs), namely maps from the set of vertices to itself which are preserved by graph or
-
On the modified Palm version (workshop ERC Nemo Processus ponctuels et graphes aléatoires unimodula…
ThorissonHermannThe Palm version of a stationary random measure is an important tool in probability. It is however not well known that there are in fact two Palm versions, with related but different
-
Subdiffusivity of random walks on random planar maps, via stationarity (workshop ERC Nemo Processus…
CurienNicolasRandom planar maps have been the subject of numerous studies over the last years. They are instance of stationary and reversible random planar maps exhibiting a non-conventional geometry at
-
Spectral embedding for graph classification (workshop ERC Nemo Processus ponctuels et graphes aléat…
LelargeMarcLearning on graphs requires a graph feature representation able to discriminate among different graphs while being amenable to fast computation. The graph isomorphism problem tells us that no
-
A stable marriage between order and disorder (workshop ERC Nemo Processus ponctuels et graphes aléa…
LastGünterStable matchings were introduced in a seminal paper by Gale and Shapley (1962) and play an important role in economics. Following closely Holroyd, Pemantle, Peres and Schramm (2009), we shall
-
Comments and problems regarding large graphs. (workshop ERC Nemo Processus ponctuels et graphes alé…
BenjaminiItaiWe will discuss a couple of results and questions regarding the structure of large graphs. These include vertex transitive graphs, expanders and random graphs.
-
Central Limit theorem for quasi-local statistics of point processes with fast decay of correlations…
We shall consider Euclidean stationary point processes which have fast decay of correlations i.e., their correlation functions factorize upto an additive error decaying exponentially in the
Avec les mêmes intervenants et intervenantes
-
Reversible Markov decision processes
AnantharamVenkatA Markov decision process is called reversible if for every stationary Markov control strategy the resulting Markov chain is reversible.
