%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[finalversion]{FPSAC2025}
\articlenumber{3}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}

\newtheorem{theorem}{Theorem}[section]
\newtheorem*{theorem*}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conj}[theorem]{Conjecture}
\newtheorem*{main-thm}{Main Theorem}


\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{question}[theorem]{Question}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{notation}[theorem]{Notation}

\newcommand{\op}[1]{\operatorname{#1}}


\newcommand{\bd}[1]{\mathbf{#1}}  % for bolding symbols
\newcommand{\eps}{\varepsilon}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\EE}{\mathbb{E}}
\newcommand{\id}{\mathbf{1}}

%michael's macros
\newcommand{\LandauO}{\mathcal{O}}
\newcommand{\Landauo}{o}

%baptiste's macros
\renewcommand{\P}{\mathbb{P}}
\newcommand{\summ}{\ensuremath{\mathbf{\Sigma}}}
\newcommand{\sett}{S}
\newcommand{\seps}{\ensuremath{\sett^\eps}}
\newcommand{\slow}{\ensuremath{\sett_{\text{low}}^\eps}}
\newcommand{\snorm}{\ensuremath{\sett_{\text{norm}}^\eps}}
\newcommand{\spec}{\ensuremath{\sett_{\text{spec}}^\eps}}
\newcommand{\E}{E}
\newcommand{\K}{K}
\newcommand{\M}{M}
\newcommand{\Rl}{R}
\newcommand{\quadruple}{\ensuremath{(n_1,n_2,h_1,h_2)}}
\newcommand{\nto}{\ensuremath{n\rightarrow\infty}}
\newcommand{\largev}{\ensuremath{n-2g \gg \log n}}

\newcommand{\artanh}{\operatorname{artanh}}
\newcommand{\f}[2]{f\left(\frac{#1}{#2}\right)}
\newcommand{\ff}[2]{f'\left(\frac{#1}{#2}\right)}
\newcommand{\fff}[2]{f''\left(\frac{#1}{#2}\right)}
\newcommand{\bigO}[1]{O\left({#1}\right)}
\newcommand{\smallo}[1]{o\left({#1}\right)}
\newcommand{\halfminth}{\left(\frac 1 2 -\theta\right)}
\newcommand{\err}{\bigO{n^{-1}\log^{-2}(n)}}
\newcommand{\unpluserr}{\left(1+\err\right)}
\newcommand{\bigpar}[1]{\left({#1}\right)}


\usepackage{lipsum}

%% define your title in the usual way
\title[Bivariate asymptotics via random walks]{Bivariate asymptotics via random walks: application to large genus maps}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
%% for more than 3 names, use the Oxford comma: One Author, Two Author, Red Author, \and Blue Author
\author[A. Elvey Price, W. Fang, B. Louf, and M.\ Wallner]{\texorpdfstring{%
Andrew Elvey Price\thanks{\href{mailto:andrew.elvey-price@cnrs.fr}{andrew.elvey-price@cnrs.fr}. Partially supported by ANR CartesEtPlus (ANR-23-CE48-0018) and ANR IsOMA (ANR-21-CE48-0007).}\addressmark{1},
%
Wenjie Fang\thanks{\href{mailto:wenjie.fang@univ-eiffel.fr}{wenjie.fang@univ-eiffel.fr}. Partially supported by ANR CartesEtPlus (ANR-23-CE48-0018), ANR IsOMA (ANR-21-CE48-0007), and the French-Austrian PHC Amadeus project ``Asymptotic behaviour of combinatorial structures''.}\addressmark{2},
\\
Baptiste Louf\thanks{\href{mailto:baptiste.louf@math.u-bordeaux.fr}{baptiste.louf@math.u-bordeaux.fr}. Partially supported by ANR CartesEtPlus (ANR-23-CE48-0018).}\addressmark{3}, 
\and 
Michael Wallner\thanks{\href{mailto:michael.wallner@tugraz.at}{michael.wallner@tugraz.at}. Partially supported by the Austrian Science Fund (FWF): P 34142 and the OeAD WTZ project FR~01/2023.}\addressmark{4} 
}{%
Andrew Elvey Price,
%
Wenjie Fang,
\\
Baptiste Louf, 
and 
Michael Wallner 
}}


%% then use \addressmark to match authors to institutions here
\address{%
\addressmark{1}CNRS and Institut Denis Poisson, Université de Tours, France \\ 
\addressmark{2}Univ Gustave Eiffel, CNRS, LIGM, F-77454 Marne-la-Vallée, France \\ 
\addressmark{3}CNRS and Institut de Mathématiques de Bordeaux, France \\ 
\addressmark{4}Institute of Discrete Mathematics, TU Graz, Austria 
}

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{We obtain bivariate asymptotics for the number of (unicellular) combinatorial maps (a model of discrete surfaces) as both the size and the genus grow. This work is related to two research topics that have been very active recently: multivariate asymptotics and large genus geometry.  
%
Our method consists in studying a linear recurrence for these numbers, and in fact it can be applied to many other linear recurrences. We discuss briefly the generality of our method and future research directions.}

% %% put your French abstract here, or comment this out if you don't have one
% \resume{\lipsum[2]}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{Maps, multivariate recurrences, random walks, asymptotic enumeration, large genus}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations; i.e., [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
\usepackage[backend=bibtex, giveninits]{biblatex}
\addbibresource{sample.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}

\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above

%%====================================%%
\section{Introduction}

This paper deals with \emph{multivariate asymptotics} and \emph{large genus geometry}, two recent topics that received a lot of traction in the past 15 years \cite{Agg,linear-genus,budzinski-louf,DGZZ,acsv_web}.

{Asymptotic enumeration} is one of the main branches of combinatorics, and it finds many applications; see, e.g., \cite{flajolet}. The univariate case (when one parameter tends to infinity) has been studied extensively and many general methods have been developed to tackle it, but the {multivariate} case is notoriously much harder. The main modern approach to this topic is Analytic Combinatorics in Several Variables (ACSV)~\cite{acsv_web}. However, the ACSV theory mostly only applies to rational and algebraic generating functions.

{Combinatorial maps} can be seen as a model of discrete surfaces or, alternatively, graphs on surfaces. Like other models of surfaces, there has been a growing interest recently in understanding their {large genus geometry} (see, e.g., \cite{budzinski-louf,DGZZ}), and it turns out that asymptotic enumeration plays a crucial role in this study\footnote{This is due to the simple reason  that probabilities and expectations are expressed in terms of ratios of enumerative quantities.}, for instance \cite{DGZZ} crucially relies on the asymptotics proven in \cite{Agg}.

In this paper, we compute the asymptotic number of unicellular maps in terms of two parameters (size and genus) by analyzing a {linear bivariate recurrence }satisfied by these numbers. Our method relies on two main ingredients: an \emph{asymptotic guess and check} approach, and modelling the recurrence by a \emph{random walk}. In \Cref{sec_guess} we give an informal overview of our approach, 
and in \Cref{sec_proof} we present the main ingredients of the proof.


Although we are presenting one particular case, our method should apply more generally, as it {only uses the recurrence and not the combinatorics of the model}. In \Cref{sec_discussion} we will discuss further applications and research directions. In particular, we explain how this method should apply to a class of bivariate sequences that are not (yet) tackled by the ACSV approach, as well as other large genus asymptotics problems.




\section{Main result on large genus unicellular maps}\label{sec_main_results}

A \emph{unicellular map} with $n$ edges and genus~$g$ is the combinatorial data of a $2n$-gon whose sides are identified two by two to form a compact, connected, oriented surface of genus~$g$, along with an additional distinguished oriented edge called the root; see \Cref{fig:map}.  Note that unicellular maps of genus $0$ are rooted plane trees.

\begin{figure}
    \centering
    \includegraphics[width=0.6\linewidth]{FPSAC.pdf}
    \caption{A unicellular map of genus $1$ with $3$ edges.}
    \label{fig:map}
\end{figure}


Let $\E(n,g)$ be the number of unicellular maps with $n$ edges and genus $g$. They  satisfy the \emph{Harer--Zagier recurrence formula}; see~\cite[page~460]{HarerZagier1986Euler}:% and ~\cite[Proposition~8]{ChapuyFerayFusy2013Unicellular}:
\begin{align}
    \label{eq:recurrence}
    (n+1)\E(n,g)=2(2n-1)\E(n-1,g)+(n-1)(2n-1)(2n-3)\E(n-2,g-1),
\end{align}
with boundary conditions 
\begin{equation}\label{eq_bdy}
    \E(0,0)=1 \qquad \text{ and } \qquad  \E(n,g)=0\text{ if } g<0 \text{ or } n<2g.
\end{equation}

\begin{theorem}[Main result on large genus unicellular maps]\label{thm_main}
Given a sequence\footnote{We will use the notation $g \equiv g_n$ to denote the omission of the dependency of $g$ on $n$. 
% We will omit the dependency of $g$ on $n$ from now on.
} $g \equiv g_n$ such that $\frac{n-2g}{\log n}\rightarrow \infty$ as $n\to\infty$, the following asymptotics hold:
\begin{equation}\label{eq_main_asympto}
    \E(n,g)\sim \frac{1}{2\sqrt{\pi}} \frac{\sqrt{g}(g/e)^g}{g!}n^{2g-2}e^{nf(\frac{g}{n})}{J}\left(\frac{g}{n}\right),
\end{equation}
with $f$ and $J$ defined as follows (see \Cref{fig:lambda-f-J}): 
For every $\theta\in[0,1/2]$, let %\footnote{We will also omit the dependency of $\lambda$ on $\theta$ from now on.} 
$\lambda \equiv \lambda(\theta) \in [0,1/4]$ be the unique value satisfying 
\[\theta=\frac{1}{2}-\frac{\lambda\log\left(\frac{1+\sqrt{1-4\lambda}}{1-\sqrt{1-4\lambda}}\right)}{\sqrt{1-4\lambda}}.\]
Then we define
% \begin{align*}
% f(\theta)& =  - \theta \log(1-4\lambda(\theta)) - (1-2\theta) \log(\lambda(\theta)) + 2(\log(2)-1)\theta,\\
% {J}(\theta)&=\sqrt{\frac{2}{\lambda(\theta)(1-2\theta-4\lambda(\theta)+4\theta\lambda(\theta))}}.
% \end{align*}
\begin{align*}
f(\theta)& =  - \theta \log(1-4\lambda) - (1-2\theta) \log(\lambda) + 2(\log(2)-1)\theta,\\
{J}(\theta)&=\sqrt{\frac{2}{\lambda(1-2\theta-4\lambda+4\theta\lambda)}}.
\end{align*}
\end{theorem}




\begin{figure}[t]
    \centering
    \newcommand{\myplotscale}{0.3\linewidth}
    \includegraphics[width=\myplotscale]{plot-lambda.pdf}
    \quad
    \includegraphics[width=\myplotscale]{plot-f.pdf}
    \quad
    \includegraphics[width=\myplotscale]{plot-J.pdf}
    \caption{Plots of $\lambda$, $f$, and $J$ with respect to $\theta$. 
    Note that for $\theta \to 0^+$ it holds that $\lambda$ and $f$ tend to $1/4$ and $2\log(2) \approx 1.39$, %respectively,
    while for $\theta \to 1/2^-$ they tend to $0$ and $\log(2)-1 \approx -0.3$, respectively.
    The function $J$ tends to $+\infty$ for both these limits.
    }
    \label{fig:lambda-f-J}
\end{figure}

\begin{remark}[Number of vertices]\label{rem_vertices}
For unicellular maps, Euler's formula states that the number of vertices $v \equiv v_n$ is given by $v = n + 1 - 2g$. 
Therefore, the range of our main theorem is equivalent to $\frac{v}{\log n} \to \infty$.
\end{remark}

\begin{remark}[Genus zero]\label{rem_g0}
    %% For theta close to 0, lambda = 1/4 - 3/4*theta + 9/20*theta^2 + 27/700*theta^3 + ...
    For $g=0$, one needs to take the continuous limit $g\rightarrow 0$ in the right-hand side of~\eqref{eq_main_asympto}. This gives
$\E(n,0)\sim \frac{4^n}{n^{3/2}\sqrt{\pi}},$
which is consistent with the asymptotics of the Catalan number $\frac{1}{n+1}\binom{2n}{n}$ that is the closed-form solution of $E(n,0)$ (unicellular maps of genus $0$). 
\end{remark}

\Cref{thm_main} has already been proved for $g\in[\eps n,(1/2-\eps)n]$ \cite{linear-genus} and $g=O(n^{1/3})$ \cite{meso-genus}, but both works rely heavily on the combinatorics of the model, whereas in this work, we only use the Harer--Zagier recurrence formula~\eqref{eq:recurrence} with the initial conditions~\eqref{eq_bdy}, and we can forget everything about where the numbers $\E(n,g)$ come from.

\begin{remark}%[Other regimes]
    In this extended abstract, we focus on the regime $\largev$.
    In \Cref{sec_regimes} we discuss the necessary changes for 
    the regime(s) 
    $n-2g=O(\log n)$.
\end{remark}

\section{Informal proof ideas: asymptotic guess and check}\label{sec_guess}

This section is written in an informal tone. The idea is to give the main ingredients of the proof, and how to come up with them. 
In particular, we explain our heuristics for guessing the asymptotic formula. 
The goal is to provide a sort of recipe that one can apply to find bivariate asymptotics if given a recurrence similar to~\eqref{eq:recurrence} with initial conditions but no other information (we discuss the generality of our approach in \Cref{sec_generality}).


If we were able to guess explicit formulas $\Omega(n,g)$ that satisfied the same recurrence~\eqref{eq:recurrence} as the numbers $E(n,g)$, such that $\Omega(0,0)=E(0,0)$, then we would have $E(n,g)=\Omega(n,g)$ for all $n$ and $g$, and we would have an explicit formula for all numbers $E(n,g)$. 
This is of course not possible as it stands, but we will use an ``asymptotic version'' of this approach that we describe now.

\bigskip

\noindent\textbf{Goal:} Find \emph{explicit} numbers $\Omega(n,g)$ satisfying
% \begin{flalign*}
% \Omega(n,0)&\sim \E(n,0) \quad \text{ as $n\rightarrow \infty$},&&&&\textbf{``asymptotic initial condition''}\\
% (n+1)\Omega(n,g)&\approx 2(2n-1)\Omega(n-1,g)\\&\quad +(n-1)(2n-1)(2n-3)\Omega(n-2,g-1).&&&&\textbf{``asymptotic recurrence''}
% \end{flalign*}
\begin{enumerate}
    \item \textbf{Asymptotic initial condition} (for $n\rightarrow \infty$): 
    \[     
        \Omega(n,0)\sim \E(n,0)
    \]
    %
    \item \textbf{Asymptotic recurrence} (with a well-chosen definition of ``$\approx$''):
    \begin{align*}        
        (n+1)\Omega(n,g)&\approx 2(2n-1)\Omega(n-1,g) + (n-1)(2n-1)(2n-3)\Omega(n-2,g-1)
    \end{align*}
\end{enumerate}



\subsection{Heuristic guessing}

We discuss now how we guess a bivariate asymptotic form $\Omega(n,g)$ for $E(n,g)$, as our proof will then revolve around the analysis of the ratios $E(n,g)/\Omega(n,g)$. 
First we use the recurrence to compute the exact values $E(n,g)$ for $n\leq 1000$. Then, using standard, univariate empirical analysis (see \cite{guttmannser} and references therein), we derive precise asymptotic estimates for subsequences, e.g.,
\[\E(3g,g)\sim c_{1}g^{2g-2}\mu_{1}^{g}~~~~~\text{and}~~~~~\E(4g,g)\sim c_{2}g^{2g-2}\mu_{2}^{g},\]
with constants $c_{1}\approx 0.042124$ and $c_{2}\approx0.033183$, and growth rates $\mu_{1}\approx 117.923$ and $\mu_{2}\approx 1633.26$. Analysing $\E(n,\theta n)$ for different fixed, rational values of $\theta$ yields similar results, which leads us to predict that
\[\E(n,\theta n)\sim n^{2\theta n-2}e^{nf(\theta)}{J}\left(\theta\right),\]
for some functions $f$ and $J$. The next step is to guess the function $f$. 
To do this, we substitute the approximate expression above for $\E$ into \eqref{eq:recurrence} with $g=\theta n$, divide by the left-hand side, and then take the limit $n\to\infty$. This yields the differential equation
\[1=4e^{-2\theta-f(\theta)+\theta f'(\theta)}+4e^{-4\theta-2f(\theta)+2\theta f'(\theta)-f'(\theta)},\]
which can be exactly solved to give our expression for $f(\theta)$. To estimate $J(\theta)$ we again substitute our approximate expression for $\E$ into \eqref{eq:recurrence}, but this time we analyse the $n^{-1}$ term in the resulting equation. Doing so yields the equation
\[\frac{J'(\theta)}{J(\theta)}=\frac{4\kappa\lambda(\theta)-2\kappa+6\lambda(\theta)-4}{4\theta\lambda(\theta)-2\theta-4\lambda(\theta)+1}-\frac{4\theta\lambda(\theta)}{(4\theta\lambda(\theta)-2\theta-4\lambda(\theta)+1)^2}+f'(\theta)+2,\]
which can be solved up to a constant term. Finally, we multiply the expression by $\frac{1}{2\sqrt{\pi}} \frac{\sqrt{g}(g/e)^g}{g!}$ so that it holds for fixed $g$, which gives our estimate \eqref{eq_main_asympto}. One can check that this is precisely consistent with our asymptotic estimates of $\E(3g,g)$ and $\E(4g,g)$. 


\subsection{Modeling by random walks}\label{sec_RW}


We will now present our \emph{random walk method}. 
%
Iterating the Harer--Zagier recurrence formula, we get
\begin{align}\label{eq:sum_walks}
    \E(n,g)&=\frac{2(2n-1)}{n+1}\E(n-1,g)+\frac{(n-1)(2n-1)(2n-3)}{n+1}\E(n-2,g-1)\notag\\
&=\sum_{\substack{\mathbf{p}\in\text{paths} \\ (n,g) \to (0,0)} }\prod_{\text{step}\in \mathbf{p}}\text{weight}(\text{step}),
\end{align}
where the sum spans over all paths from $(n,g)$ to $(0,0)$ with steps $(-1,0)$ and $(-2,-1)$. 
Therein, the weight of a path is the product of the weights of its steps, 
and the \emph{space-dependent} weights of the steps are defined as follows:
\begin{align*}
    \text{step} \quad (n,g)&\rightarrow (n-1,g) &&\text{has weight }  \alpha = \frac{2(2n-1)}{n+1},\\
    \text{step} \quad (n,g)&\rightarrow (n-2,g-1) &&\text{has weight } \beta = \frac{(n-1)(2n-1)(2n-3)}{n+1}.
\end{align*}
Unfortunately, it is not immediately clear how to determine the asymptotics from this weighted walk model either. 
To facilitate this task, we repeat the analysis above this time on the ratios $\frac{\E(n,g)}{\Omega(n,g)}$, where $\Omega(n,g)$ is our explicit asymptotic approximation for $E(n,g)$. 
Then the recursion~\eqref{eq:recurrence} for $E(n,g)$ turns into a recursion for 
%the ratios 
$\frac{\E(n,g)}{\Omega(n,g)}$, which corresponds to a new weighted walk model with the same steps but the new weights
%To estimate $\E(n,g)$ asymptotically, a first idea would be to figure out which paths contribute the most in the sum of~\eqref{eq:sum_walks}. In other words, this amounts to understanding the behaviour of the random walk with the following transition probabilities:
%\begin{flalign*}
%    &(n,g)\rightarrow (n-1,g) &&&&\text{with probability} \quad \frac{2(2n-1)}{n+1}\frac{\E(n-1,g)}{\E(n,g)}\\
%     &(n,g)\rightarrow (n-2,g-1) &&&&\text{with probability}\quad \frac{(n-1)(2n-1)(2n-3)}{n+1}\frac{\E(n-2,g-1)}{\E(n,g)}
%\end{flalign*}
%Unfortunately, this is not possible, since we do not know the numbers $\E(n,g)$ ! Instead, we will study a very similar random walk whose transition probabilities are roughly\footnote{in the sense that, by the "asymptotic recurrence", these two quantities do not sum to exactly one, but almost} given by
\begin{align*}
    \alpha &= \frac{2(2n-1)}{n+1} \cdot \frac{\Omega(n-1,g)}{\Omega(n,g)}
    &&\text{and}& 
    \beta &=\frac{(n-1)(2n-1)(2n-3)}{n+1} \cdot \frac{\Omega(n-2,g-1)}{\Omega(n,g)}.
\end{align*}
The advantage of this new model is that these weights sum to approximately $1$, so we have approximately a classical random walk model. The key observation now is that the ratio $\frac{E(n,g)}{\Omega(n,g)}$ interpreted as in~\eqref{eq:sum_walks} is approximately the probability that a walk defined by this model ends at $(0,0)$, which is approximately $1$. In order to prove $\frac{E(n,g)}{\Omega(n,g)}\sim 1$, we just need to be precise about what we mean by ``approximately'' in each case.

\section{Elements of the proof}
\label{sec_proof}

In this section, we sketch the proof of our main theorem. We write it in a concise way and omit some details, but all the main parts are given, except for the proofs of \Cref{prop_alpha_beta} and Properties~\eqref{eq_lower_bd_s_bad_wall},~\eqref{eq_ineq_s_gnus_1}, and~\eqref{eq_small_s}. These involve a careful analysis of the asymptotics of $\Omega(n,g)$ (especially in the regimes $g/n\rightarrow 0$ and $g/n\rightarrow 1/2$), which is rather technical but only involves explicit functions.
% \todobl{I try to convey the idea that's it's not so easy but it's "just" studying functions we have formulas for.}

\subsection{Setup: the numbers \texorpdfstring{$\Omega(n,g)$}{Omega(n,g)}}

For all integers $n\geq 0$ and $g\leq (n-1)/2$ we define
\begin{align}\label{eq_def_omega}
    \Omega(n,g)&:=\frac{1}{2\sqrt{\pi}} \frac{\sqrt{g}(g/e)^g}{g!}n^{2g-2}e^{nf(\frac{g}{n})}{J}\left(\frac{g}{n}\right)K(n-2g)\color{red}{}\color{black} \qquad \text{ with } \\
    K(x)&:=\frac{\sqrt{2\pi} \, x^{x+1}}{e^{x} \, \Gamma(x+3/2)}
    % \rightarrow 1\quad\quad\text{as $x\to\infty$},
    \notag
\end{align}
where $f$ and $J$ are the same as in \Cref{thm_main} (recall \Cref{rem_g0} for $g=0$).
Note that $K(x) \rightarrow 1$ as $x\to\infty$.
Now, define 
\begin{align*}
Q(n,g)&:=\frac{\E(n,g)}{\Omega(n,g)},\\
    \alpha(n,g) &:= \frac{2(2n-1)}{n+1} \cdot \frac{\Omega(n-1,g)}{\Omega(n,g)},\\
    \beta(n,g) &:= \frac{(n-1)(2n-1)(2n-3)}{n+1} \cdot \frac{\Omega(n-2,g-1)}{\Omega(n,g)}.
\end{align*}
Then the Harer--Zagier recursion~\eqref{eq:recurrence} can be rewritten as
\begin{equation}\label{eq_alpha_beta_Q}
    Q(n,g)=\alpha(n,g)Q(n-1,g)+\beta(n,g)Q(n-2,g-1),
\end{equation}
and \Cref{thm_main} is equivalent to showing that, for $\nto$ and $\largev$, we have $Q(n,g)\sim 1$.
From the Harer--Zagier recursion~\eqref{eq:recurrence} we directly deduce
\begin{align*}
    E(n,0)&=\frac{1}{n+1}\binom{2n}{n} &
    & \text{ and } &
    E(2n+1,n)\sim 2\sqrt{2}\left(\frac{4n}{e}\right)^{2n}\log(n).
\end{align*}
%
Of course, the formula for $E(n,0)$ was already known (see Remark \ref{rem_g0}). In the words of \Cref{sec_guess}, the asymptotic initial condition is easily checked by combining this expression for $E(n,0)$ with \eqref{eq_def_omega}:
\begin{equation}\label{eq_Q_good_bdy}
    Q(n,0)\rightarrow 1 \quad\text{as \nto}.
\end{equation}
Similarly we have the following useful convergence result that we will need later:
\begin{equation}\label{eq_Q_bad_bdy}
    Q(2n+1,n)\sim\frac{3\pi}{2\sqrt{2}}\log(n)^{-1/2}\rightarrow 0 \quad\quad\text{as \nto}.
\end{equation}
The crucial result is the asymptotic recurrence:
\begin{proposition}\label{prop_alpha_beta}
As $\nto$, uniformly in $0<g<(n-1)/2$,
\[\alpha(n,g)+\beta(n,g)=1+O\left((n-g)^{-1}\log^{-2}(n-g)\right).\]
\end{proposition}
The key property is that the error term is \textbf{summable}, and this is why we had to add the seemingly useless factor $K(n-2g)$ in the definition of $\Omega(n,g)$. Note that \Cref{prop_alpha_beta} doesn't hold in the ``extreme cases'' $g=0$, $n=2g$, and $n=2g+1$.


\subsection{Setup: the random walk}\label{sec_setupRW}
Given $n,g$ we define the random walk $(N_k,G_k)_{k\geq 0}$ as follows:
\begin{itemize}
    \item $(N_0,G_0)=(n,g)$
    \item The walk is stopped as soon as $N_k=2G_k-1$ or $G_k=0$. In other words, we stop once \Cref{prop_alpha_beta} no longer holds. We call $\tau=\tau(n,g)$ the stopping time.
    \item At step $0\leq k<\tau$, we have the following transitions\footnote{The transitions have independent sources of randomness for each step.}:
    \begin{align*}
    &(N_{k+1},G_{k+1})= (N_{k}-1,G_{k}) &\text{with probability} &\quad \frac{\alpha(N_k,G_k)}{\alpha(N_k,G_k)+\beta(N_k,G_k)},\\
    &(N_{k+1},G_{k+1})= (N_{k}-2,G_{k}-1)&\text{with probability} &\quad \frac{\beta(N_k,G_k)}{\alpha(N_k,G_k)+\beta(N_k,G_k)}.
    \end{align*}
\end{itemize}

Notice that $M_k:=N_k-G_k > 0$ is a deterministic quantity, indeed $M_k=M_0-k = n-g-k$. This fact, along with~\eqref{eq_alpha_beta_Q} and \Cref{prop_alpha_beta} shows that $Q(N_k,G_k)$ does not change much in expected value. To make this precise, we define the error terms
\begin{align*}r^{+}(k)&:=\prod_{j=k+1}^{\infty}\max(\{\alpha(n,g)+\beta(n,g):n-g=j,0<g<(n-1)/2\}),\\
r^{-}(k)&:=\prod_{j=k+1}^{\infty}\min(\{\alpha(n,g)+\beta(n,g):n-g=j,0<g<(n-1)/2\}),
\end{align*}
which due to \Cref{prop_alpha_beta} satisfy $r^{-}(k),r^{+}(k)\in(0,\infty)$ and $r^{-}(k),r^{+}(k)\to 1$ as $k\to\infty$. Moreover, we have the following
\begin{proposition}[Conserved quantity]\label{prop_E(Q)}Let $Q_k:=Q(N_k,G_k)$, then
\[\mathbb{E}(r^{-}(M_{\tau})Q_\tau) \leq Q_0 \leq \mathbb{E}(r^{+}(M_{\tau})Q_\tau ).\]
\end{proposition}

\subsection{Behaviour of the walk and asymptotics}

In this section, we show that, with high probability, the random walk will hit the $g=0$ axis, \emph{far away} from the origin.

\begin{proposition}\label{prop_typ_behaviour}
    For any fixed $L>0$, we have, as $\nto$,
    \[\mathbb{P}(G_\tau=0\text{ and }N_{\tau}>L)=1-o(1).\]
\end{proposition}
This immediately implies our main result:
\begin{proof}[Proof of \Cref{thm_main} assuming \Cref{prop_typ_behaviour}]
    By~\eqref{eq_Q_good_bdy} and~\eqref{eq_Q_bad_bdy}, we can bound $Q(n,0)$ and $Q(2n+1,n)$ by a constant $C$ for all $n$, and therefore $Q_\tau\leq C$ deterministically. Hence, by \Cref{prop_typ_behaviour}, it holds that
    \[\mathbb{E}(r^{\pm}(M_{\tau})Q_\tau)=\mathbb{E}(r^{\pm}(M_{\tau})Q_\tau \mid G_\tau=0\text{ and }N_{\tau}>L)+o(1).\]
    %\[\mathbb{P}(N_{\tau}=2G_\tau+1)\mathbb{E}(Q_\tau|N_{\tau}=2G_\tau+1)=o(1)\quad\text{and} \quad \mathbb{P}(N_{\tau}<\infty)\mathbb{E}(Q_\tau|N_{\tau}=\infty)=o(1), \]
    Hence, by \Cref{prop_E(Q)}, we have
    \[Q(n,g)=Q_0\leq\mathbb{E}(r^{+}(M_{\tau})Q_\tau)\leq \max_{N>L}(r^{+}(N)Q(N,0))+o(1).\]
    Note that this holds for any $L$, and by~\eqref{eq_Q_good_bdy} we have $r^{+}(N)Q(N,0)\to 1$ as $N\to\infty$. Moreover, we have a similar lower bound on $Q(n,g)$ using $r^{-}(N)Q(N,0)$. Combining these facts yields $Q(n,g)= 1+o(1)$, which completes the proof.
\end{proof}

It remains to show \Cref{prop_typ_behaviour}. For that, we introduce another conserved quantity:
\[s(n,g):=\frac{\Omega(n,g-1)}{\Omega(n,g)}\quad \text{ with } s(n,0)=0.\]

\begin{lemma}[Conserved quantity, bis]\label{lem_E(S)}
Let $S_k:=s(N_k,G_k)$, then
\[\mathbb{E}(S_{\tau-1})=\bigO{S_0}.\]
\end{lemma}
\begin{proof}
We immediately have the exact equality
\[\frac{\alpha(n,g)s(n-1,g)+\beta(n,g)s(n-2,g-1)}{s(n,g)}=\alpha(n,g-1)+\beta(n,g-1),\]
and the proof is similar to that of \Cref{prop_E(Q)}, noting that there is a uniform bound on the error terms $r^{+}$ and $r^{-}$.
\end{proof}

Finally, we need the following properties of $s(n,g)$, which follow from the definitions by some involved calculations:
\begin{align}
   & \text{There exists a constant $c>0$ such that } s(2g+2,g)>c \text{ for all }g\geq 1; \label{eq_lower_bd_s_bad_wall}\\
   & s(n,1)>0 \text{ for all }n\geq 1; \label{eq_ineq_s_gnus_1}\\
   &s(n,g)\rightarrow 0 \text{ as }\nto \text{ with }\largev. \label{eq_small_s}
\end{align}

We can finally prove the main result of this section

\begin{proof}[Proof of \Cref{prop_typ_behaviour}]
    By \Cref{lem_E(S)} and~\eqref{eq_small_s}, one has, as $\nto$ with $\largev$
\[\P(N_\tau=2G_\tau+1)\mathbb{E}(S_{\tau-1} \mid N_\tau=2G_\tau+1)=\bigO{S_0}=o(1).\]
But $\mathbb{E}(S_{\tau-1} \mid N_\tau=2G_\tau+1) = \mathbb{E}(s(2G_\tau+2,G_\tau) \mid N_\tau=2G_\tau+1)>c>0$ by~\eqref{eq_lower_bd_s_bad_wall}, hence 
\begin{equation}\label{eq_XX}
    \P(N_\tau=2G_\tau+1)=o(1).
\end{equation}

Now, fix a constant $L$. By the same argument
\[\P(N_\tau\leq L\text{ and }G_\tau=0)\mathbb{E}(S_{\tau-1} \mid N_\tau\leq L\text{ and }G_\tau=0)=o(1).\]
But $\mathbb{E}(S_{\tau-1} \mid N_\tau\leq L\text{ and }G_\tau=0)\geq \min_{1\leq j\leq L+1}s(j,1)>0$ by~\eqref{eq_ineq_s_gnus_1}, hence
\begin{equation}\label{eq_YY}
   \P(N_\tau\leq L\text{ and }G_\tau=0)=o(1).
\end{equation}
\Cref{eq_XX,eq_YY} imply the result.
\end{proof}


\section{Discussion}\label{sec_discussion}

\subsection{Other regimes}\label{sec_regimes}



In this extended abstract, we presented the regime $\largev$, the other regimes (i.e., when $n-2g=O(\log n)$) will be tackled in the full version. The strategy for the regime $n-2g=o(\log n)$ is similar: a random walk method (with a slightly different definition of $\Omega(n,g)$), that this time hits the $n=2g$ axis almost surely. Finally, for the regime $n-2g = \Theta(\log n)$, we can use standard saddle point asymptotic methods (as done for instance in~\cite{Gao}) using either an explicit expression for the generating series, or a more general results on linear differential equations (see~\cite[Theorem~VIII.4]{flajolet}).  

\subsection{Other works about enumeration and random walks}

Several other works\footnote{This list is most probably not exhaustive.} study links between recurrences, random walks, and enumeration:
\begin{itemize}
    \item In~\cite{compacted-tree} and later works, the first, second, and last author studied the asymptotic enumeration of a family of so-called compacted trees using a bivariate recurrence, also interpreted as space-dependent weighted walks as in this work. However, the walk there may leave the boundary, and the asymptotic initial condition there was unknown. Thus, no asymptotic equality but a $\Theta$-result was given there, where a stretched exponential term appeared.
    The same method was later applied to solve the asymptotic enumeration of families of minimal DFAs, Young tableaux~\cite{banderier2021walls}, and phylogenetic networks~\cite{fuchs2021phylo}, always showing similar behaviour. 
    \item In~\cite{Agg} and two other works, large genus asymptotics of intersection numbers (a geometric quantity of interest) are obtained by ``comparing the coefficients in [some recursive] relations with the jump probabilities of a certain asymmetric simple random walk'';
    \item In~\cite{FlinChassaing}, the authors study the typical path of the random walk defined by well-known linear recurrences, such as Pascal's triangle, and prove a scaling limit. 
\end{itemize}

As far as we understand, each of these three works (and the present one) studies a different setting. It is tempting (and rather ambitious) to ask for a general framework for ``asymptotics via random walks''. We conclude by stating how far we think our method applies, and the next steps we wish to take in this research programme. 




\subsection{Generality of the method}\label{sec_generality}

In this paper, we presented bivariate asymptotics in one concrete case, but our method should apply to a larger class of recurrences associated to bivariate generating functions satisfying a linear ODE. This is in contrast with the ACSV approach, which currently only applies to a restricted class of algebraic generating functions.
More precisely, our approach could work for any numbers $E(n,k)$
with boundary conditions
\[E(0,0)=1 \qquad \text{ and } \qquad E(n,k)=0\text{ if } n<0 \text{ or }k<0,\]
which satisfy a recurrence of the type
\begin{align}\label{eq_generalized}
    A(n)E(n,k)=\sum_{i=1}^C\sum_{j=0}^D P_{i,j}(n)E(n-i,k-j),
\end{align}
where $C$ and $D$ are nonnegative integers, while $A$ and the $P_{i,j}$'s are polynomials. As long as $E(n, \theta n)$ behaves like $n^{c\theta n+d} \exp(n f(\theta))J(\theta)$ for some $c,d\in\mathbb{R}$ and some functions $f(\theta),J(\theta)$, \Cref{eq_generalized} gives a differential equation for $f(\theta)$ as in \Cref{sec_guess}, whose solution gives an estimate of $E(n, k)$. Then a differential equation for $J(\theta)$ could be obtained using the subdominant term as in our case. Proving the accuracy of such an estimate with our random walk method then depends primarily on the existence of a result analogous to \Cref{prop_alpha_beta}. In principal this should not be a problem, as such a result will necessarily hold if the asymptotic estimate is sufficiently precise.

In particular, we are looking into applying our method in other contexts where similar bivariate recurrences arise: to estimate the probability that, given $n$ random points in a triangle, $k$ of them lie on the convex hull (Anna Gusakova, private communication), or to estimate the probability that, in a model of colliding bullets, $k$ out of $n$ survive~\cite{bullet}.


\subsection{Outlook}\label{sec_further}

Our next goal is to go beyond linear recurrences. In fact several combinatorial/geometric families of importance (maps, Hurwitz numbers, constellations, etc.) satisfy \emph{quadratic} recurrences~\cite{DYZ,KP-triangulation} coming from integrable systems such as the {KP hierarchy}. We are working on extending our methods to obtain large genus asymptotics for these families.

In another direction, we have been made aware of a problem inspired by population genetics which models the probability of extinction of a species by a random walk in 2D with weighted steps~\cite{flower}. Our method allows us to conjecture the bivariate asymptotics for these probabilities, and we are trying to prove this conjecture.

Finally, we are working on a variation of our method that applies to recurrences with a \emph{bouncy wall}, where the sum in \eqref{eq_generalized} also allows $j<0$ as in \cite{compacted-tree}, meaning that the walks analogous to those defined in \Cref{sec_setupRW} can leave the $x$-axis.
In this case we expect to be able to determine the asymptotics up to some unknown universal constant.

\printbibliography

\end{document}
