\(
\newcommand\egaldef{\stackrel{\tiny def}{=}}
\newcommand{\ep}{\varepsilon}
\newcommand{\Zset}{\mathbb{Z}}
\newcommand{\Nset}{\mathbb{N}}
\newcommand{\Rset}{\mathbb{R}}
\newcommand{\Cset}{\mathbb{C}}
\newcommand{\CN}{\mathcal{N}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\E}{\mathbb{E}}
\newcommand{\EE}[1]{\E\left[#1\right]}
\newcommand{\PCond}[2]{\PP\left[#1\middle| #2\right]}
\newcommand{\ECond}[2]{\E\left[#1\middle| #2\right]}
\newcommand{\PP}{\mathbb{P}}
\newcommand{\CF}{\mathcal{F}}
\newcommand{\CG}{\mathcal{G}}
\newcommand{\CP}{\mathcal{P}}
\newcommand{\CC}{\mathcal{C}}
\newcommand{\CD}{\mathcal{D}}
\newcommand{\CO}{\mathcal{O}}
\newcommand{\CL}{\mathcal{L}}
\newcommand{\CA}{\mathcal{A}}
\newcommand{\CT}{\mathcal{T}}
\newcommand{\CW}{\mathcal{W}}
\newcommand{\CS}{\mathcal{S}}
\newcommand{\CH}{\mathcal{H}}
\newcommand{\CB}{\mathcal{B}}
\newcommand{\CM}{\mathcal{M}}
\renewcommand{\S}[1]{\ensuremath{S\textsc{\lowercase{#1}}}}
\newcommand{\btheta}{\boldsymbol{\theta}}
\newcommand{\limite}[2]{\mathop{\longrightarrow}
\limits_{\mathrm{#1}}^{\mathrm{#2}}}
\newcommand{\limiteloi}[2]{\mathop{\rightsquigarrow}
\limits_{\mathrm{#1}}^{\mathrm{#2}}}
\newcommand\1{\mathbb{1}}
\newcommand\ind[1]{\1_{\{#1\}}}
\newcommand\muDisc{\mu_{d}}
\newcommand\muDiff{\mu_c}
\newcommand{\lpref}{\overleftarrow{\rm pref}}
\newcommand{\petitlpref}{\overleftarrow{\rm pref}}
\newcommand\idt{\mathbf{I}_H}
\newcommand\stp[1]{U_{#1}}
\newcommand\ie{\emph{i.e.}}
\newcommand\argmin{\mathbf{argmin}}
\newcommand\scal[1]{\left\langle #1 \right\rangle}
\newcommand\nrm[1]{\left\| #1 \right\|} %
\newcommand\abs[1]{\left| #1 \right|} %
\DeclareMathOperator{\cv}{\limite{n \to \infty}{}}
\DeclareMathOperator{\cvp}{\limite{n \to \infty}{P}}
\DeclareMathOperator{\cvl}{\limite{n \to \infty}{\CL}}
\DeclareMathOperator{\cvloi}{\limiteloi{n \to \infty}{\CL}}
\DeclareMathOperator{\cvmq}{\limite{n \to \infty}{\convLp_2}}
\DeclareMathOperator{\trace}{Tr}
\newcommand\Rlogo{\protect\includegraphics[height=1.8ex,keepaspectratio]{Rlogo.pdf}}
\DeclareMathOperator{\diag}{diag}
\DeclareMathOperator{\tr}{tr}
\DeclareMathOperator{\dilog}{Li}
\DeclareMathOperator{\var}{var}
\newcommand\bbox{\hfill\rule{2mm}{2mm}}
\newcommand\ordPart[1]{\mathop{\rm \sum _{#1}\uparrow}\nolimits}
\DeclareMathOperator{\Hess}{Hess}
\newcommand\lUn{L^1}
\newcommand\lDeux{L^2}
\newcommand\Zbar{\overline{Z}}
\newcommand\Tbar{\overline{T}}
\newcommand\wass[1]{\mathcal{W}_2\left(#1\right)}
\newcommand\law{\mathcal{L}}
\newcommand\cstHolder{C_3}
\newcommand\cstWass{C_4}
\newcommand\cstMoment{C_6}
\newcommand\assm[1]{\textbf{A#1}}
\newcommand\lmin{\lambda_{min}}
\newcommand\cG{c_\gamma}
\newcommand\covLimite{\Sigma}
\)
Récursivité au carrefour de la modélisation de séquences, des arbres aléatoires, des algorithmes stochastiques et des martingales
Résumé:
Ce mémoire est une synthèse de
plusieurs études à l'intersection des systèmes dynamiques dans l'analyse statistique de séquences, de l'analyse d'algorithmes dans des arbres aléatoires et des processus stochastiques discrets. Les résultats établis ont des applications dans des domaines variés allant des séquences biologiques aux
modèles de régression linéaire, processus de branchement, en passant par la statistique fonctionnelle et les estimations d'indicateurs de risque appliqués à l'assurance. Tous les résultats établis utilisent d'une façon ou d'une autre le caractère récursif de la structure étudiée, en faisant apparaître des invariants comme des martingales. Elles sont au cœ ur de ce mémoire, utilisées comme outils dans les preuves ou comme objets d'étude.
Mots-clés: Arbres digitaux de recherche, chaîne de Markov à mémoire variable, temps d’occurrences de motifs, système dynamique, trie des suffixes; lois fortes de martingales discrètes, modèles auto-régressifs, erreur d’estimation et de prédiction, algorithmes de gradient stochastiques, optimisation stochastique.
Recursion at the crossroads of sequence modeling, random trees, stochastic algorithms and martingales
Abstract: This monograph synthesizes several studies spanning from dynamical systems in the statistical analysis of sequences, to analysis of algorithms in random trees and discrete stochastic processes. These works find applications in various fields ranging from biological sequences to linear regression models, branching processes, through functional statistics and estimates of risk indicators for insurances. All the established results use, in one way or another, the recursive property of the structure under study, by highlighting invariants such as martingales, which are at the heart of this monograph, as tools as well as objects of study.
Key-words: Digital search trees, variable length Markov chain, occurrences time, dynamical system, suffix trie; strong laws for discrete martingales, auto-regressive models, estimation and prediction error, stochastic gradient algorithms, stochastic optimization.