<figure><img src="image_1.png" /></figure>

HAL
open science

# Some recent advances in random walks and random environments

Alexis Devulder, Roland Diel, Xiaolin Zeng

<figure><img src="image_2.png" /></figure>

## To cite this version:

Alexis Devulder, Roland Diel, Xiaolin Zeng. Some recent advances in random walks and random environments. ESAIM: Proceedings and Surveys, 2023, 74, pp.38-50. 10.1051/proc/202374038. hal-04477619

HAL Id: hal-04477619

https://hal.science/hal-04477619

Submitted on 13 Jun 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_3.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
<figure><img src="image_1.png" /></figure>

HAL
open science

Some recent advances in random walks and random environments

Alexis Devulder, Roland Diel, Xiaolin Zeng

<figure><img src="image_2.png" /></figure>

To cite this version:

Alexis Devulder, Roland Diel, Xiaolin Zeng. Some recent advances in random walks and random environments. ESAIM: Proceedings and Surveys, 2023, 74, pp.38-50. 10.1051/proc/202374038. hal-04477619

HAL Id: hal-04477619

https://hal.science/hal-04477619v1

Submitted on 13 Jun 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_3.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# SOME RECENT ADVANCES IN RANDOM WALKS AND RANDOM ENVIRONMENTS*

ALEXIS DEVULDER<fnref n="1" />, ROLAND DIEL<fnref n="2" /> AND XIAOLIN ZENG<fnref n="3" />

**Abstract.** Recent contributions to random walks in random environments and related topics are presented. We focus on non parametric estimation for one dimensional random walks in random environment and on the Dirichlet distribution on decomposable graphs.

**Résumé.** Nous présentons de récentes contributions concernant les marches aléatoires en milieux aléatoires et des sujets qui leurs sont reliés. Nous nous intéressons en particulier à l'estimation non paramétrique pour les marches aléatoires en milieu aléatoire unidimensionnelles, et à la loi de Dirichlet sur des graphes décomposables.

## INTRODUCTION

We are interested in random walks in random environments (RWRE). RWRE on $\mathbb{Z}$ are defined as follows. Throughout the paper, we write $\mathbb{N} = \mathbb{Z}_+ = \{0, 1, 2, \dots\}$. Let $\omega = (\omega_x)_{x \in \mathbb{Z}}$ be an i.i.d. sequence of random variables taking values in $(0, 1)$, with common distribution $\nu$. Given a realization of $\omega$, let $S = (S_t)_{t \in \mathbb{N}}$ denote the random walk in the environment $\omega$, which is the Markov chain on $\mathbb{Z}$ starting at $S_0 = 0$ and with probability transitions, for every $t \in \mathbb{N}$:

$$ \mathbb{P}_{\omega}(S_{t+1} = y | S_t = x) = \begin{cases} \omega_x & \text{if } y = x + 1, \\ 1 - \omega_x & \text{if } y = x - 1, \\ 0 & \text{otherwise.} \end{cases} \qquad (1) $$

Hence, $S = (S_t)_{t \in \mathbb{N}}$ is a random walk in the random environment $\omega$. The probability measure $\mathbb{P}_{\omega}$ of the chain, conditionally on the environment $\omega$, is called the *quenched* distribution, while the unconditional distribution

$$ \mathbb{P}^{\nu}(\cdot) = \int \mathbb{P}_{\omega}(\cdot) \nu^{\otimes \mathbb{Z}}(d\omega) \qquad (2) $$

is called the *annealed* distribution.

<footnote>* X. Z. acknowledges the Agence Nationale de la Recherche for their financial support via ANR grant RAW ANR-20-CE40-0012-01.</footnote>

<footnote n="1">¹ Université Paris-Saclay, UVSQ, CNRS, Laboratoire de Mathématiques de Versailles, 78000 Versailles, France; e-mail: devulder@math.uvsq.fr.</footnote>

<footnote n="2">² Université Côte d'Azur, CNRS, LJAD, France; e-mail: roland.diel@univ-cotedazur.fr</footnote>

<footnote n="3">³ Institut de Recherche Mathématique Avancée, UMR 7501, Université de Strasbourg, 7 rue René Descartes, 67084 Strasbourg, France; e-mail: zeng@math.unistra.fr.</footnote>
# SOME RECENT ADVANCES IN RANDOM WALKS AND RANDOM ENVIRONMENTS*

ALEXIS DEVULDER<fnref n="1" />, ROLAND DIEL<fnref n="2" /> AND XIAOLIN ZENG<fnref n="3" />

**Abstract.** Recent contributions to random walks in random environments and related topics are presented. We focus on non parametric estimation for one dimensional random walks in random environment and on the Dirichlet distribution on decomposable graphs.

**Résumé.** Nous présentons de récentes contributions concernant les marches aléatoires en milieux aléatoires et des sujets qui leurs sont reliés. Nous nous intéressons en particulier à l'estimation non paramétrique pour les marches aléatoires en milieu aléatoire unidimensionnelles, et à la loi de Dirichlet sur des graphes décomposables.

## INTRODUCTION

We are interested in random walks in random environments (RWRE). RWRE on $\mathbb{Z}$ are defined as follows. Throughout the paper, we write $\mathbb{N} = \mathbb{Z}_+ = \{0, 1, 2, \dots\}$. Let $\omega = (\omega_x)_{x \in \mathbb{Z}}$ be an i.i.d. sequence of random variables taking values in $(0, 1)$, with common distribution $\nu$. Given a realization of $\omega$, let $S = (S_t)_{t \in \mathbb{N}}$ denote the random walk in the environment $\omega$, which is the Markov chain on $\mathbb{Z}$ starting at $S_0 = 0$ and with probability transitions, for every $t \in \mathbb{N}$:

$$ \mathbb{P}_{\omega}(S_{t+1} = y | S_t = x) = \begin{cases} \omega_x & \text{if } y = x + 1, \\ 1 - \omega_x & \text{if } y = x - 1, \\ 0 & \text{otherwise.} \end{cases} \qquad (1) $$

Hence, $S = (S_t)_{t \in \mathbb{N}}$ is a random walk in the random environment $\omega$. The probability measure $\mathbb{P}_{\omega}$ of the chain, conditionally on the environment $\omega$, is called the *quenched* distribution, while the unconditional distribution

$$ \mathbb{P}^{\nu}(\cdot) = \int \mathbb{P}_{\omega}(\cdot) \nu^{\otimes \mathbb{Z}}(d\omega) \qquad (2) $$

is called the *annealed* distribution.

<footnote>* X. Z. acknowledges the Agence Nationale de la Recherche for their financial support via ANR grant RAW ANR-20-CE40-0012-01.</footnote>

<footnote n="1">¹ Université Paris-Saclay, UVSQ, CNRS, Laboratoire de Mathématiques de Versailles, 78000 Versailles, France; e-mail: devulder@math.uvsq.fr.</footnote>

<footnote n="2">² Université Côte d'Azur, CNRS, LJAD, France; e-mail: roland.diel@univ-cotedazur.fr</footnote>

<footnote n="3">³ Institut de Recherche Mathématique Avancée, UMR 7501, Université de Strasbourg, 7 rue René Descartes, 67084 Strasbourg, France; e-mail: zeng@math.unistra.fr.</footnote>
A continuous time and space analogue of RWRE on $\mathbb{Z}$ is introduced by Schumacher [31] and Brox [5]. See Shi [32] for some applications of such model and stochastic calculus to RWRE.

Also, RWRE can be generalised on $\mathbb{Z}^d$ for $d \ge 1$ as follows. Let $(e_1, e_2, \dots, e_d)$ be the canonical basis of $\mathbb{Z}^d$. We also set $e_{d+i} = -e_i$ for all $1 \le i \le d$. Hence, $(e_1, \dots, e_{2d})$ is the set of unit vectors of $\mathbb{Z}^d$. We consider a collection $\omega = (\omega(x, x + e_i), 1 \le i \le 2d, x \in \mathbb{Z}^d)$ of random variables, with joint law $\eta$, such that $\sum_{i=1}^{2d} \omega(x, x + e_i) = 1$ for every $x \in \mathbb{Z}^d$ and $\omega(x, x + e_i) \in (0, 1)$ for all $x \in \mathbb{Z}^d$ and $1 \le i \le 2d$. Given a realization of $\omega$, the random walk in the environment $\omega$ is the Markov chain $S = (S_t)_{t \in \mathbb{N}}$ on $\mathbb{Z}^d$ starting at $S_0 = (0, \dots, 0)$ and with probability transitions:

$$ \mathbb{P}_{\omega}(S_{t+1} = x + e_i | S_t = x) = \omega(x, x + e_i), \quad x \in \mathbb{Z}^d, i \in \{1, \dots, 2d\}, t \in \mathbb{N}. $$

Once more, $\mathbb{P}_{\omega}$ is the quenched law of $S$. The annealed law of $S$ is defined as

$$ \mathbb{P}(\cdot) = \int \mathbb{P}_{\omega}(\cdot) \eta(d\omega). $$

The more classical model of RWRE is the case where $(\omega(x, x + e_i), 1 \le i \le 2d), x \in \mathbb{Z}^d$ are independent with the same law $\nu$, that is, the transition probabilities at each site $x \in \mathbb{Z}^d$ are independent with the same law $\nu$.

Since the works of Chernov [7] in biophysics and of Temkin [35] in metallurgy, RWRE have attracted a considerable interest, both in Mathematics and in Physics. Also, RWRE have many applications in physics (see for example Hughes [20]) and in biology (see e.g. Cocco and Monasson [8]). Moreover, RWRE are used to define or study some other mathematical models, see e.g. [24] (Chapter 3) for random walks in oriented lattices with random environments, [38] for random walks in random environments with random scenery, [4] for branching processes in random environments, [12] for branching random walks in random environments, and [14] for the internal DLA cluster generated by Sinai's walk. For a general account on RWRE, we refer to Zeitouni [36] and Révész [28].

A particular case of RWRE on $\mathbb{Z}^d$ is the case where the transition probabilities are i.i.d. at each site with a Dirichlet distribution. Such RWRE, also called random walks in Dirichlet environments (RWDE), are related to reinforced random walks, and more precisely, the annealed law of RWDE is that of a reinforced random walk with linear reinforcement on directed edges. For an overview of RWRE in Dirichlet environments, see Sabot and Tournier [30].

We present in Section 1 results obtained in [13] by R. Diel and M. Lerasle about non parametric estimation for one dimensional RWRE.

Then Section 2 deals with a generalization of the Dirichlet distribution, depending on a finite decomposable graph. One possible application could be to establish a link between such laws and random walks in random environments on graphs. This section is a joint work of Bartosz Kołodziejek and Jacek Wesolowski (both from Warsaw University of Technology) with Xiaolin Zeng.

Finally, a third talk of this session was given by Xinxin Chen about fixed points for branching Brownian motions.

Acknowledgement: We are thankful to two anonymous referees for their very careful reading of the paper and for their useful comments.

# 1. NON PARAMETRIC ESTIMATION FOR RANDOM WALKS IN RANDOM ENVIRONMENT

This part is based on [13] by R. Diel and M. Lerasle.

## 1.1. Introduction

The topic of statistical inference for RWRE emerged with the appearance of statistical data fitting this model such as data related to the DNA-unzipping experiment or DNA-polymerase phenomenon. We are interested here in estimating the distribution of the random environment from the observation of one trajectory of a RWRE on
A continuous time and space analogue of RWRE on $\mathbb{Z}$ is introduced by Schumacher [31] and Brox [5]. See Shi [32] for some applications of such model and stochastic calculus to RWRE.

Also, RWRE can be generalised on $\mathbb{Z}^d$ for $d \ge 1$ as follows. Let $(e_1, e_2, \dots, e_d)$ be the canonical basis of $\mathbb{Z}^d$. We also set $e_{d+i} = -e_i$ for all $1 \le i \le d$. Hence, $(e_1, \dots, e_{2d})$ is the set of unit vectors of $\mathbb{Z}^d$. We consider a collection $\omega = (\omega(x, x + e_i), 1 \le i \le 2d, x \in \mathbb{Z}^d)$ of random variables, with joint law $\eta$, such that $\sum_{i=1}^{2d} \omega(x, x + e_i) = 1$ for every $x \in \mathbb{Z}^d$ and $\omega(x, x + e_i) \in (0, 1)$ for all $x \in \mathbb{Z}^d$ and $1 \le i \le 2d$. Given a realization of $\omega$, the random walk in the environment $\omega$ is the Markov chain $S = (S_t)_{t \in \mathbb{N}}$ on $\mathbb{Z}^d$ starting at $S_0 = (0, \dots, 0)$ and with probability transitions:

$$ \mathbb{P}_{\omega}(S_{t+1} = x + e_i | S_t = x) = \omega(x, x + e_i), \quad x \in \mathbb{Z}^d, i \in \{1, \dots, 2d\}, t \in \mathbb{N}. $$

Once more, $\mathbb{P}_{\omega}$ is the quenched law of $S$. The annealed law of $S$ is defined as

$$ \mathbb{P}(\cdot) = \int \mathbb{P}_{\omega}(\cdot) \eta(d\omega). $$

The more classical model of RWRE is the case where $(\omega(x, x + e_i), 1 \le i \le 2d), x \in \mathbb{Z}^d$ are independent with the same law $\nu$, that is, the transition probabilities at each site $x \in \mathbb{Z}^d$ are independent with the same law $\nu$.

Since the works of Chernov [7] in biophysics and of Temkin [35] in metallurgy, RWRE have attracted a considerable interest, both in Mathematics and in Physics. Also, RWRE have many applications in physics (see for example Hughes [20]) and in biology (see e.g. Cocco and Monasson [8]). Moreover, RWRE are used to define or study some other mathematical models, see e.g. [24] (Chapter 3) for random walks in oriented lattices with random environments, [38] for random walks in random environments with random scenery, [4] for branching processes in random environments, [12] for branching random walks in random environments, and [14] for the internal DLA cluster generated by Sinai's walk. For a general account on RWRE, we refer to Zeitouni [36] and Révész [28].

A particular case of RWRE on $\mathbb{Z}^d$ is the case where the transition probabilities are i.i.d. at each site with a Dirichlet distribution. Such RWRE, also called random walks in Dirichlet environments (RWDE), are related to reinforced random walks, and more precisely, the annealed law of RWDE is that of a reinforced random walk with linear reinforcement on directed edges. For an overview of RWRE in Dirichlet environments, see Sabot and Tournier [30].

We present in Section 1 results obtained in [13] by R. Diel and M. Lerasle about non parametric estimation for one dimensional RWRE.

Then Section 2 deals with a generalization of the Dirichlet distribution, depending on a finite decomposable graph. One possible application could be to establish a link between such laws and random walks in random environments on graphs. This section is a joint work of Bartosz Kołodziejek and Jacek Wesolowski (both from Warsaw University of Technology) with Xiaolin Zeng.

Finally, a third talk of this session was given by Xinxin Chen about fixed points for branching Brownian motions.

Acknowledgement: We are thankful to two anonymous referees for their very careful reading of the paper and for their useful comments.

# 1. NON PARAMETRIC ESTIMATION FOR RANDOM WALKS IN RANDOM ENVIRONMENT

This part is based on [13] by R. Diel and M. Lerasle.

## 1.1. Introduction

The topic of statistical inference for RWRE emerged with the appearance of statistical data fitting this model such as data related to the DNA-unzipping experiment or DNA-polymerase phenomenon. We are interested here in estimating the distribution of the random environment from the observation of one trajectory of a RWRE on
Z. The problem considered may also be useful in applications where one wants to recover the environment itself. Indeed, a purely frequentist estimator of the environment has poor performances on sites where the walk only spent a short time, it is likely to be outperformed by a Bayesian estimator, provided that the prior distribution is reasonably chosen. An estimator of the law of the environment could provide such a reasonable prior.

In the literature, the problem was originally considered in [1] who introduced an estimator of the moments of the distribution. The state space of the walk in [1] is more general than Z but their estimators have a huge variance, they are therefore unstable and cannot really be used in practice. More recently, [9, 10, 15, 16] considered the random walk on Z and investigated the problem in a parametric framework. The case of Markovian environment has also been investigated in [3]. Although very interesting, this approach suffers several drawbacks. Indeed, the quality of the estimator strongly relies on the assumption that the unknown distribution lies in a parametric model which imposes severe restrictions for applications.

We present here a non-asymptotic and non-parametric approach to tackle the estimation of the unknown cumulative distribution function (c.d.f.) of the environment from one observation of the walk. All our concentration results are valid in any regime, the only difference lies in the convergence rate of the c.d.f. estimator. Our approach is based on the estimation of the moments of the unknown distribution, these estimations can always be performed in linear time. Those primary estimators are then combined to build a collection of estimators with non-increasing bias and non-decreasing variance and the final estimator is chosen among them according to Goldenshluger-Lepski's method [17]. The resulting estimator is therefore easily computable and satisfies an oracle type inequality. This approach has also been used in [19] to obtain results on the estimation of the probability density of the environment and in [2] to obtain convergence results in estimating the distribution of the environment of a RWRE on a tree.

## 1.2. Setting

We consider $\omega = (\omega_x)_{x \in \mathbb{Z}}$, an i.i.d. sequence of random variables taking values in $(0, 1)$, with common distribution $\nu$. The RWRE $S = (S_t)_{t \in \mathbb{N}}$ and the probability measures $P_\omega$ and $P^\nu$ are defined as in the introduction, respectively in (1) and (2). We denote by $\mathbb{E}^\nu$ the expectation with respect to $P^\nu$.

Here we construct an estimator of the c.d.f. of $\nu$ built from one trajectory of the walk $(S_t)_{t \in \mathbb{N}}$. The asymptotic behaviour of the walk $(S_t)_{t \in \mathbb{N}}$ depends on the random variables $\rho_x = \frac{1-\omega_x}{\omega_x}$, $x \in \mathbb{Z}$. Results of Kesten, Kozlov and Spitzer [22] and Sinaï [33] give a precise description of the different possible behaviours. Our main result is valid either under the assumptions of [22] or under a slightly weaker version of the ones given in [33] which we present in the following global assumption:

$$ 
\left\{ 
\begin{array}{l}
\mathbb{E}^{\nu}[\log \rho_0] = 0, \mathbb{E}^{\nu}[(\log \rho_0)^2] > 0 \text{ and } \exists a > 0, \mathbb{E}^{\nu}[\rho_0^a] + \mathbb{E}^{\nu}[\rho_0^{-a}] < +\infty \\
\text{or} \\
\mathbb{E}^{\nu}[\log \rho_0] < 0, \log \rho_0 \text{ has a non arithmetic distribution} \\
\text{and } \exists \kappa \in (0, \infty), \mathbb{E}^{\nu}[\rho_0^{\kappa}] = 1 \text{ and } \mathbb{E}^{\nu}[\rho_0^{\kappa} \log(1 \vee \rho_0)] < \infty.
\end{array}
\right. 
\quad (\mathbf{H})
$$

Under $(\mathbf{H})$, we know since Solomon [34] that $(S_t)_{t \in \mathbb{N}}$ is either transient to the right for almost every environment when $\mathbb{E}^{\nu}[\log \rho_0] < 0$, or recurrent for almost every environment when $\mathbb{E}^{\nu}[\log \rho_0] = 0$.

Let us first recall the results obtained in [22] and [33]. Denote by

$$T_n = \inf \{t \in \mathbb{N}, S_t = n\}$$

the first hitting time of a site $n \in \mathbb{N}$. Precisely,

* if $\mathbb{E}^{\nu}[\log \rho_0] < 0$ (transient case, [22]):

1. if $\kappa < 1$, then $T_n/n^{1/\kappa}$ and $S_t/t^\kappa$ converge in distribution to some non trivial distributions,

2. if $\kappa = 1$, then $\frac{T_n}{n \log n}$ and $\frac{\log t}{t} S_t$ converge in probability to non zero constants,

3. if $\kappa > 1$, then $\frac{T_n}{n}$ and $\frac{S_t}{t}$ converge in probability to non zero constants.
Z. The problem considered may also be useful in applications where one wants to recover the environment itself. Indeed, a purely frequentist estimator of the environment has poor performances on sites where the walk only spent a short time, it is likely to be outperformed by a Bayesian estimator, provided that the prior distribution is reasonably chosen. An estimator of the law of the environment could provide such a reasonable prior.

In the literature, the problem was originally considered in [1] who introduced an estimator of the moments of the distribution. The state space of the walk in [1] is more general than Z but their estimators have a huge variance, they are therefore unstable and cannot really be used in practice. More recently, [9, 10, 15, 16] considered the random walk on Z and investigated the problem in a parametric framework. The case of Markovian environment has also been investigated in [3]. Although very interesting, this approach suffers several drawbacks. Indeed, the quality of the estimator strongly relies on the assumption that the unknown distribution lies in a parametric model which imposes severe restrictions for applications.

We present here a non-asymptotic and non-parametric approach to tackle the estimation of the unknown cumulative distribution function (c.d.f.) of the environment from one observation of the walk. All our concentration results are valid in any regime, the only difference lies in the convergence rate of the c.d.f. estimator. Our approach is based on the estimation of the moments of the unknown distribution, these estimations can always be performed in linear time. Those primary estimators are then combined to build a collection of estimators with non-increasing bias and non-decreasing variance and the final estimator is chosen among them according to Goldenshluger-Lepski's method [17]. The resulting estimator is therefore easily computable and satisfies an oracle type inequality. This approach has also been used in [19] to obtain results on the estimation of the probability density of the environment and in [2] to obtain convergence results in estimating the distribution of the environment of a RWRE on a tree.

## 1.2. Setting

We consider $\omega = (\omega_x)_{x \in \mathbb{Z}}$, an i.i.d. sequence of random variables taking values in $(0, 1)$, with common distribution $\nu$. The RWRE $S = (S_t)_{t \in \mathbb{N}}$ and the probability measures $P_\omega$ and $P^\nu$ are defined as in the introduction, respectively in (1) and (2). We denote by $\mathbb{E}^\nu$ the expectation with respect to $P^\nu$.

Here we construct an estimator of the c.d.f. of $\nu$ built from one trajectory of the walk $(S_t)_{t \in \mathbb{N}}$. The asymptotic behaviour of the walk $(S_t)_{t \in \mathbb{N}}$ depends on the random variables $\rho_x = \frac{1-\omega_x}{\omega_x}$, $x \in \mathbb{Z}$. Results of Kesten, Kozlov and Spitzer [22] and Sinaï [33] give a precise description of the different possible behaviours. Our main result is valid either under the assumptions of [22] or under a slightly weaker version of the ones given in [33] which we present in the following global assumption:

$$ \left\{ \begin{array}{ll} \mathbb{E}^\nu[\log \rho_0] = 0, \mathbb{E}^\nu[(\log \rho_0)^2] > 0 \text{ and } \exists a > 0, \mathbb{E}^\nu[\rho_0^a] + \mathbb{E}^\nu[\rho_0^{-a}] < +\infty & \text{(H)} \\ \text{or} \\ \mathbb{E}^\nu[\log \rho_0] < 0, \log \rho_0 \text{ has a non arithmetic distribution} & \\ \text{and } \exists \kappa \in (0, \infty), \mathbb{E}^\nu[\rho_0^\kappa] = 1 \text{ and } \mathbb{E}^\nu[\rho_0^\kappa \log(1 \vee \rho_0)] < \infty. & \end{array} \right. $$

Under (H), we know since Solomon [34] that $(S_t)_{t \in \mathbb{N}}$ is either transient to the right for almost every environment when $\mathbb{E}^\nu[\log \rho_0] < 0$, or recurrent for almost every environment when $\mathbb{E}^\nu[\log \rho_0] = 0$.

Let us first recall the results obtained in [22] and [33]. Denote by

$$ T_n = \inf \{t \in \mathbb{N}, S_t = n\} $$

the first hitting time of a site $n \in \mathbb{N}$. Precisely,

* if $\mathbb{E}^\nu[\log \rho_0] < 0$ (transient case, [22]):

1. if $\kappa < 1$, then $T_n/n^{1/\kappa}$ and $S_t/t^\kappa$ converge in distribution to some non trivial distributions,

2. if $\kappa = 1$, then $\frac{T_n}{n \log n}$ and $\frac{\log t}{t} S_t$ converge in probability to non zero constants,

3. if $\kappa > 1$, then $\frac{T_n}{n}$ and $\frac{S_t}{t}$ converge in probability to non zero constants.
• if $\mathbb{E}^{\nu}[\log \rho_0] = 0$ (recurrent case, [33]) then $S_t/(\log t)^2$ converges in distribution to a non trivial limit.

When $\kappa$ exists, a simple convexity argument shows that it is unique. In all cases, $T_n$ is almost surely finite for any $n \in \mathbb{N}$.

We give an estimator of the c.d.f. $F$ of $\nu$ using the path $S_{[0,T_n]} = \{S_t, 0 \le t \le T_n\}$. Even if they do not have an explicit formulation, these estimators are easily computable as we will see in the next sections.

**Theorem 1.1.** Suppose that the c.d.f. $F$ of $\nu$ is $\gamma$-Hölder for some $\gamma \in (0, 2]$ and that $\nu$ satisfies Assumption (H). There exists a constant $C_\nu$ depending on the distribution $\nu$ such that, for any integer $n \ge 2$, there exists an estimator $\hat{F}_n = f_n(S_{[0,T_n]})$ of the c.d.f. $F$ satisfying

$$ \mathbb{E}^{\nu} \left[ \| \hat{F}_n - F \|_{\infty} \right] \le \begin{cases} C_{\nu} \left( \frac{\log n}{n} \right)^{\frac{\gamma}{2\gamma+4\kappa}} & \text{if } \mathbb{E}^{\nu} [\log \rho_0] < 0, \\ C_{\nu} \frac{\log n}{\sqrt{n}} & \text{if } \mathbb{E}^{\nu} [\log \rho_0] = 0. \end{cases} $$

Moreover, for any integer $n \ge 1$ and any real number $z > 0$, there exists an estimator $\hat{F}_n^z = f_n^z(S_{[0,T_n]})$ such that if $\mathbb{E}^{\nu}[\log \rho_0] < 0$,

$$ \mathbb{P}^{\nu} \left( \| \hat{F}_n^z - F \|_{\infty} \ge C_{\nu} \left( \frac{z + \log n}{n} \right)^{\frac{\gamma}{2\gamma+4\kappa}} \right) \le e^{-z}. $$

In the recurrent case, the rate $\log n/\sqrt{n}$ is, up to the logarithmic factor, the rate of convergence of the empirical c.d.f. when the environment $(\omega_x)_{0 \le x \le n}$ is observed. This is the best rate reached by our estimator expressed in terms of the number $n$ of visited sites. This is not surprising since the walk visits each site many times and can basically learn the environment itself. In the transient regime, the rate deteriorates as $\kappa$ increases; this was also expected since the walk derives faster to infinity in this case and time $T_n$ is smaller. This is a reason why it can be more natural to express the rates of convergence as functions of the number $T_n$ of observed steps of the walk. Combining Theorem 1.1 with convergence results for the distribution of $T_n$, see [22] for the transient case and [18] for the recurrent case, yields the following corollary.

**Corollary 1.2.** Grant the conditions of Theorem 1.1. For any positive increasing function $f$ such that $\lim_{x \to +\infty} f(x) = +\infty$,

$$ \lim_{n \to \infty} \mathbb{P}^{\nu} \left( \| \hat{F}_n - F \|_{\infty} \ge r(T_n) f(T_n) \right) = 0, \\ \text{where} \quad \begin{cases} r(T_n) = \frac{\log \log T_n}{\log T_n} & \text{when } \mathbb{E}^{\nu} [\log \rho_0] = 0, \\ r(T_n) = \left( \frac{(\log T_n)^{1/\kappa}}{T_n} \right)^{\frac{\gamma\kappa}{2\gamma+4\kappa}} & \text{when } \mathbb{E}^{\nu} [\log \rho_0] < 0, 0 < \kappa < 1, \\ r(T_n) = \left( \frac{(\log T_n)^2}{T_n} \right)^{\frac{\gamma}{2\gamma+4}} & \text{when } \mathbb{E}^{\nu} [\log \rho_0] < 0, \kappa = 1, \\ r(T_n) = \left( \frac{\log T_n}{T_n} \right)^{\frac{\gamma}{2\gamma+4\kappa}} & \text{when } \mathbb{E}^{\nu} [\log \rho_0] < 0, \kappa > 1. \end{cases} $$

In the original paper [13], there is a misprint in the rate for the case $\mathbb{E}^{\nu}[\log \rho_0] < 0, 0 < \kappa < 1$: it is easily checked that, as written above, the logarithmic term is $(\log T_n)^{1/\kappa}$ and not $\log T_n$.

In the non parametric case, there seems to be a trade-off between exploring more sites (increasing $\kappa$) to get information about more realizations of $\nu$ and spend more time on these sites (decreasing $\kappa$) to have a better knowledge of these realizations. And, in terms of $T_n$, the fastest convergence of the estimator is obtained for $\kappa = 1$. This looks surprising compared to the results of [16] where the rate $1/\sqrt{T_n}$ can be recovered in the ballistic regime ($\kappa > 1$).

The results of Theorem 1.1 and Corollary 1.2 are illustrated with some experiments on synthetic data using Beta distribution $B(a, b)$. In this example, $F$ is clearly infinitely differentiable and simple computations show that $\kappa = a - b$. Figures 1-4 show the estimates of the c.d.f. for various values of $\kappa$ and $n = 500$. They also provide the value of the selected model $\hat{M}_n$ and the value of the loss $N_{\infty} = \|F - \hat{F}_n^{\hat{M}_n}\|_{\infty}$. The red curve is the empirical c.d.f. knowing the environment $(\omega_x)_{0 \le x \le n-1}$.
• if $\mathbb{E}^{\nu}[\log \rho_0] = 0$ (recurrent case, [33]) then $S_t/(\log t)^2$ converges in distribution to a non trivial limit.

When $\kappa$ exists, a simple convexity argument shows that it is unique. In all cases, $T_n$ is almost surely finite for any $n \in \mathbb{N}$.

We give an estimator of the c.d.f. $F$ of $\nu$ using the path $S_{[0,T_n]} = \{S_t, 0 \le t \le T_n\}$. Even if they do not have an explicit formulation, these estimators are easily computable as we will see in the next sections.

**Theorem 1.1.** Suppose that the c.d.f. $F$ of $\nu$ is $\gamma$-Hölder for some $\gamma \in (0, 2]$ and that $\nu$ satisfies Assumption (H). There exists a constant $C_\nu$ depending on the distribution $\nu$ such that, for any integer $n \ge 2$, there exists an estimator $\hat{F}_n = f_n(S_{[0,T_n]})$ of the c.d.f. $F$ satisfying

$$ \mathbb{E}^{\nu} \left[ \| \hat{F}_n - F \|_{\infty} \right] \le \begin{cases} C_{\nu} \left( \frac{\log n}{n} \right)^{\frac{\gamma}{2\gamma+4\kappa}} & \text{if } \mathbb{E}^{\nu} [\log \rho_0] < 0, \\ C_{\nu} \frac{\log n}{\sqrt{n}} & \text{if } \mathbb{E}^{\nu} [\log \rho_0] = 0. \end{cases} $$

Moreover, for any integer $n \ge 1$ and any real number $z > 0$, there exists an estimator $\hat{F}_n^z = f_n^z(S_{[0,T_n]})$ such that if $\mathbb{E}^{\nu}[\log \rho_0] < 0$,

$$ \mathbb{P}^{\nu} \left( \| \hat{F}_n^z - F \|_{\infty} \ge C_{\nu} \left( \frac{z + \log n}{n} \right)^{\frac{\gamma}{2\gamma+4\kappa}} \right) \le e^{-z}. $$

In the recurrent case, the rate $\log n/\sqrt{n}$ is, up to the logarithmic factor, the rate of convergence of the empirical c.d.f. when the environment $(\omega_x)_{0 \le x \le n}$ is observed. This is the best rate reached by our estimator expressed in terms of the number $n$ of visited sites. This is not surprising since the walk visits each site many times and can basically learn the environment itself. In the transient regime, the rate deteriorates as $\kappa$ increases; this was also expected since the walk derives faster to infinity in this case and time $T_n$ is smaller. This is a reason why it can be more natural to express the rates of convergence as functions of the number $T_n$ of observed steps of the walk. Combining Theorem 1.1 with convergence results for the distribution of $T_n$, see [22] for the transient case and [18] for the recurrent case, yields the following corollary.

**Corollary 1.2.** Grant the conditions of Theorem 1.1. For any positive increasing function $f$ such that $\lim_{x \to +\infty} f(x) = +\infty$,

$$ \lim_{n \to \infty} \mathbb{P}^{\nu} \left( \| \hat{F}_n - F \|_{\infty} \ge r(T_n) f(T_n) \right) = 0, \\ \text{where} \quad \begin{cases} r(T_n) = \frac{\log \log T_n}{\log T_n} & \text{when } \mathbb{E}^{\nu}[\log \rho_0] = 0, \\ r(T_n) = \left( \frac{(\log T_n)^{1/\kappa}}{T_n} \right)^{\frac{\gamma\kappa}{2\gamma+4\kappa}} & \text{when } \mathbb{E}^{\nu}[\log \rho_0] < 0, 0 < \kappa < 1, \\ r(T_n) = \left( \frac{(\log T_n)^2}{T_n} \right)^{\frac{\gamma}{2\gamma+4}} & \text{when } \mathbb{E}^{\nu}[\log \rho_0] < 0, \kappa = 1, \\ r(T_n) = \left( \frac{\log T_n}{T_n} \right)^{\frac{\gamma}{2\gamma+4\kappa}} & \text{when } \mathbb{E}^{\nu}[\log \rho_0] < 0, \kappa > 1. \end{cases} $$

In the original paper [13], there is a misprint in the rate for the case $\mathbb{E}^{\nu}[\log \rho_0] < 0, 0 < \kappa < 1$: it is easily checked that, as written above, the logarithmic term is $(\log T_n)^{1/\kappa}$ and not $\log T_n$.

In the non parametric case, there seems to be a trade-off between exploring more sites (increasing $\kappa$) to get information about more realizations of $\nu$ and spend more time on these sites (decreasing $\kappa$) to have a better knowledge of these realizations. And, in terms of $T_n$, the fastest convergence of the estimator is obtained for $\kappa = 1$. This looks surprising compared to the results of [16] where the rate $1/\sqrt{T_n}$ can be recovered in the ballistic regime ($\kappa > 1$).

The results of Theorem 1.1 and Corollary 1.2 are illustrated with some experiments on synthetic data using Beta distribution $B(a, b)$. In this example, $F$ is clearly infinitely differentiable and simple computations show that $\kappa = a - b$. Figures 1-4 show the estimates of the c.d.f. for various values of $\kappa$ and $n = 500$. They also provide the value of the selected model $\hat{M}_n$ and the value of the loss $N_{\infty} = \|F - \hat{F}_n^{\hat{M}_n}\|_{\infty}$. The red curve is the empirical c.d.f. knowing the environment $(\omega_x)_{0 \le x \le n-1}$.
<figure><img src="image_4.png" /><figcaption>FIGURE 1. Recurrent case $B(3, 3)$: $n = 500$, $T_n \approx 8.7 \times 10^9$, $\hat{M}_n = 99$, $N_\infty \approx 0.029$.</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>FIGURE 3. $\kappa = 1$, $B(4, 3)$: $n = 500$, $T_n = 8553$, $\hat{M}_n = 28$, $N_\infty \approx 0.063$.</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>FIGURE 2. $\kappa = 0.5$, $B(3.5, 3)$: $n = 500$, $T_n = 198284$, $\hat{M}_n = 49$, $N_\infty \approx 0.047$.</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>FIGURE 4. $\kappa = 3$, $B(6, 3)$: $n = 500$, $T_n = 1732$, $\hat{M}_n = 13$, $N_\infty \approx 0.156$.</figcaption></figure>

## 1.3. Estimation of the moments of the environment

We suppose in this part that $E^\nu[\log \rho_0] \le 0$. This section presents estimators of the moments of the environment and the key martingale arguments underlying the concentration property. These will be the basic tools to build and control the estimator of the c.d.f.. Following [10], let

$$L(t_0, x) = \sum_{0 \le t \le t_0 - 1} 1_{\{S_t=x, S_{t+1}=x-1\}}$$

denote the number of steps to the left from site $x$ until time $t_0$. The process

$$(Z_x^n)_{0 \le x \le n} = (L(T_n, n-x))_{0 \le x \le n}$$

is an exhaustive statistic that is the building block of our estimation strategy. According to [22], $(Z_x^n)_{0 \le x \le n}$ has the same distribution as a branching process in random environment with immigration $(Z_x)_{0 \le x \le n}$. Under the annealed law $P^\nu$, $(Z_x)_{x \in \mathbb{N}}$ is an homogeneous Markov chain starting at 0 with transition kernel

$$K^\nu(i, j) = \binom{i+j}{i} \int_0^1 a^{i+1} (1-a)^j \nu(\mathrm{d}a) \quad (3)$$
<figure><img src="image_4.png" /><figcaption>FIGURE 1. Recurrent case $B(3, 3)$: $n = 500$, $T_n \approx 8.7 \times 10^9$, $\hat{M}_n = 99$, $N_\infty \approx 0.029$.</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>FIGURE 3. $\kappa = 1$, $B(4, 3)$: $n = 500$, $T_n = 8553$, $\hat{M}_n = 28$, $N_\infty \approx 0.063$.</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>FIGURE 2. $\kappa = 0.5$, $B(3.5, 3)$: $n = 500$, $T_n = 198284$, $\hat{M}_n = 49$, $N_\infty \approx 0.047$.</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>FIGURE 4. $\kappa = 3$, $B(6, 3)$: $n = 500$, $T_n = 1732$, $\hat{M}_n = 13$, $N_\infty \approx 0.156$.</figcaption></figure>

## 1.3. Estimation of the moments of the environment

We suppose in this part that $E^\nu[\log \rho_0] \le 0$. This section presents estimators of the moments of the environment and the key martingale arguments underlying the concentration property. These will be the basic tools to build and control the estimator of the c.d.f.. Following [10], let

$$L(t_0, x) = \sum_{0 \le t \le t_0-1} 1_{\{S_t=x, S_{t+1}=x-1\}}$$

denote the number of steps to the left from site $x$ until time $t_0$. The process

$$(Z_x^n)_{0 \le x \le n} = (L(T_n, n-x))_{0 \le x \le n}$$

is an exhaustive statistic that is the building block of our estimation strategy. According to [22], $(Z_x^n)_{0 \le x \le n}$ has the same distribution as a branching process in random environment with immigration $(Z_x)_{0 \le x \le n}$. Under the annealed law $P^\nu$, $(Z_x)_{x \in \mathbb{N}}$ is an homogeneous Markov chain starting at 0 with transition kernel

$$K^\nu(i, j) = \binom{i+j}{i} \int_0^1 a^{i+1} (1-a)^j \nu(\mathrm{d}a) \quad (3)$$
(see [10, Proposition 4.3]). Moreover, if $\mathbb{E}^{\nu}[\log \rho_0] < 0$, $(Z_x)_{x \in \mathbb{N}}$ is positive recurrent and aperiodic and admits a unique invariant probability measure $\pi$ (see [10, Theorem 4.5]).

Equation (3) shows that it is natural to estimate the moments

$$m^{\alpha, \beta} = \mathbb{E}^{\nu} [\omega_0^{\alpha} (1 - \omega_0)^{\beta}] = \int_{0}^{1} a^{\alpha} (1 - a)^{\beta} \nu(\mathrm{d} a).$$

Our estimation strategy is based on the following simple equality. For any $\alpha, \beta \in \mathbb{N}$,

$$\forall i \ge \alpha, \quad \sum_{j \ge \beta} \binom{i - \alpha + j - \beta}{i - \alpha} a^{i+1} (1 - a)^j = a^{\alpha} (1 - a)^{\beta}.$$

Integrating this with respect to $a$ and using (3), this gives, for any $\alpha, \beta \in \mathbb{N}$,

$$\forall i \ge 0, \forall x \in [1, n], m^{\alpha, \beta} \mathbb{1}_{\{i \ge \alpha\}} = \mathbb{E}^{\nu} [\Phi_{\alpha, \beta}(Z_{x-1}^n, Z_x^n) | Z_{x-1}^n = i] \quad (4)$$

where, for any integers $i, j \ge 0$,

$$\Phi_{\alpha, \beta}(i, j) = \mathbb{1}_{\{i \ge \alpha, j \ge \beta\}} \frac{\binom{i+j-(\alpha+\beta)}{i-\alpha}{i+j \choose i}}{\prod_{\ell=0}^{\alpha-1} (i-\ell) \prod_{\ell=0}^{\beta-1} (j-\ell)} = \mathbb{1}_{\{i \ge \alpha, j \ge \beta\}} \frac{\prod_{\ell=0}^{\alpha-1} (i-\ell) \prod_{\ell=0}^{\beta-1} (j-\ell)}{\prod_{\ell=0}^{\alpha+\beta-1} (i+j-\ell)}.$$

It is therefore natural to estimate $m^{\alpha, \beta}$ by the following estimator:

$$\hat{m}_{n}^{\alpha, \beta} = \frac{1}{N_{n}^{\alpha}} \sum_{x=1}^{n} \Phi_{\alpha, \beta}(Z_{x-1}^{n}, Z_{x}^{n}) \quad \text{where} \quad N_{n}^{\alpha} = \sum_{x=0}^{n-1} \mathbb{1}_{\{Z_{x}^{n} \ge \alpha\}}, \quad (5)$$

with the convention that $0/0 = 0$. Indeed, Equation (4) implies that, for any $\alpha, \beta \in \mathbb{N}$, the triangular arrays $(X_{n,x}^{\alpha, \beta})_{0 \le x \le n < \infty}$ defined, for all $n \ge 0$, by $X_{n,0}^{\alpha, \beta} = 0$ and for $1 \le x \le n$, $X_{n,x}^{\alpha, \beta} = \Phi_{\alpha, \beta}(Z_{x-1}^n, Z_x^n) - m^{\alpha, \beta} \mathbb{1}_{\{Z_{x-1}^n \ge \alpha\}}$ are martingale difference arrays. Then Mc Diarmid's inequality [27] gives a control of the risk of our moment estimators:

$$\forall n \ge 1, \forall z > 0, \quad \mathbb{P}^{\nu} \left( \left| \hat{m}_{n}^{\alpha, \beta} - m^{\alpha, \beta} \right| \ge \frac{n}{N_{n}^{\alpha}} \left( \frac{\alpha + \beta}{\alpha} \right)^{-1} \frac{z}{\sqrt{2n}} \right) \le 2e^{-z^2}.$$

Note that, if $\mathbb{E}^{\nu}[\log \rho_0] < 0$, $\frac{N_n^{\alpha}}{n} = \frac{1}{n} \sum_{x=0}^{n-1} \mathbb{1}_{\{Z_x^n \ge \alpha\}}$ converges to some positive constant according to ergodic theorem and if $\mathbb{E}^{\nu}[\log \rho_0] = 0$, $N_n^{\alpha}/n \ge 1/2$ with large probability. Therefore, for any $\alpha, \beta \ge 0$, $\hat{m}_{n}^{\alpha, \beta}$ converges at parametric rate $\sqrt{n}$.

## 1.4. Estimation of the cumulative distribution function

We now want to use the estimation of the moments $m^{\alpha, \beta}$ to approximate the cumulative distribution function $F$ of $\nu$. Define for any $u \in [0, 1]$ and any $M \in \mathbb{N}^*$,

$$F^M(u) = \sum_{k=0}^{\lfloor (M+1)u \rfloor - 1} \binom{M}{k} m^{k, M-k},$$

where $\sum_{k=0}^{-1} = 0$ and $x \to \lfloor x \rfloor$ is the floor function. A classical approximation result shows that, if $F$ is Hölder continuous, $F^M$ converges uniformly to $F$ when $M$ tends to infinity. Thus, we only have to estimate $F^M$ using
(see [10, Proposition 4.3]). Moreover, if $\mathbb{E}^{\nu}[\log \rho_0] < 0$, $(Z_x)_{x \in \mathbb{N}}$ is positive recurrent and aperiodic and admits a unique invariant probability measure $\pi$ (see [10, Theorem 4.5]).

Equation (3) shows that it is natural to estimate the moments

$$m^{\alpha, \beta} = \mathbb{E}^{\nu} [\omega_0^{\alpha} (1 - \omega_0)^{\beta}] = \int_{0}^{1} a^{\alpha} (1 - a)^{\beta} \nu(\mathrm{d} a).$$

Our estimation strategy is based on the following simple equality. For any $\alpha, \beta \in \mathbb{N}$,

$$\forall i \ge \alpha, \quad \sum_{j \ge \beta} \binom{i - \alpha + j - \beta}{i - \alpha} a^{i+1} (1 - a)^j = a^{\alpha} (1 - a)^{\beta}.$$

Integrating this with respect to $a$ and using (3), this gives, for any $\alpha, \beta \in \mathbb{N}$,

$$\forall i \ge 0, \forall x \in [1, n], m^{\alpha, \beta} \mathbb{1}_{\{i \ge \alpha\}} = \mathbb{E}^{\nu} [\Phi_{\alpha, \beta}(Z_{x-1}^n, Z_x^n) | Z_{x-1}^n = i] \quad (4)$$

where, for any integers $i, j \ge 0$,

$$\Phi_{\alpha, \beta}(i, j) = \mathbb{1}_{\{i \ge \alpha, j \ge \beta\}} \frac{\binom{i+j-(\alpha+\beta)}{i-\alpha}{i+j \choose i}}{\prod_{\ell=0}^{\alpha-1} (i-\ell) \prod_{\ell=0}^{\beta-1} (j-\ell)} = \mathbb{1}_{\{i \ge \alpha, j \ge \beta\}} \frac{\prod_{\ell=0}^{\alpha-1} (i-\ell) \prod_{\ell=0}^{\beta-1} (j-\ell)}{\prod_{\ell=0}^{\alpha+\beta-1} (i+j-\ell)}.$$

It is therefore natural to estimate $m^{\alpha, \beta}$ by the following estimator:

$$\hat{m}_{n}^{\alpha, \beta} = \frac{1}{N_{n}^{\alpha}} \sum_{x=1}^{n} \Phi_{\alpha, \beta}(Z_{x-1}^{n}, Z_{x}^{n}) \quad \text{where} \quad N_{n}^{\alpha} = \sum_{x=0}^{n-1} \mathbb{1}_{\{Z_{x}^{n} \ge \alpha\}}, \quad (5)$$

with the convention that $0/0 = 0$. Indeed, Equation (4) implies that, for any $\alpha, \beta \in \mathbb{N}$, the triangular arrays $(X_{n,x}^{\alpha, \beta})_{0 \le x \le n < \infty}$ defined, for all $n \ge 0$, by $X_{n,0}^{\alpha, \beta} = 0$ and for $1 \le x \le n$, $X_{n,x}^{\alpha, \beta} = \Phi_{\alpha, \beta}(Z_{x-1}^n, Z_x^n) - m^{\alpha, \beta} \mathbb{1}_{\{Z_{x-1}^n \ge \alpha\}}$ are martingale difference arrays. Then Mc Diarmid's inequality [27] gives a control of the risk of our moment estimators:

$$\forall n \ge 1, \forall z > 0, \quad \mathbb{P}^{\nu} \left( \left| \hat{m}_{n}^{\alpha, \beta} - m^{\alpha, \beta} \right| \ge \frac{n}{N_{n}^{\alpha}} \left( \frac{\alpha + \beta}{\alpha} \right)^{-1} \frac{z}{\sqrt{2n}} \right) \le 2e^{-z^2}.$$

Note that, if $\mathbb{E}^{\nu}[\log \rho_0] < 0$, $\frac{N_n^{\alpha}}{n} = \frac{1}{n} \sum_{x=0}^{n-1} \mathbb{1}_{\{Z_x^n \ge \alpha\}}$ converges to some positive constant according to ergodic theorem and if $\mathbb{E}^{\nu}[\log \rho_0] = 0$, $N_n^{\alpha}/n \ge 1/2$ with large probability. Therefore, for any $\alpha, \beta \ge 0$, $\hat{m}_{n}^{\alpha, \beta}$ converges at parametric rate $\sqrt{n}$.

## 1.4. Estimation of the cumulative distribution function

We now want to use the estimation of the moments $m^{\alpha, \beta}$ to approximate the cumulative distribution function $F$ of $\nu$. Define for any $u \in [0, 1]$ and any $M \in \mathbb{N}^*$,

$$F^M(u) = \sum_{k=0}^{\lfloor (M+1)u \rfloor - 1} \binom{M}{k} m^{k, M-k},$$

where $\sum_{k=0}^{-1} = 0$ and $x \to \lfloor x \rfloor$ is the floor function. A classical approximation result shows that, if $F$ is Hölder continuous, $F^M$ converges uniformly to $F$ when $M$ tends to infinity. Thus, we only have to estimate $F^M$ using
the same kind of estimators as in the previous section:

$$ \hat{F}_n^M(u) = \frac{1}{N_n^M} \sum_{x=1}^n \psi_M^{\lfloor(M+1)u\rfloor}(Z_{x-1}^n, Z_x^n), $$

where $N_n^M = \sum_{x=0}^{n-1} 1\{Z_x^n \ge M\}$ as in (5) and

$$ \psi_M^l(i, j) = \frac{1_{\{i \ge M\}}}{\binom{i+j}{M}} \sum_{k=0}^{l-1} \binom{i}{k} \binom{j}{M-k}, $$

using the conventions $0/0 = 0$ and $\binom{n}{k} = 0$ for $n < k$. Remark that

$$ \psi_M^l(i, j) = \sum_{k=0}^{l-1} \binom{M}{k} \Phi_{k, M-k}(i, j), $$

for any $i \ge M$, where $\Phi_{k,M-k}$ is defined in (4). This estimator is then essentially the estimator of $F^M$ obtained from the moment estimators of Section 1.3, but using only the sites $x$ satisfying $Z_{x-1}^n \ge M$. The Vandermonde's identity $\sum_{k=0}^M \binom{i}{k} \binom{j}{M-k} = \binom{i+j}{M}$ for any $i, j \ge 0$, shows that any $\hat{F}_n^M$ is a (random) c.d.f.. Assuming that, for some $\gamma \in (0, 2]$, the c.d.f. $F$ is $\gamma$-Hölder with Hölder norm $\|F\|_\gamma$, we get an upper bound on the risk:

$$ \forall M, n \ge 1, \forall z > 0, \quad \mathbb{P}^\nu \left( \|\hat{F}_n^M - F\|_\infty \ge \frac{n}{N_n^M} \sqrt{\frac{z + \log M}{2n}} + \frac{2\|F\|_\gamma}{(M+1)^{\gamma/2}} \right) \le 2e^{-z}. \quad (6) $$

The first term in the bound is derived from the martingale argument presented in the previous section. The second term is the upper bound on the bias of this estimator derived from the error approximation between $F^M$ and $F$. It is interesting to notice that, although $F^M$ is a histogram, one can take advantage of the regularity of $F$ up to $\gamma = 2$.

Our final estimator $\hat{F}_n$ given by Theorem 1.1 is obtained via Goldenshluger-Lepski's method, see [17], using the collection $(\hat{F}_n^M)_{M \ge 1}$. This method selects, for any fixed $z > 0$ but without the knowledge of $\gamma$, a regularizing parameter $\hat{M}_n^z \ge 0$ such that the estimator $\hat{F}_n^{\hat{M}_n^z}$ optimizes, up to a multiplicative constant, the bound given by (6). To derive the rate of convergence of this estimator and conclude the proof of Theorem 1.1, we have to study the asymptotic behaviour of $\frac{\hat{M}_n^z}{n}$ when $M$ and $n$ go to infinity. This study is performed separately for the recurrent case and the transient case.

Indeed, in the transient case, the Markov chain $(Z_x)_{x \in \mathbb{N}}$ admits an invariant probability $\pi$ while it does not in the recurrent case. Therefore, in the transient regime, we can show that $N_n^M/n$ concentrates around $\pi([M, \infty))$ using the concentration inequality for Markov chains of [11] and that $\pi([M, +\infty)) \sim C_\nu M^{-\kappa}$ using the estimate of the tails of $W$ from [22]. Theorem 1.1 then follows from a classical optimization of the parameter $M$.

In the recurrent case, convergence results for the distribution of $T_n$, see [18], and the strong Gaussian approximation theorem of [26], imply that $N_n^M/n$ is asymptotically almost surely 1 if $M$ grows as a power of $n$ which is enough to obtain the result of the theorem.

## 2. GRAPH DIRICHLET DISTRIBUTION

This part is based on a joint work [25] of Xiaolin Zeng with Bartosz Kołodziejek and Jacek Wesolowski.
the same kind of estimators as in the previous section:

$$ \hat{F}_n^M(u) = \frac{1}{N_n^M} \sum_{x=1}^{n} \psi_M^{\lfloor(M+1)u\rfloor}(Z_{x-1}^n, Z_x^n), $$

where $N_n^M = \sum_{x=0}^{n-1} 1\{Z_x^n \ge M\}$ as in (5) and

$$ \psi_M^l(i, j) = \frac{1_{\{i \ge M\}}}{\binom{i+j}{M}} \sum_{k=0}^{l-1} \binom{i}{k} \binom{j}{M-k}, $$

using the conventions $0/0 = 0$ and $\binom{n}{k} = 0$ for $n < k$. Remark that

$$ \psi_M^l(i, j) = \sum_{k=0}^{l-1} \binom{M}{k} \Phi_{k, M-k}(i, j), $$

for any $i \ge M$, where $\Phi_{k,M-k}$ is defined in (4). This estimator is then essentially the estimator of $F^M$ obtained from the moment estimators of Section 1.3, but using only the sites $x$ satisfying $Z_{x-1}^n \ge M$. The Vandermonde's identity $\sum_{k=0}^M \binom{i}{k} \binom{j}{M-k} = \binom{i+j}{M}$ for any $i, j \ge 0$, shows that any $\hat{F}_n^M$ is a (random) c.d.f.. Assuming that, for some $\gamma \in (0, 2]$, the c.d.f. $F$ is $\gamma$-Hölder with Hölder norm $\|F\|_\gamma$, we get an upper bound on the risk:

$$ \forall M, n \ge 1, \forall z > 0, \quad \mathbb{P}^\nu \left( \|\hat{F}_n^M - F\|_\infty \ge \frac{n}{N_n^M} \sqrt{\frac{z + \log M}{2n}} + \frac{2\|F\|_\gamma}{(M+1)^{\gamma/2}} \right) \le 2e^{-z}. \quad (6) $$

The first term in the bound is derived from the martingale argument presented in the previous section. The second term is the upper bound on the bias of this estimator derived from the error approximation between $F^M$ and $F$. It is interesting to notice that, although $F^M$ is a histogram, one can take advantage of the regularity of $F$ up to $\gamma = 2$.

Our final estimator $\hat{F}_n$ given by Theorem 1.1 is obtained via Goldenshluger-Lepski's method, see [17], using the collection $(\hat{F}_n^M)_{M \ge 1}$. This method selects, for any fixed $z > 0$ but without the knowledge of $\gamma$, a regularizing parameter $\hat{M}_n^z \ge 0$ such that the estimator $\hat{F}_n^{\hat{M}_n^z}$ optimizes, up to a multiplicative constant, the bound given by (6). To derive the rate of convergence of this estimator and conclude the proof of Theorem 1.1, we have to study the asymptotic behaviour of $\frac{\hat{M}_n^z}{n}$ when $M$ and $n$ go to infinity. This study is performed separately for the recurrent case and the transient case.

Indeed, in the transient case, the Markov chain $(Z_x)_{x \in \mathbb{N}}$ admits an invariant probability $\pi$ while it does not in the recurrent case. Therefore, in the transient regime, we can show that $N_n^M/n$ concentrates around $\pi([M, \infty))$ using the concentration inequality for Markov chains of [11] and that $\pi([M, +\infty)) \sim C_\nu M^{-\kappa}$ using the estimate of the tails of $W$ from [22]. Theorem 1.1 then follows from a classical optimization of the parameter $M$.

In the recurrent case, convergence results for the distribution of $T_n$, see [18], and the strong Gaussian approximation theorem of [26], imply that $N_n^M/n$ is asymptotically almost surely 1 if $M$ grows as a power of $n$ which is enough to obtain the result of the theorem.

## 2. GRAPH DIRICHLET DISTRIBUTION

This part is based on a joint work [25] of Xiaolin Zeng with Bartosz Kołodziejek and Jacek Wesolowski.
## 2.1. Introduction

Dirichlet distribution is well known in probability and statistics. It has applications in e.g. Pólya urn (or the more general Dirichlet urn, see Johnson et al. [21]), directed edge reinforced random walk [29], and in Bayesian statistics as a common prior distribution (see [21]).

To fix the notations, given $d \ge 2$, we say that $X = (X_1, \dots, X_{d-1})$ supported on $M = \{x \in (0,1)^{d-1}, x_1+\dots+x_{d-1} < 1\}$ follows the Dirichlet distribution with parameter $\alpha = (\alpha_1, \dots, \alpha_d) \in \mathbb{R}_{>0}^d$, denoted by $X \sim \text{Dir}(\alpha)$, if its law is $f(x) \prod_{i=1}^{d-1} dx_i$ where

$$f(x) = \mathbb{1}_M(x) \frac{\Gamma(\sum_{i=1}^d \alpha_i)}{\prod_{i=1}^d \Gamma(\alpha_i)} \prod_{i=1}^d x_i^{\alpha_i - 1}. \qquad (7)$$

It is often said, with a slight abuse of notation, that $X = (X_1, \dots, X_{d-1}, X_d)$, where $X_d = 1 - \sum_{i=1}^{d-1} X_i$, also follows a Dir($\alpha$) distribution (notice that here, the number of $X_i$ is the same as the number of $\alpha_i$, contrarily to the previous case). We use this abuse of notation in the following.

Classically, it is related to the Dirichlet urn process: assume that $\alpha_i \in \mathbb{N}^*$ for all $i = 1, \dots, d$, and let there be initially $\alpha_i$ balls of color $i$ in the urn. The Dirichlet urn process is a stochastic process $(Y_n)_{n \in \mathbb{N}}$ taking values in $\{1, \dots, d\}$, constructed by the following rules:

(1) At time $n \ge 0$, draw a ball uniformly at random from the urn, its color is denoted by $Y_n$;

(2) Put back immediately this ball into the urn, and add in the urn an additional ball of the same color before the next drawing.

The process $Y = (Y_n)_{n \ge 0}$ is related to $X$ by: The law of $Y$ is the same as, first sample a probability measure $x = (x_1, \dots, x_d)$ from $X \sim \text{Dir}(\alpha)$, then run an i.i.d. process that takes value $i$ with probability $x_i$. This can be seen by direct computation of finite dimensional marginal distributions of the two processes (see Johnson et al. [21]; see also Zeng [37] Section 1.3).

Another classic story in which Dirichlet distribution plays a role is the shooting board game in Bayesian statistic. Consider a random experiment producing outcome $0, 1, \dots, k$ with probability respectively equal to $q_0, q_1, \dots, q_k$ and repeat this experiment successively and independently infinitely many times. If we count the number of outcomes $1, \dots, k$ until 0 is occurred $r$ times, let $N_1, \dots, N_k$ be the number of times each result $1, \dots, k$ occurs. The random vector $N$ follows a negative multinomial distribution with parameter $(r; q_1, \dots, q_k)$, i.e. the probability to observe $n = (n_1, \dots, n_k)$ is

$$\mathbb{P}(N_i = n_i, 1 \le i \le k) = \binom{r + |n| - 1}{n_1, \dots, n_k} \left(1 - \sum_{i=1}^k q_i\right)^r \prod_{i=1}^k q_i^{n_i}, \qquad (8)$$

where $|n| = n_1 + n_2 + \dots + n_k$.

Dirichlet distribution is the conjugate prior for the negative multinomial distribution (as likelihood): if $q$ is drawn from a Dirichlet distribution of parameter $(\beta, \alpha_1, \dots, \alpha_k)$, then the posterior, the new estimation after the observation $n$ follows again the Dirichlet distribution with parameter $(\beta + r, \alpha_1 + n_1, \dots, \alpha_k + n_k)$.

We are going to generalize the Dirichlet distribution so as it will depend on a finite decomposable graph $G = (V, E)$ and parameters $\alpha = (\alpha_i)_{i \in V} \in \mathbb{R}_{>0}^V$ and $\beta > 0$, and list some of its properties and one of its related processes. We call this generalization graph $G$-Dirichlet distribution. In particular, the classical Dirichlet distribution becomes a $G$-Dirichlet distribution with $G$ being the complete graph. We will use a particular graph as an example of application, called the nasty graph in this manuscript, depicted in Figure 5.

## 2.2. Decomposable graph and definition of $G$-Dirichlet distribution

For details of proofs and references of the claims in this section, please see [25]. An undirected simple graph $G = (V, E)$ is said to be decomposable if it admits a perfect eliminating sequence, which provides a way to decompose the graph (like in a finite tree graph, we can decompose it by removing its leaves). More precisely, a graph $G = (V, E)$ with $V = \{v_1, \dots, v_d\}$ is decomposable if there exists a permutation $\sigma$ (called a perfect
## 2.1. Introduction

Dirichlet distribution is well known in probability and statistics. It has applications in e.g. Pólya urn (or the more general Dirichlet urn, see Johnson et al. [21]), directed edge reinforced random walk [29], and in Bayesian statistics as a common prior distribution (see [21]).

To fix the notations, given $d \ge 2$, we say that $X = (X_1, \dots, X_{d-1})$ supported on $M = \{x \in (0, 1)^{d-1}, x_1+\dots+x_{d-1} < 1\}$ follows the Dirichlet distribution with parameter $\alpha = (\alpha_1, \dots, \alpha_d) \in \mathbb{R}_{>0}^d$, denoted by $X \sim \text{Dir}(\alpha)$, if its law is $f(x) \prod_{i=1}^{d-1} dx_i$ where

$$f(x) = \mathbb{I}_M(x) \frac{\Gamma(\sum_{i=1}^d \alpha_i)}{\prod_{i=1}^d \Gamma(\alpha_i)} \prod_{i=1}^d x_i^{\alpha_i - 1}. \qquad (7)$$

It is often said, with a slight abuse of notation, that $X = (X_1, \dots, X_{d-1}, X_d)$, where $X_d = 1 - \sum_{i=1}^{d-1} X_i$, also follows a Dir($\alpha$) distribution (notice that here, the number of $X_i$ is the same as the number of $\alpha_i$, contrarily to the previous case). We use this abuse of notation in the following.

Classically, it is related to the Dirichlet urn process: assume that $\alpha_i \in \mathbb{N}^*$ for all $i = 1, \dots, d$, and let there be initially $\alpha_i$ balls of color $i$ in the urn. The Dirichlet urn process is a stochastic process $(Y_n)_{n \in \mathbb{N}}$ taking values in $\{1, \dots, d\}$, constructed by the following rules:

(1) At time $n \ge 0$, draw a ball uniformly at random from the urn, its color is denoted by $Y_n$;

(2) Put back immediately this ball into the urn, and add in the urn an additional ball of the same color before the next drawing.

The process $Y = (Y_n)_{n \ge 0}$ is related to $X$ by: The law of $Y$ is the same as, first sample a probability measure $x = (x_1, \dots, x_d)$ from $X \sim \text{Dir}(\alpha)$, then run an i.i.d. process that takes value $i$ with probability $x_i$. This can be seen by direct computation of finite dimensional marginal distributions of the two processes (see Johnson et al. [21]; see also Zeng [37] Section 1.3).

Another classic story in which Dirichlet distribution plays a role is the shooting board game in Bayesian statistic. Consider a random experiment producing outcome $0, 1, \dots, k$ with probability respectively equal to $q_0, q_1, \dots, q_k$ and repeat this experiment successively and independently infinitely many times. If we count the number of outcomes $1, \dots, k$ until 0 is occurred $r$ times, let $N_1, \dots, N_k$ be the number of times each result $1, \dots, k$ occurs. The random vector $N$ follows a negative multinomial distribution with parameter $(r; q_1, \dots, q_k)$, i.e. the probability to observe $n = (n_1, \dots, n_k)$ is

$$\mathbb{P}(N_i = n_i, 1 \le i \le k) = \binom{r + |n| - 1}{n_1, \dots, n_k} \left(1 - \sum_{i=1}^k q_i\right)^r \prod_{i=1}^k q_i^{n_i}, \qquad (8)$$

where $|n| = n_1 + n_2 + \dots + n_k$.

Dirichlet distribution is the conjugate prior for the negative multinomial distribution (as likelihood): if $q$ is drawn from a Dirichlet distribution of parameter $(\beta, \alpha_1, \dots, \alpha_k)$, then the posterior, the new estimation after the observation $n$ follows again the Dirichlet distribution with parameter $(\beta + r, \alpha_1 + n_1, \dots, \alpha_k + n_k)$.

We are going to generalize the Dirichlet distribution so as it will depend on a finite decomposable graph $G = (V, E)$ and parameters $\alpha = (\alpha_i)_{i \in V} \in \mathbb{R}_{>0}^V$ and $\beta > 0$, and list some of its properties and one of its related processes. We call this generalization graph $G$-Dirichlet distribution. In particular, the classical Dirichlet distribution becomes a $G$-Dirichlet distribution with $G$ being the complete graph. We will use a particular graph as an example of application, called the nasty graph in this manuscript, depicted in Figure 5.

## 2.2. Decomposable graph and definition of $G$-Dirichlet distribution

For details of proofs and references of the claims in this section, please see [25]. An undirected simple graph $G = (V, E)$ is said to be decomposable if it admits a perfect eliminating sequence, which provides a way to decompose the graph (like in a finite tree graph, we can decompose it by removing its leaves). More precisely, a graph $G = (V, E)$ with $V = \{v_1, \dots, v_d\}$ is decomposable if there exists a permutation $\sigma$ (called a perfect
eliminating sequence) of order $d$ such that for all $k = 1, \dots, d-1$, the vertex $v_{\sigma(k)}$ is simplicial in the inducted subgraph of $\mathcal{G}$ with vertices set $\{v_{\sigma(k)}, \dots, v_{\sigma(d)}\}$. We recall that a vertex $v$ is simplicial in $\mathcal{G}$ if its neighbors in $\mathcal{G}$ form a clique (i.e. a subgraph which is a complete graph) in $\mathcal{G}$.

**Remark 2.1 (Chordal graph).** There is a simpler definition for decomposable graphs: a graph is decomposable if it is chordal, i.e. a graph in which all cycle of four or more vertices have a chord. There are other characterizations for decomposable graphs, see [23] for the precise definition of cycles and chords, and a more complete introduction.

In Figure 5, we depict one perfect eliminating sequence of the nasty graph in which we identify $v_i$ to $i$ for $i = 1, \dots, 5$, $\sigma = \text{id}$, and we illustrate how successive simplicial vertices are removed. Note that perfect elimination sequence is not unique for a given decomposable graph.

<figure><img src="image_8.png" /><figcaption>FIGURE 5. Decomposition of the nasty graph with perfect elimination sequence $\sigma = \text{id}$.</figcaption></figure>

Given a finite graph $\mathcal{G} = (V, E)$, let $\mathcal{C}_\mathcal{G}$ be the collection of cliques of $\mathcal{G}$. If $C \in \mathcal{C}_\mathcal{G}$, we say that $C$ is a clique of order $|C|$ (the cardinality of $C$); in particular, there is only one clique of order 0, which is the empty set. A clique $C \in \mathcal{C}_\mathcal{G}$ is said to be maximal if it is not strictly contained in a larger clique. We denote by $\mathcal{C}_\mathcal{G}^+$ the collection of maximal cliques of $\mathcal{G}$.

Another equivalent definition of a decomposable graph is: $\mathcal{G}$ is decomposable if $\mathcal{C}_\mathcal{G}^+$ allows a perfect ordering, i.e. we can order the elements of $\mathcal{C}_\mathcal{G}^+$ as $C_1, \dots, C_K$ (so $K$ is the number of maximal cliques) in such a way that for any $j \in \{2, \dots, K\}$, there exists $i \in \{1, \dots, j-1\}$ such that

$$ \emptyset \neq S_j := C_j \cap \bigcup_{\ell=1}^{j-1} C_\ell \subset C_i. $$

The sets $S_2, \dots, S_k$ defined above are called minimal separators of $\mathcal{G}$, they need not to be distinct. Moreover, the family $S_\mathcal{G}^- := \{S \subset V : \exists k \in \{2, \dots, K\}, S = S_k\}$ is called the set of minimal separators. For $S \in S_\mathcal{G}^-$, the number of indices $k$ such that $S = S_k$ is called the multiplicity of the minimal separator $S$ and is denoted by $\nu_S$. Both $S_\mathcal{G}^-$ and $\nu_S$ do not depend on the perfect ordering.

For example, on the nasty graph, we have $C_1 = \{1, 2, 3\}$, $C_2 = \{2, 3, 4\}$, $C_3 = \{3, 4, 5\}$ and $S_2 = \{2, 3\}$, $S_3 = \{3, 4\}$ and $K = 3$.

Given a finite decomposable graph $\mathcal{G} = (V, E)$, let $\mathcal{G}^*$ be its complementary graph, i.e. $\mathcal{G}^* = (V, E^c)$, where the complementary of $E$ is taken as the edges that do not exist in $E$ (an edge of the form $\{i, i\}$ is not allowed). Recall that $\mathcal{C}_\mathcal{G}^*$ is the collection of cliques in $\mathcal{G}^*$. From now on we identify $V = \{v_1, \dots, v_d\} = \{1, \dots, d\}$, and use $x_1, \dots, x_d$ to denote indeterminate variables associated to the vertices. Let $|C|$ denote the number of vertices in $C$, and $\pi_C(x) = \prod_{i \in C} x_i$, with the convention $\pi_\emptyset(x) = 1$, for $x = (x_i)_{i \in V}$. We define the graph polynomial $\Delta_\mathcal{G}$ of formal variables $(x_i, i \in V)$ by

$$ \Delta_{\mathcal{G}}(x) = \sum_{C \in \mathcal{C}_{\mathcal{G}}^*} (-1)^{|C|} \pi_C(x). $$
eliminating sequence) of order $d$ such that for all $k = 1, \dots, d-1$, the vertex $v_{\sigma(k)}$ is simplicial in the inducted subgraph of $\mathcal{G}$ with vertices set $\{v_{\sigma(k)}, \dots, v_{\sigma(d)}\}$. We recall that a vertex $v$ is simplicial in $\mathcal{G}$ if its neighbors in $\mathcal{G}$ form a clique (i.e. a subgraph which is a complete graph) in $\mathcal{G}$.

**Remark 2.1 (Chordal graph).** There is a simpler definition for decomposable graphs: a graph is decomposable if it is chordal, i.e. a graph in which all cycle of four or more vertices have a chord. There are other characterizations for decomposable graphs, see [23] for the precise definition of cycles and chords, and a more complete introduction.

In Figure 5, we depict one perfect eliminating sequence of the nasty graph in which we identify $v_i$ to $i$ for $i = 1, \dots, 5$, $\sigma = \text{id}$, and we illustrate how successive simplicial vertices are removed. Note that perfect elimination sequence is not unique for a given decomposable graph.

<figure><img src="image_8.png" /><figcaption>FIGURE 5. Decomposition of the nasty graph with perfect elimination sequence $\sigma = \text{id}$.</figcaption></figure>

Given a finite graph $\mathcal{G} = (V, E)$, let $\mathcal{C}_\mathcal{G}$ be the collection of cliques of $\mathcal{G}$. If $C \in \mathcal{C}_\mathcal{G}$, we say that $C$ is a clique of order $|C|$ (the cardinality of $C$); in particular, there is only one clique of order 0, which is the empty set. A clique $C \in \mathcal{C}_\mathcal{G}$ is said to be maximal if it is not strictly contained in a larger clique. We denote by $\mathcal{C}_\mathcal{G}^+$ the collection of maximal cliques of $\mathcal{G}$.

Another equivalent definition of a decomposable graph is: $\mathcal{G}$ is decomposable if $\mathcal{C}_\mathcal{G}^+$ allows a perfect ordering, i.e. we can order the elements of $\mathcal{C}_\mathcal{G}^+$ as $C_1, \dots, C_K$ (so $K$ is the number of maximal cliques) in such a way that for any $j \in \{2, \dots, K\}$, there exists $i \in \{1, \dots, j-1\}$ such that

$$ \emptyset \neq S_j := C_j \cap \bigcup_{\ell=1}^{j-1} C_\ell \subset C_i. $$

The sets $S_2, \dots, S_k$ defined above are called minimal separators of $\mathcal{G}$, they need not to be distinct. Moreover, the family $S_\mathcal{G}^- := \{S \subset V : \exists k \in \{2, \dots, K\}, S = S_k\}$ is called the set of minimal separators. For $S \in S_\mathcal{G}^-$, the number of indices $k$ such that $S = S_k$ is called the multiplicity of the minimal separator $S$ and is denoted by $\nu_S$. Both $S_\mathcal{G}^-$ and $\nu_S$ do not depend on the perfect ordering.

For example, on the nasty graph, we have $C_1 = \{1, 2, 3\}$, $C_2 = \{2, 3, 4\}$, $C_3 = \{3, 4, 5\}$ and $S_2 = \{2, 3\}$, $S_3 = \{3, 4\}$ and $K = 3$.

Given a finite decomposable graph $\mathcal{G} = (V, E)$, let $\mathcal{G}^*$ be its complementary graph, i.e. $\mathcal{G}^* = (V, E^c)$, where the complementary of $E$ is taken as the edges that do not exist in $E$ (an edge of the form $\{i, i\}$ is not allowed). Recall that $\mathcal{C}_\mathcal{G}^*$ is the collection of cliques in $\mathcal{G}^*$. From now on we identify $V = \{v_1, \dots, v_d\} = \{1, \dots, d\}$, and use $x_1, \dots, x_d$ to denote indeterminate variables associated to the vertices. Let $|C|$ denote the number of vertices in $C$, and $\pi_C(x) = \prod_{i \in C} x_i$, with the convention $\pi_\emptyset(x) = 1$, for $x = (x_i)_{i \in V}$. We define the graph polynomial $\Delta_\mathcal{G}$ of formal variables $(x_i, i \in V)$ by

$$ \Delta_{\mathcal{G}}(x) = \sum_{C \in \mathcal{C}_{\mathcal{G}}^*} (-1)^{|C|} \pi_C(x). $$
To fix the idea, one can think of the $x_i$ as real numbers. In fact they are generators of a monoid algebra defined in Section 2.3. For $A \subset V$, let $\mathcal{G}_A$ be the graph induced by the subset $A$ of $\mathcal{G}$, that is, defined by

$$ \mathcal{G}_A = (A, \{\{i, j\} \in E, i, j \in A\}), $$

and

$$ M_G = \{x \in (0, 1)^d, \forall A \subset V, \Delta_{\mathcal{G}_A}(x_A) > 0\} $$

where $x_A = (x_i)_{i \in A}$. We are ready to define the graph Dirichlet distribution.

**Theorem 2.2** (Definition of Graph Dirichlet distribution). Given a finite decomposable graph $\mathcal{G} = (V, E)$, let $|V| = d$, for $\alpha \in (0, \infty)^d$ and $\beta > 0$, a random vector $X = (X_i)_{i \in V} \in (0, 1)^V$ is $\mathcal{G}$-Dirichlet distributed with parameters $\alpha$ and $\beta$ if it has the probability density function

$$ f(x) = K_{\mathcal{G}}(\alpha, \beta) 1_{M_{\mathcal{G}}}(x) \Delta_{\mathcal{G}}(x)^{\beta-1} \prod_{i \in V} x_i^{\alpha_i-1} $$

where

$$ K_{\mathcal{G}}(\alpha, \beta) = \frac{\prod_{C \in \mathcal{C}_{\mathcal{G}}^{+}} \Gamma(|\alpha_C| + \beta)}{\Gamma(\beta)^m \prod_{i \in V} \Gamma(\alpha_i) \prod_{S \in \mathcal{S}_{\mathcal{G}}^{-}} \Gamma(|\alpha_S| + \beta)^{\nu_S}}, $$

and $\mathcal{C}_{\mathcal{G}}^{+}$ is the collection of maximal cliques of $\mathcal{G}$, $\mathcal{S}_{\mathcal{G}}$ is the collection of minimal separators of $\mathcal{G}$ and $\nu_S$ is the multiplicity of $S$, and $|\alpha_A| = \sum_{i \in A} \alpha_i$ for any $A \subset V$, and $m$ is the number of connected components of $\mathcal{G}$.

**Example 2.3** (Examples on complete graphs and on the nasty graph).

(1) For $d \ge 2$, let $\mathcal{G} = K_{d-1}$ be the complete graph with $d-1$ vertices. $\mathcal{G}^*$ is the completely disconnected graph, so it only has cliques of order 0 and 1. If we denote

$$ x_d := \Delta_{\mathcal{G}}(x) = 1 - x_1 - x_2 - \dots - x_{d-1}, $$

and note the fact that there is only one maximal clique of $\mathcal{G}$: $\mathcal{G}$ itself, then we recover the classical Dirichlet distribution discussed in (7).

(2) Let $\mathcal{G}$ be the nasty graph depicted in Figure 5, then we have

$$ \Delta_{\mathcal{G}}(x) = 1 - x_1 - x_2 - x_3 - x_4 - x_5 + x_1 x_5 + x_1 x_4 + x_2 x_5. $$

It appears that, by definition,

$$ \int_{M_{\mathcal{G}}} \Delta_{\mathcal{G}}(x)^{\beta-1} \prod_{i=1}^{5} x_i^{\alpha_i-1} \prod_{i=1}^{5} dx_i = \frac{\Gamma(\beta) \prod_{i=1}^{5} \Gamma(\alpha_i) \cdot \Gamma(\alpha_2 + \alpha_3 + \beta) \Gamma(\alpha_3 + \alpha_4 + \beta)}{\Gamma(\alpha_1 + \alpha_2 + \alpha_3 + \beta) \Gamma(\alpha_2 + \alpha_3 + \alpha_4 + \beta) \Gamma(\alpha_3 + \alpha_4 + \alpha_5 + \beta)}. $$

## 2.3. The graph negative multinomial distribution

Similar to the shooting board game, we can construct a distribution for which the graph Dirichlet distribution is its conjugate prior.

**Theorem 2.4** (Definition of Graph negative multinomial distribution). We use the same notations as in Theorem 2.2. Let $\mathcal{G} = (V, E)$ be a finite decomposable graph. A random vector $N = (N_i)_{i \in V} \in \mathbb{N}^V$ is distributed according to the $\mathcal{G}$-negative multinomial distribution of parameters $r > 0$ and $p = (p_i)_{i \in V} \in M_{\mathcal{G}}$, if

$$ \mathbb{P}(N_i = n_i, 1 \le i \le d) = \frac{K_{\mathcal{G}}(n, r)}{\pi_V(n)} \Delta_{\mathcal{G}}(p)^r \prod_{i \in V} p_i^{n_i}, \quad (9) $$
To fix the idea, one can think of the $x_i$ as real numbers. In fact they are generators of a monoid algebra defined in Section 2.3. For $A \subset V$, let $\mathcal{G}_A$ be the graph induced by the subset $A$ of $\mathcal{G}$, that is, defined by

$$ \mathcal{G}_A = (A, \{\{i, j\} \in E, i, j \in A\}), $$

and

$$ M_G = \{x \in (0, 1)^d, \forall A \subset V, \Delta_{\mathcal{G}_A}(x_A) > 0\} $$

where $x_A = (x_i)_{i \in A}$. We are ready to define the graph Dirichlet distribution.

**Theorem 2.2** (Definition of Graph Dirichlet distribution). Given a finite decomposable graph $\mathcal{G} = (V, E)$, let $|V| = d$, for $\alpha \in (0, \infty)^d$ and $\beta > 0$, a random vector $X = (X_i)_{i \in V} \in (0, 1)^V$ is $\mathcal{G}$-Dirichlet distributed with parameters $\alpha$ and $\beta$ if it has the probability density function

$$ f(x) = K_{\mathcal{G}}(\alpha, \beta) 1_{M_{\mathcal{G}}}(x) \Delta_{\mathcal{G}}(x)^{\beta-1} \prod_{i \in V} x_i^{\alpha_i-1} $$

where

$$ K_{\mathcal{G}}(\alpha, \beta) = \frac{\prod_{C \in \mathcal{C}_{\mathcal{G}}^{+}} \Gamma(|\alpha_C| + \beta)}{\Gamma(\beta)^m \prod_{i \in V} \Gamma(\alpha_i) \prod_{S \in \mathcal{S}_{\mathcal{G}}^{-}} \Gamma(|\alpha_S| + \beta)^{\nu_S}}, $$

and $\mathcal{C}_{\mathcal{G}}^{+}$ is the collection of maximal cliques of $\mathcal{G}$, $\mathcal{S}_{\mathcal{G}}$ is the collection of minimal separators of $\mathcal{G}$ and $\nu_S$ is the multiplicity of $S$, and $|\alpha_A| = \sum_{i \in A} \alpha_i$ for any $A \subset V$, and $m$ is the number of connected components of $\mathcal{G}$.

**Example 2.3** (Examples on complete graphs and on the nasty graph).

(1) For $d \ge 2$, let $\mathcal{G} = K_{d-1}$ be the complete graph with $d-1$ vertices. $\mathcal{G}^*$ is the completely disconnected graph, so it only has cliques of order 0 and 1. If we denote

$$ x_d := \Delta_{\mathcal{G}}(x) = 1 - x_1 - x_2 - \dots - x_{d-1}, $$

and note the fact that there is only one maximal clique of $\mathcal{G}$: $\mathcal{G}$ itself, then we recover the classical Dirichlet distribution discussed in (7).

(2) Let $\mathcal{G}$ be the nasty graph depicted in Figure 5, then we have

$$ \Delta_{\mathcal{G}}(x) = 1 - x_1 - x_2 - x_3 - x_4 - x_5 + x_1 x_5 + x_1 x_4 + x_2 x_5. $$

It appears that, by definition,

$$ \int_{M_{\mathcal{G}}} \Delta_{\mathcal{G}}(x)^{\beta-1} \prod_{i=1}^{5} x_i^{\alpha_i-1} \prod_{i=1}^{5} dx_i = \frac{\Gamma(\beta) \prod_{i=1}^{5} \Gamma(\alpha_i) \cdot \Gamma(\alpha_2 + \alpha_3 + \beta) \Gamma(\alpha_3 + \alpha_4 + \beta)}{\Gamma(\alpha_1 + \alpha_2 + \alpha_3 + \beta) \Gamma(\alpha_2 + \alpha_3 + \alpha_4 + \beta) \Gamma(\alpha_3 + \alpha_4 + \alpha_5 + \beta)}. $$

## 2.3. The graph negative multinomial distribution

Similar to the shooting board game, we can construct a distribution for which the graph Dirichlet distribution is its conjugate prior.

**Theorem 2.4** (Definition of Graph negative multinomial distribution). We use the same notations as in Theorem 2.2. Let $\mathcal{G} = (V, E)$ be a finite decomposable graph. A random vector $N = (N_i)_{i \in V} \in \mathbb{N}^V$ is distributed according to the $\mathcal{G}$-negative multinomial distribution of parameters $r > 0$ and $p = (p_i)_{i \in V} \in M_{\mathcal{G}}$, if

$$ \mathbb{P}(N_i = n_i, 1 \le i \le d) = \frac{K_{\mathcal{G}}(n, r)}{\pi_V(n)} \Delta_{\mathcal{G}}(p)^r \prod_{i \in V} p_i^{n_i}, \quad (9) $$
and this expression defines a probability mass function on $\mathbb{N}^V$. Moreover, the $\mathcal{G}$-Dirichlet distribution is a conjugate prior for $N$.

Note that, when $\mathcal{G}$ is a complete graph, we recover the negative multinomial distribution defined in (8).

Next we give a probabilistic interpretation of the $\mathcal{G}$-negative multinomial distribution such as the shooting board game, i.e. we will describe a random experiment such that, if $N$ is $\mathcal{G}$-negative multinomial distributed, then the probability of outcome $n$ equals the one defined in (9).

The interpretation uses a theorem of Cartier and Foata [6], which holds for any graph. To simplify our presentation, we will rephrase their theorem in our setting. Recall that we fix $\mathcal{G} = (V, E)$, a finite decomposable graph. Consider $V$ as the alphabet, its elements are called letters, and let $V^*$ denote the free monoid generated<fnref n="1" /> by $V$. Elements of $V^*$ are called words. Recall that $E^c$ is the edge set of the complementary graph $\mathcal{G}^*$, it induces a commutation structure on $V$: $v_1v_2 = v_2v_1$ if and only if $\{v_1, v_2\} \in E^c$.

We say that two words $w, w'$ are adjacent if there is $w_1, w_2 \in V^*$ and $\{v_1, v_2\} \in E^c$ such that

$$w = w_1v_1v_2w_2, \quad w' = w_1v_2v_1w_2.$$

Two words $w, w'$ are equivalent, and denoted by $w \sim w'$, if there is a sequence of words $w_0 = w, w_1, \dots, w_p = w'$ such that consecutive words in the sequence are adjacent. Let $L = V^*/\sim$ be the quotient monoid. Elements in $L$ are denoted by $[w]$, where $w$ is any representative of the equivalent class $[w]$. We say that $L$ is the quotient monoid induced by $\mathcal{G} = (V, E)$.

For any clique $C \in \mathcal{C}_{G^*}$, we denote by $[C] = [\pi_C]$, the equivalent class of product of letters in $C$, this notation is well-defined since all vertices in $C$ commute with each other.

**Theorem 2.5** (Cartier Foata). For any graph $\mathcal{G} = (V, E)$, let $L$ be the quotient monoid induced by $\mathcal{G}$. The following equality holds in the monoid algebra of $L$ over $\mathbb{Z}$,

$$\left( \sum_{C \in \mathcal{C}_{G^*}} (-1)^{|C|} [C] \right)^{-1} = \sum_{[w] \in L} [w]. \qquad (10)$$

**Remark 2.6** (General graph). The above theorem holds for any finite graph, but we only use it for decomposable graph $\mathcal{G}$. When the graph is not decomposable, one can still define the Graph Dirichlet distribution, but our explicit expression of probabilities and normalizing constant no longer hold.

**Corollary 2.7.** Let $L$ be the quotient monoid induced by a decomposable graph $\mathcal{G} = (V, E)$. Let $\varepsilon: L \to \mathbb{N}^V$ be such that $\varepsilon([w])$ counts the number of each letters in $w$, any representative of $[w]$, clearly $\varepsilon$ is well defined. Fix $n \in \mathbb{N}^V$, the number of elements $[w]$ in the quotient monoid $L$ such that $\varepsilon([w]) = n$ equals $\frac{K_{\mathcal{G}}(n)}{\pi_V(n)}$, where $K_{\mathcal{G}}(n) = K_{\mathcal{G}}(n, 1)$.

By the above corollary, we have, the probability that a $\mathcal{G}$-negative multinomial (with parameters $r = 1$, $p \in M_{\mathcal{G}}$) distributed random variable $N$ equals $n$ is

$$\begin{aligned} \mathbb{P}(N = n) &:= p(n) = \frac{K_{\mathcal{G}}(n)}{\pi_V(n)} \Delta_{\mathcal{G}}(p) \prod_{i \in V} p_i^{n_i} \\ &= \left( \frac{K_{\mathcal{G}}(n)}{\pi_V(n)} \prod_{i \in V} p_i^{n_i} \right) (\Delta_{\mathcal{G}}(p)^{-1})^{-1} \\ &= \left( \sum_{[w]: \varepsilon([w]) = n} \prod_{i} p_i^{n_i} \right) \left( \sum_{[w] \in L} \pi_w(p) \right)^{-1} \end{aligned}$$

<footnote n="1">¹with the operation as concatenation of words, i.e. finite sequence of letters.</footnote>
and this expression defines a probability mass function on $\mathbb{N}^V$. Moreover, the $\mathcal{G}$-Dirichlet distribution is a conjugate prior for $N$.

Note that, when $\mathcal{G}$ is a complete graph, we recover the negative multinomial distribution defined in (8).

Next we give a probabilistic interpretation of the $\mathcal{G}$-negative multinomial distribution such as the shooting board game, i.e. we will describe a random experiment such that, if $N$ is $\mathcal{G}$-negative multinomial distributed, then the probability of outcome $n$ equals the one defined in (9).

The interpretation uses a theorem of Cartier and Foata [6], which holds for any graph. To simplify our presentation, we will rephrase their theorem in our setting. Recall that we fix $\mathcal{G} = (V, E)$, a finite decomposable graph. Consider $V$ as the alphabet, its elements are called letters, and let $V^*$ denote the free monoid generated<fnref n="1" /> by $V$. Elements of $V^*$ are called words. Recall that $E^c$ is the edge set of the complementary graph $\mathcal{G}^*$, it induces a commutation structure on $V$: $v_1v_2 = v_2v_1$ if and only if $\{v_1, v_2\} \in E^c$.

We say that two words $w, w'$ are adjacent if there is $w_1, w_2 \in V^*$ and $\{v_1, v_2\} \in E^c$ such that

$$w = w_1v_1v_2w_2, \quad w' = w_1v_2v_1w_2.$$

Two words $w, w'$ are equivalent, and denoted by $w \sim w'$, if there is a sequence of words $w_0 = w, w_1, \dots, w_p = w'$ such that consecutive words in the sequence are adjacent. Let $L = V^*/\sim$ be the quotient monoid. Elements in $L$ are denoted by $[w]$, where $w$ is any representative of the equivalent class $[w]$. We say that $L$ is the quotient monoid induced by $\mathcal{G} = (V, E)$.

For any clique $C \in \mathcal{C}_{G^*}$, we denote by $[C] = [\pi_C]$, the equivalent class of product of letters in $C$, this notation is well-defined since all vertices in $C$ commute with each other.

**Theorem 2.5** (Cartier Foata). For any graph $\mathcal{G} = (V, E)$, let $L$ be the quotient monoid induced by $\mathcal{G}$. The following equality holds in the monoid algebra of $L$ over $\mathbb{Z}$,

$$\left( \sum_{C \in \mathcal{C}_{G^*}} (-1)^{|C|} [C] \right)^{-1} = \sum_{[w] \in L} [w]. \qquad (10)$$

**Remark 2.6** (General graph). The above theorem holds for any finite graph, but we only use it for decomposable graph $\mathcal{G}$. When the graph is not decomposable, one can still define the Graph Dirichlet distribution, but our explicit expression of probabilities and normalizing constant no longer hold.

**Corollary 2.7.** Let $L$ be the quotient monoid induced by a decomposable graph $\mathcal{G} = (V, E)$. Let $\varepsilon: L \to \mathbb{N}^V$ be such that $\varepsilon([w])$ counts the number of each letters in $w$, any representative of $[w]$, clearly $\varepsilon$ is well defined. Fix $n \in \mathbb{N}^V$, the number of elements $[w]$ in the quotient monoid $L$ such that $\varepsilon([w]) = n$ equals $\frac{K_{\mathcal{G}}(n)}{\pi_{V}(n)}$, where $K_{\mathcal{G}}(n) = K_{\mathcal{G}}(n, 1)$.

By the above corollary, we have, the probability that a $\mathcal{G}$-negative multinomial (with parameters $r = 1$, $p \in M_{\mathcal{G}}$) distributed random variable $N$ equals $n$ is

$$\begin{align*}
\mathbb{P}(N = n) &:= p(n) = \frac{K_{\mathcal{G}}(n)}{\pi_{V}(n)} \Delta_{\mathcal{G}}(p) \prod_{i \in V} p_{i}^{n_i} \\
&= \left( \frac{K_{\mathcal{G}}(n)}{\pi_{V}(n)} \prod_{i \in V} p_{i}^{n_i} \right) (\Delta_{\mathcal{G}}(p)^{-1})^{-1} \\
&= \left( \sum_{[w]:\varepsilon([w])=n} \prod_{i} p_{i}^{n_i} \right) \left( \sum_{[w] \in L} \pi_{w}(p) \right)^{-1}
\end{align*}$$

<footnote n="1">¹with the operation as concatenation of words, i.e. finite sequence of letters.</footnote>
$$= \frac{\sum_{[w]:\varepsilon([w])=n} \pi_w(p)}{\sum_{[w]\in L} \pi_w(p)}$$

where we used (10) to deduce that $\Delta_G(p)^{-1} = \sum_{[w]\in L} \pi_w(p)$, by the (monoid algebra extension of the) specification map $i \mapsto p_i$, $\forall i \in V$. We see that, to sample $N$, we can first sample an element $[w]$ in $L$ with probability proportional to $\pi_w(p)$, then take the pushforward measure by $\varepsilon$. This process generalizes the shooting board game.

## REFERENCES

[1] ADELMAN, O. AND ENRIQUEZ, N. (2004) Random walks in random environment: what a single trajectory tells. *Israel Journal of Mathematics* **142**, 205–220.

[2] ANDREOLETTI, P. AND DIEL, R. (2014) The heavy range of randomly biased walks on trees *Stoch. Proc. Appl.* **130**, 962–999.

[3] ANDREOLETTI, P., LOUKIANOVA, D. AND MATIAS, C. (2015) Hidden Markov model for parameter estimation of a random walk in a Markov environment. *ESAIM Probab. Stat.* **19**, 605–625.

[4] AURZADA, F., DEVULDER, A., GUILLOTIN-PLANTARD, N. AND PÈNE, F. (2017) Random walks and branching processes in correlated Gaussian environment. *J. Stat. Phys.* **166**, 1–23.

[5] BROX, TH. (1986) A one-dimensional diffusion process in a Wiener medium. *Ann. Probab.* **14**, 1206–1218.

[6] CARTIER, P., FOATA, D. AND LASS, B. Commutation and Rearrangements. Monograph: Problèmes combinatoires de commutation et réarrangements, in: Lecture Notes in Math **85**, 1969.

[7] CHERNOV, A.A. (1967) Reduplication of a multicomponent chain by the mechanism of “lightning”. *Biophysica* **12**, 297–301 (in Russian).

[8] COCCO, S. AND MONASSON, R. (2008) Reconstructing a random potential from its random walks. *Europhysics Letters* **81**, 20002.

[9] COMETS, F., FALCONNET M., LOUKIANOV, O. AND LOUKIANOVA, D. (2016) Maximum likelihood estimator consistency for recurrent random walk in a parametric random environment with finite support *Stochastic Process. Appl.* **126**, 3578–3604.

[10] COMETS, F., FALCONNET, M., LOUKIANOV, O., LOUKIANOVA, D. AND MATIAS, C. (2014) Maximum likelihood estimator consistency for a ballistic random walk in a parametric random environment. *Stoch. Proc. Appl.* **124**, 268–288.

[11] DEDECKER, J. AND GOUËZEL, S. (2015) Subgaussian concentration inequalities for geometrically ergodic Markov chains. *Electron. Commun. Probab.* **20**, 1–12.

[12] DEVULDER, A. (2007) The speed of a branching system of random walks in random environment. *Statist. Probab. Lett.* **77**, 1712–1721.

[13] DIEL, R. AND LERASLE, M. (2014) Non parametric estimation for random walks in random environment. *Stochastic Process. Appl.* **128**, 132–155.

[14] ENRIQUEZ N., LUCAS C. AND SIMENHAUS F. (2010) The Arcsine law as the limit of the internal DLA cluster generated by Sinai’s walk. *Ann. Inst. H. Poincaré Probab. Stat.* **46**, 991–1000.

[15] FALCONNET, M., GLOTER, A. AND LOUKIANOVA, D. (2014) Maximum likelihood estimation in the context of a sub-ballistic random walk in a parametric random environment. *Math. Methods Statist.* **23**, 159–175.

[16] FALCONNET, M., LOUKIANOVA, D. AND MATIAS, C. (2014) Asymptotic normality and efficiency of the maximum likelihood estimator for the parameter of a ballistic random walk in a random environment. *Math. Methods Statist.* **23**, 1–19.

[17] GOLDENSHLUGER, A. AND LEPSKI, O. (2008) Universal pointwise selection rule in multivariate function estimation. *Bernoulli* **14**, 1150–1190.

[18] GOLOSOV, A. O. (1986) Limit distributions for a random walk in a critical one-dimensional random environment. *Uspekhi Mat. Nauk* **41** (2(248)), 189–190.

[19] HAVET, A., LERASLE, M. AND MOULINES, E. (2019) Density Estimation for RWRE. *Mathematical Methods of Statistics* **28**, 18–38.

[20] HUGHES, B.D.: *Random Walks and Random Environment, vol. II: Random Environments*. Oxford Science Publications, Oxford, 1996.

[21] JOHNSON, N. L. AND KOTZ, S. Urn models and their application. An approach to modern discrete probability theory. Wiley Series in Probability and Mathematical Statistics. John Wiley & Sons, New York-London-Sydney, 1977.

[22] KESTEN, H., KOZLOV, M. V. AND SPITZER, F. (1975) A limit law for random walk in a random environment. *Compositio Math.* **30**, 145–168.

[23] KNUTH, DONALD E. The art of computer programming, Volume 4, Fascicle 6: Satisfiability. Addison-Wesley Professional, 2015.

[24] KOCHLER M. Random Walks in Random Environment, Random Orientations and Branching. Doktors der Naturwissenschaften genehmigten Dissertation, Technische Universität München (2012).

[25] KOLODZIEJEK B., JACEK WESOLOWSKI AND ZENG, X. (2023) Discrete parametric graphical models with a Dirichlet type priors. Preprint arXiv, arXiv:2301.06058.
$$= \frac{\sum_{[w]:\varepsilon([w])=n} \pi_w(p)}{\sum_{[w]\in L} \pi_w(p)}$$

where we used (10) to deduce that $\Delta_G(p)^{-1} = \sum_{[w]\in L} \pi_w(p)$, by the (monoid algebra extension of the) specification map $i \mapsto p_i$, $\forall i \in V$. We see that, to sample $N$, we can first sample an element $[w]$ in $L$ with probability proportional to $\pi_w(p)$, then take the pushforward measure by $\varepsilon$. This process generalizes the shooting board game.

## REFERENCES

[1] ADELMAN, O. AND ENRIQUEZ, N. (2004) Random walks in random environment: what a single trajectory tells. *Israel Journal of Mathematics* **142**, 205–220.

[2] ANDREOLETTI, P. AND DIEL, R. (2014) The heavy range of randomly biased walks on trees *Stoch. Proc. Appl.* **130**, 962–999.

[3] ANDREOLETTI, P., LOUKIANOVA, D. AND MATIAS, C. (2015) Hidden Markov model for parameter estimation of a random walk in a Markov environment. *ESAIM Probab. Stat.* **19**, 605–625.

[4] AURZADA, F., DEVULDER, A., GUILLOTIN-PLANTARD, N. AND PÈNE, F. (2017) Random walks and branching processes in correlated Gaussian environment. *J. Stat. Phys.* **166**, 1–23.

[5] BROX, TH. (1986) A one-dimensional diffusion process in a Wiener medium. *Ann. Probab.* **14**, 1206–1218.

[6] CARTIER, P., FOATA, D. AND LASS, B. Commutation and Rearrangements. Monograph: Problèmes combinatoires de commutation et réarrangements, in: Lecture Notes in Math **85**, 1969.

[7] CHERNOV, A.A. (1967) Reduplication of a multicomponent chain by the mechanism of “lightning”. *Biophysica* **12**, 297–301 (in Russian).

[8] COCCO, S. AND MONASSON, R. (2008) Reconstructing a random potential from its random walks. *Europhysics Letters* **81**, 20002.

[9] COMETS, F., FALCONNET M., LOUKIANOV, O. AND LOUKIANOVA, D. (2016) Maximum likelihood estimator consistency for recurrent random walk in a parametric random environment with finite support *Stochastic Process. Appl.* **126**, 3578–3604.

[10] COMETS, F., FALCONNET, M., LOUKIANOV, O., LOUKIANOVA, D. AND MATIAS, C. (2014) Maximum likelihood estimator consistency for a ballistic random walk in a parametric random environment. *Stoch. Proc. Appl.* **124**, 268–288.

[11] DEDECKER, J. AND GOUÈZEL, S. (2015) Subgaussian concentration inequalities for geometrically ergodic Markov chains. *Electron. Commun. Probab.* **20**, 1–12.

[12] DEVULDER, A. (2007) The speed of a branching system of random walks in random environment. *Statist. Probab. Lett.* **77**, 1712–1721.

[13] DIEL, R. AND LERASLE, M. (2014) Non parametric estimation for random walks in random environment. *Stochastic Process. Appl.* **128**, 132–155.

[14] ENRIQUEZ N., LUCAS C. AND SIMENHAUS F. (2010) The Arcsine law as the limit of the internal DLA cluster generated by Sinai’s walk. *Ann. Inst. H. Poincaré Probab. Stat.* **46**, 991–1000.

[15] FALCONNET, M., GLOTER, A. AND LOUKIANOVA, D. (2014) Maximum likelihood estimation in the context of a sub-ballistic random walk in a parametric random environment. *Math. Methods Statist.* **23**, 159–175.

[16] FALCONNET, M., LOUKIANOVA, D. AND MATIAS, C. (2014) Asymptotic normality and efficiency of the maximum likelihood estimator for the parameter of a ballistic random walk in a random environment. *Math. Methods Statist.* **23**, 1–19.

[17] GOLDENSHLUGER, A. AND LEPSKI, O. (2008) Universal pointwise selection rule in multivariate function estimation. *Bernoulli* **14**, 1150–1190.

[18] GOLOSOV, A. O. (1986) Limit distributions for a random walk in a critical one-dimensional random environment. *Uspekhi Mat. Nauk* **41** (2(248)), 189–190.

[19] HAVET, A., LERASLE, M. AND MOULINES, E. (2019) Density Estimation for RWRE. *Mathematical Methods of Statistics* **28**, 18–38.

[20] HUGHES, B.D.: *Random Walks and Random Environment, vol. II: Random Environments*. Oxford Science Publications, Oxford, 1996.

[21] JOHNSON, N. L. AND KOTZ, S. Urn models and their application. An approach to modern discrete probability theory. Wiley Series in Probability and Mathematical Statistics. John Wiley & Sons, New York-London-Sydney, 1977.

[22] KESTEN, H., KOZLOV, M. V. AND SPITZER, F. (1975) A limit law for random walk in a random environment. *Compositio Math.* **30**, 145–168.

[23] KNUTH, DONALD E. The art of computer programming, Volume 4, Fascicle 6: Satisfiability. Addison-Wesley Professional, 2015.

[24] KOCHLER M. Random Walks in Random Environment, Random Orientations and Branching. Doktors der Naturwissenschaften genehmigten Dissertation, Technische Universität München (2012).

[25] KOLODZIEJEK B., JACEK WESOLOWSKI AND ZENG, X. (2023) Discrete parametric graphical models with a Dirichlet type priors. Preprint arXiv, arXiv:2301.06058.
[26] KOMLÓS, J., MAJOR, P. AND TUSNÁDY, G. (1975) An approximation of partial sums of independent rv's and the sample df. I, Wahrsch verw Gebiete/Probability Theory and Related Fields 32, 111-131.

[27] MCDIARMID, C. (1989) On the method of bounded differences. In *Surveys in combinatorics, 1989* (Norwich, 1989), volume 141 of *London Math. Soc. Lecture Note Ser.*, pages 148–188. Cambridge Univ. Press, Cambridge, 1989.

[28] RÉVÉSZ, P.: *Random walk in random and non-random environments*, second edition. World Scientific, Singapore, 2005.

[29] SABOT, C. (2011) Random walks in random Dirichlet environment are transient in dimension $d \ge 3$. *Probability theory and related fields* 151, 297–317.

[30] SABOT, C. AND TOURNIER, L. (2016) Random walks in Dirichlet environment: an overview. *Annales de la Faculté des Sciences de Toulouse Sér. 6*, Vol. 26, No. 2.

[31] SCHUMACHER, S. (1985) Diffusions with random coefficients. *Contemp. Math.* 41, 351–356.

[32] SHI, Z. (2001) Sinai's walk via stochastic calculus. *Panoramas et Synthèses* 12, 53–74, Société mathématique de France.

[33] SINAI, YA. G. (1982) The limiting behavior of a one-dimensional random walk in a random medium. *Th. Probab. Appl.*, 27, 256–268.

[34] SOLOMON, F. (1975) Random walks in a random environment. *Ann. Probab.*, 3, 1–31.

[35] TEMKIN, D.E. (1972) One-dimensional random walks in a two-component chain. *Soviet math. Dokl.* 13, 1172–1176.

[36] ZEITOUNI, O. (2004) Lecture notes on random walks in random environment. *École d'été de probabilités de Saint-Flour 2001*. Lecture Notes in Math. 1837, 189–312. Springer, Berlin.

[37] ZENG, X. (2015) Marches aléatoires renforcées et opérateurs de Schrödinger aléatoires. Phd thesis, Université Claude Bernard Lyon 1, available at https://tel.archives-ouvertes.fr/tel-01267712.

[38] ZINDY, O. (2008) Upper limits of Sinai's walk in random scenery. *Stoch. Proc. Appl.* 118, 981–1003.
[26] KOMLÓS, J., MAJOR, P. AND TUSNÁDY, G. (1975) An approximation of partial sums of independent rv's and the sample df. I, Wahrsch verw Gebiete/Probability Theory and Related Fields 32, 111–131.

[27] McDIARMID, C. (1989) On the method of bounded differences. In *Surveys in combinatorics, 1989* (Norwich, 1989), volume 141 of *London Math. Soc. Lecture Note Ser.*, pages 148–188. Cambridge Univ. Press, Cambridge, 1989.

[28] RÉVÉSZ, P.: *Random walk in random and non-random environments*, second edition. World Scientific, Singapore, 2005.

[29] SABOT, C. (2011) Random walks in random Dirichlet environment are transient in dimension $d \ge 3$. *Probability theory and related fields* 151, 297–317.

[30] SABOT, C. AND TOURNIER, L. (2016) Random walks in Dirichlet environment: an overview. *Annales de la Faculté des Sciences de Toulouse Sér. 6*, Vol. 26, No. 2.

[31] SCHUMACHER, S. (1985) Diffusions with random coefficients. *Contemp. Math.* 41, 351–356.

[32] SHI, Z. (2001) Sinai's walk via stochastic calculus. *Panoramas et Synthèses* 12, 53–74, Société mathématique de France.

[33] SINAI, YA. G. (1982) The limiting behavior of a one-dimensional random walk in a random medium. *Th. Probab. Appl.*, 27, 256–268.

[34] SOLOMON, F. (1975) Random walks in a random environment. *Ann. Probab.*, 3, 1–31.

[35] TEMKIN, D.E. (1972) One-dimensional random walks in a two-component chain. *Soviet math. Dokl.* 13, 1172–1176.

[36] ZEITOUNI, O. (2004) Lecture notes on random walks in random environment. *École d'été de probabilités de Saint-Flour 2001*. Lecture Notes in Math. 1837, 189–312. Springer, Berlin.

[37] ZENG, X. (2015) Marches aléatoires renforcées et opérateurs de Schrödinger aléatoires. Phd thesis, Université Claude Bernard Lyon 1, available at https://tel.archives-ouvertes.fr/tel-01267712.

[38] ZINDY, O. (2008) Upper limits of Sinai's walk in random scenery. *Stoch. Proc. Appl.* 118, 981–1003.