\documentclass[12pt]{article} \usepackage{e-jc} \specs{P1.17}{23(1)}{2016} \usepackage{amsmath,ifthen, amsfonts, amssymb, srcltx, amsopn, textcomp,amsthm} \usepackage{hyperref} \usepackage{graphicx} %\usepackage{txfonts} \usepackage{tikz} \newcommand\tikze[1]{\pgfmathparse{#1}\pgfmathprintnumber{\pgfmathresult}} \usetikzlibrary{calc} \usetikzlibrary{decorations.pathmorphing} \usepackage[small]{caption} %%%%%%%%%%%%%%%FLOAT ADJUSTMENT%%%%%%%%%% \renewcommand{\abovecaptionskip}{.4mm} \renewcommand{\belowcaptionskip}{.1mm} \newcommand{\showcomments}{yes} \renewcommand{\showcomments}{no} \newcommand{\hidetodo}[1] {\ifthenelse{\equal{\showcomments}{yes}}% % then end comment {#1} % else do nothing } \newsavebox{\commentbox} \newenvironment{com}% % begin comment {\ifthenelse{\equal{\showcomments}{yes}}% % then begin comment in margin {\footnotemark \begin{lrbox}{\commentbox} \begin{minipage}[t]{1.25in}\raggedright\sffamily\tiny \footnotemark[\arabic{footnote}]} % else eat contents of the environment {\begin{lrbox}{\commentbox}}}% % end comment {\ifthenelse{\equal{\showcomments}{yes}}% % then end comment {\end{minipage}\end{lrbox}\marginpar{\usebox{\commentbox}}} % else finish eating {\end{lrbox}}} \newtheorem{thm}{Theorem}[section] \newtheorem{lem}[thm]{Lemma} \newtheorem{mainlem}[thm]{Main Lemma} \newtheorem{cor}[thm]{Corollary} \newtheorem{conj}[thm]{Conjecture} \newtheorem{prop}[thm]{Proposition} \newtheorem*{quasithm}{Quasi-Theorem} \newtheorem*{claim}{Claim} \newtheorem*{mainA}{Theorem~\ref{thm:half}} \newtheorem*{mainB}{Theorem B} \newtheorem*{thmM}{C6-Sample} \newtheorem*{thmD}{B6-Sample} \newtheorem*{Nrem}{Remark} \theoremstyle{definition} \newtheorem{defn}[thm]{Definition} \newtheorem{rem}[thm]{Remark} \newtheorem{exmp}[thm]{Example} \newtheorem{warning}[thm]{Warning} \newtheorem{history}[thm]{Historical Note} \newtheorem{notation}[thm]{Notation} \newtheorem{conv}[thm]{Convention} \newtheorem{lede}[thm]{Lemma-Definition} \newtheorem{openprob}[thm]{Open Problem} \newtheorem{prob}[thm]{Problem} \newtheorem{const}[thm]{Construction} \newtheorem{cond}[thm]{Conditions} \newcommand{\neb}{\mathcal N} \DeclareMathOperator{\dimension}{dim} \DeclareMathOperator{\kernel}{ker} \DeclareMathOperator{\image}{image} \DeclareMathOperator{\rank}{rank} \DeclareMathOperator{\mrank}{\widetilde{rank}} \DeclareMathOperator{\Aut}{Aut} \DeclareMathOperator{\Out}{Out} \DeclareMathOperator{\valence}{valence} \DeclareMathOperator{\link}{link} \DeclareMathOperator{\cstar}{Star} \DeclareMathOperator{\stab}{Stab} \DeclareMathOperator{\Hom}{Hom} \DeclareMathOperator{\GL}{GL} \DeclareMathOperator{\height}{Height} \DeclareMathOperator{\grade}{Grade} \DeclareMathOperator{\peak}{peak} \newcommand\card[1]{\left|#1\right|} \newcommand{\semidirect}{\ensuremath{\rtimes}} \newcommand{\homology}{\ensuremath{{\sf{H}}}} \newcommand{\walk}{\ensuremath{w}} \newcommand{\dist}{\textup{\textsf{d}}} \newcommand{\scname}[1]{\text{\sf #1}} \newcommand{\area}{\scname{Area}} \newcommand{\curvature}{{\ensuremath{\kappa}}} \newcommand{\field}[1]{\mathbb{#1}} \newcommand{\integers}{\ensuremath{\field{Z}}} \newcommand{\rationals}{\ensuremath{\field{Q}}} \newcommand{\naturals}{\ensuremath{\field{N}}} \newcommand{\reals}{\ensuremath{\field{R}}} \newcommand{\complexes}{\ensuremath{\field{C}}} \newcommand{\Euclidean}{\ensuremath{\field{E}}} \newcommand{\hyperbolic}{\ensuremath{\field{H}}} \newcommand{\truncated}{\ensuremath{\field{T}}} \DeclareMathOperator{\Isom}{Isom} \DeclareMathOperator{\Centralizer}{Cent} \DeclareMathOperator{\Commensurator}{Comm} \newcommand{\length} [1] {{\ensuremath \vert\vert{#1}\vert\vert}} \newcommand{\boundary} {{\ensuremath \partial}} \newcommand{\fold}{\breve} \newcommand{\euler}{\chi} \newcommand{\subwords}[1]{\text{\textsl{subwords}}(#1)} \newcommand{\interior} [1] {{\ensuremath \text{\rm Int}(#1) }} \newcommand{\size}[1]{\ensuremath{\vert #1 \vert}} \newcommand{\systole}[1]{\ensuremath{\vert\!\vert #1 \vert\!\vert}} \newcommand{\nclose}[1]{\ensuremath{\langle\!\langle#1\rangle\!\rangle}} \newcommand{\p}{\textup{\textsf{p}}} \DeclareMathOperator{\order}{order} \newcommand{\VH}{\mathcal V \mathcal H} \newcommand{\artin}{\mathcal ART} \newcommand{\canon}[2]{\ensuremath{{{\sf C}({#1}\rightarrow {#2})}}} \newcommand{\elev}{\breve} \newcommand{\PROJ}[3]{\textsf{\walkProj}_{{#1}}{({#2}}\rightarrow {{#3}})} \newcommand{\bowwow}[1]{\ensuremath{\stackrel{\bowtie}{#1}}} \renewcommand{\angle}{\sphericalangle} \newcommand{\CC}{\#_c} \newcommand{\SSS}{\#_s} \newcommand{\HYP}{\mathcal H} \DeclareMathOperator{\diagonal}{Diag} \DeclareMathOperator{\nullity}{Nullity} \DeclareMathOperator{\intersector}{Intersector} \DeclareMathOperator{\IntOsc}{\text{Osculator}} \DeclareMathOperator{\Osc}{\text{Osc}} \DeclareMathOperator{\Crosses}{\text{Crosses}} \DeclareMathOperator{\nonintersector}{\text{Nonintersector}} \DeclareMathOperator{\pseudostabilizer}{\text{Pseudostabilizer}} \DeclareMathOperator{\diameter}{\text{diam}} \DeclareMathOperator{\deficiency}{\text{defect}} \DeclareMathOperator{\Comp}{\text{\sf Comp}} \DeclareMathOperator{\girth}{girth} \newcommand{\bonus}{$\circledast$\ } \newcommand{\flub}{\circledR: \ } \newcommand{\cev}[1]{\reflectbox{\ensuremath{\vec{\reflectbox{\ensuremath{#1}}}}}} \newcommand{\MWS}[1]{(X_{#1},\mathcal W_{#1}, \mathcal B_{#1},\mu_{#1})} \newcommand{\properss}{\mathcal{PSS}} \newcommand{\edges}{\mathcal{E}} \newcommand{\vertices}{\mathcal{V}} %%%%%%%%%%%%%DIMENSIONS%%%%%%%%%%%%% %\setlength{\textwidth}{5.5in} %\setlength{\textheight}{8.3in} %\hoffset=-.27in %%%%%\voffset=.15 in %%%%%%%%%%%%%DIMENSIONS%%%%%%%%%%%%% \begin{document} \title{\bf A note on maxima in random walks} \author{Joseph Helfer\\ \small Department of Mathematics\\[-0.8ex] \small Stanford Univ.\\[-0.8ex] \small Stanford, CA 94305, U.S.A. \\ \small\tt joj@stanford.edu\\ \and Daniel T. Wise\thanks{Research supported by NSERC}\\ \small Dept. of Math. \& Stats.\\[-0.8ex] \small McGill Univ.\\[-0.8ex] \small Montreal, QC, Canada H3A 0B9\\ \small\tt wise@math.mcgill.ca} %\subjclass[2010]{60G50, 05A19} \date{\dateline{Jun 13, 2015}{Jan 13, 2016}{Jan 22, 2016}\\ \small Mathematics Subject Classifications: 60G50, 05A19} %\keywords{} \maketitle \begin{com} {\bf \normalsize COMMENTS\\} ARE\\ SHOWING!\\ \end{com} \begin{abstract} We give a combinatorial proof that a random walk attains a unique maximum with probability at least $1/2$. For closed random walks with uniform step size, we recover Dwass's count of the number of length~$\ell$ walks attaining the maximum exactly $k$~times. We also show that the probability that there is both a unique maximum and a unique minimum is asymptotically equal to $\frac14$ and that the probability that a Dyck word has a unique minimum is asymptotically $\frac12$. \bigskip\noindent \textbf{Keywords:} Random walk, Dyck Words, Catalan Numbers \end{abstract} \section{Introduction} A \emph{length~$\ell$ walk} is a sequence $\walk:\{1,\ldots, \ell\} \rightarrow \{\pm 1\}$. % The \emph{trajectory} of $\walk$ is the sequence $\bar\walk:\{0,\ldots, \ell\} \rightarrow \integers$ defined by $\bar \walk(j)=\sum_{i=1}^j \walk(i)$. We define $\max(\walk) = \sup\{\bar \walk(j) : 0\leq j \leq \ell \}$. % The length~$\ell$ walk $\walk$ is \emph{closed} if $\bar \walk(\ell)=0$. Let $\mathcal C(n)$ denote the set of length~$2n$ closed walks and let $\mathcal M(n)\subset\mathcal C(n)$ denote the subset consisting of those walks $\walk$ for which there is a unique $i\in\{1,\ldots,2n\}$ such that $\bar \walk(i)=\max(\walk)$. The paper centers around a combinatorial proof of the following theorem which was first proven by Dwass in \cite{Dwass67}: \begin{mainA} $\card{\mathcal M(n)}=\frac12\card{\mathcal C(n)}$ for each $n\geq 1$. \end{mainA} In \cite{Dwass67}, this is proven by a method that computes the probabilities of events in finite random walks by relating them to events in infinite random walks for which probabilities are more readily computed. This is a general analytic method used to compute a large number of quantities including $\mathcal M(n)$ as well as the more general $\mathcal M(n,r)$ which we discuss in Section~\ref{sec:multiple}. As is often the case, a combinatorial proof offers other intuition and insight. In this case, we will see that our method generalizes to certain cases not amenable to Dwass's method. In Section~\ref{sec:dyck} we give a first proof of Dwass's result, which uses a method we will employ fundamentally in the text. A second more transparent proof is give in Section~\ref{sec:dyck unimax}. This second proof uses that the number of Dyck words is the corresponding Catalan number. % In Section~\ref{sec:multiple} we recover Dwass's stronger result that there are precisely ${2n-r \choose r-1}$ length~$2n$ closed walks attaining their maximum exactly $r$ times. % In Section~\ref{sec:nonuniform} we explain that the combinatorial proof generalizes to show that more general types of finite random walks have probability $\geq \frac12$ of attaining a unique maximum. This conclusion does not assume that the walks are closed and allows an arbitrary distribution of step sizes. % In Section~\ref{sec:minmax} we show that the probability of having both a unique minimum and a unique maximum approaches $\frac14$ as the length of a uniform closed walk increases. % In Section~\ref{sec:dyck unimax} we show that the probability that a length~$n$ Dyck word has a unique minimum approaches $\frac12$ as $n\to\infty$. \section{Dyck Words and Leads}\label{sec:dyck} A \emph{Dyck word} of length~$2n$ is a closed walk $\walk$ such that $\max(\walk) =0$. Let $\mathcal D(n)$ denote the set of length~$2n$ Dyck words. The number of Dyck words of a given length is the corresponding Catalan number: \begin{thm}\label{thm:counting Dyck words} $\card{\mathcal D(n)}= \frac1{n+1}{2n \choose n}$. \end{thm} The \emph{lead} of $\walk\in \mathcal C(k)$ is the number of values $i\in\{1,\ldots, 2k\}$ with both $\walk(i)>0$ and $\bar \walk(i)>0$. % For $0\leq e\leq k$ let $\mathcal L(k,e) \subset \mathcal C(k)$ be the set of lead~$e$ walks (so that $\mathcal L(k,0)=\mathcal D(k)$). Thus $\mathcal C(k)=\sqcup_{e=0}^k \mathcal L(k,e)$. Since $\card{\mathcal C(n)}={2n\choose n}$, Theorem~\ref{thm:counting Dyck words} follows from the Chung-Feller Theorem which states that $\card{\mathcal L(k,e)}$ is independent of $e$ \cite{ChungFeller49}. Among the many proofs of the Chung-Feller theorem is a bijective explanation given in \cite{BlackwellHodges67,Narayana67} the former of which traced the explanation to \cite{DvoretzkyMotzkin47}. We now recount the bijection: \begin{lem}\label{lem:Bijective Proof} For each $1\leq e \leq k$ there is a bijection $\psi:\mathcal L(k,e-1)\rightarrow \mathcal L(k,e)$. \end{lem} \begin{proof} Let $\walk\in \mathcal L(k,e-1)$. Let $p>0$ be maximal such that $\walk(p)=-1$ and $\bar \walk(p)=-1$. Regard $\walk$ as a string in $\{\pm 1\}$, and express $\walk$ as the concatenation $axb$ where $a$ is the initial length~$p$ subpath and $x$ is a single symbol (which is necessarily $-1$). Define $\psi(\walk)$ to be the sequence corresponding to $bxa$. This lies in $\mathcal L(k, e)$ since $a,xb,bx$ are all closed and the lead of $bx$ is one greater than that of $b$. The map $\psi^{-1}$ is defined by recognizing the decomposition of $\walk\in \mathcal L(k,e)$ as a concatenation $bxa$ by declaring $b$ to be the length~$n$ subword where $n$ is minimal such that $w(n+1)=-1$ and $\bar w(n+1)=0$. \end{proof} \begin{figure} \centering \begin{tikzpicture}[scale=.5] \foreach \y/\z/\s [count=\i] in {1/2/,2/3/, 3/2/dashed,2/3/dashed,3/2/very thick,2/3/dashed, 3/2/,2/1/} \draw [\s] (\i,\y) -- ({\i+1},\z); \foreach \y/\z/\s [count=\i] in {1/2/,2/3/, 3/4/dashed,4/3/very thick,3/2/dashed,2/3/dashed, 3/2/,2/1/} \draw [\s] ({\i+14},\y) -- ({\i+15},\z); \draw [->,decorate,decoration={coil,aspect=0}] (10.5,2) -- (13.5,2); \end{tikzpicture} \caption{Performing a swap} \label{fig:swap} \end{figure} \begin{rem}\label{rem:crucial property} We utilize $\psi: \mathcal L(k,0)\rightarrow \mathcal L(k,1)$ whose crucial property is that $\psi(\walk)\in \mathcal M(k)$ for $\walk\in \mathcal L(k,0)$. \end{rem} \begin{thm}\label{thm:half} $\card{\mathcal M(n)}=\frac12\card{\mathcal C(n)}$ for each $n\geq 1$. \end{thm} \begin{proof} We describe a bijection $\Psi: \mathcal C(n)-\mathcal M(n) \rightarrow \mathcal M(n)$. Let $\walk\in\mathcal C(n)-\mathcal M(n)$. As $\rank(\walk)\geq 2$, we let $a$ be the nontrivial subsequence of $\walk$ with domain $\{p,\ldots, q\} \subset\naturals$ where $p-1,q$ are the minimal and maximal values of $\bar \walk^{-1}(\max(\walk))$. Note that $a\in\mathcal L(q-p+1,0)$ and let $\psi(a)\in\mathcal L(q-p+1,1)$ be as provided by Lemma~\ref{lem:Bijective Proof}. Define $\Psi(\walk)$ to be the sequence obtained from $\walk$ by substituting $\psi(a)$ for $a$ as in Figure~\ref{fig:swap}. Note that $\Psi(\walk)\in\mathcal M(n)$ by Remark~\ref{rem:crucial property}. \end{proof} An alternate proof is given in Section~\ref{sec:dyck unimax}. \section{Counting walks of arbitrary rank}\label{sec:multiple} The \emph{rank} of a walk $\walk$ is $\card{\bar \walk^{-1}(\max(\walk))}$. For $r\geq 1$ let $\mathcal M(n,r) \subset \mathcal C(n)$ denote the subset of rank~$r$ length~$2n$ closed walks. % As $\mathcal M(n,1)=\mathcal M(n)$, Theorem~\ref{thm:half} states that $\card{\mathcal M(n,1)}=\frac12{2n\choose n}={2n-1\choose n-1}$. We now extend this result and count each $\mathcal M(n,r)$: \begin{thm}\label{thm:main} For $n,r\geq 1$ we have $\card{\mathcal M(n,r)} = {2n-r \choose n-1}$. \end{thm} \begin{proof} Let $M(n,r)={2n-r\choose n-1}$. % We first observe that the numbers $M(n,r)$ satisfy the following recursive definition (see Figure~\ref{fig:triangle}). \begin{figure} \centering \begin{tikzpicture}[scale=1] \foreach \y in {0,...,7} \pgfmathparse{div(\y,2)} \foreach \x [evaluate=\x] in {\pgfmathresult,...,\y} \draw ({(-\y / 2 + \x}, {{-\y/sqrt 2}}) node {\tiny M(\tikze{\x+1},\tikze{2*\x+2-\y})}; \end{tikzpicture} \quad \begin{tikzpicture}[scale=1] \foreach \y in {0,...,7} \pgfmathparse{div(\y,2)} \foreach \x [evaluate=\x] in {\pgfmathresult,...,\y} \draw ({(-\y / 2 + \x}, {{-\y/sqrt 2}}) node {\tikze{div(\y!,\x!*(\y-\x)!)}}; \end{tikzpicture} \vspace{5pt} \caption{ The base cases \eqref{eq:basecase} are the entries $1,3,10,35,\ldots$ and the 1 at the top. The identity \eqref{eq:induction} states that an entry in Pascal's triangle is the sum of all the numbers in the diagonal path above it, e.g. 15=10+4+1. } \label{fig:triangle} \end{figure} The base cases are: \begin{equation}\label{eq:basecase} M(n,1)={2n-1\choose n-1}\quad\text{and}\quad M(1,2)=1 \end{equation} The inductive step for $n,r\ge 2$ follows by iterating Pascal's identity: \begin{equation}\label{eq:induction} M(n,r) = \sum_{j=r-1}^n M(n-1,j) \end{equation} We will show that Equations \eqref{eq:basecase} and \eqref{eq:induction} are satisfied with $M(a,b)$ replaced by $\card{\mathcal M(a,b)}$, from which it follows that $\card{\mathcal M(n,r)}=M(n,r)$ for all $n,r\ge1$ as desired. Equation~(\ref{eq:basecase}) is easy as Theorem~\ref{thm:half} asserts that $\card{\mathcal M(n,1)}={2n-1 \choose n-1}$ and obviously $\card{\mathcal M(1,2)}=1$. To verify Equation~\eqref{eq:induction}, for each $n,r\ge 2$, we describe a bijection $\chi_r$ between $\bigcup_{j=r-1}^n\mathcal M(n-1,j)$ and $\mathcal M(n,r)$. Let $\walk\in \bigcup_{j=r-1}^n\mathcal M(n-1,j)$. As $\rank(\walk)\ge r-1$, we may consider the $(r-1)$th maximal peak of $\walk$, counted from the right. As in Figure~\ref{fig:insertpeak}, we insert a peak at this point to obtain a path $\hat w\in\mathcal M(n)$. We then apply the map $\Psi^{-1}:\mathcal M(n)\to\mathcal C(n)\setminus\mathcal M(n)$ to $\hat w$ to obtain $\chi_r(\walk)$. %%%%%%%%%%%% previous position of figure We must show that $\chi_r$ is injective and that its image is $\mathcal M(n,r)$. The former holds since a left-inverse to $\chi_r$ is obtained by first applying $\Psi$ and then removing the single maximal peak. The latter holds by Lemma~\ref{lem:insertpeak}. \end{proof} \begin{lem}\label{lem:insertpeak} Let $n,r\ge 2$, let $w\in\mathcal M(n,r)$ and let $w'$ be obtained by removing the single maximal peak from $\Psi(w)$. Then $\rank(w')\ge r-1$. \end{lem} \begin{proof} The general case follows from the case where $w\in\mathcal D(m)\cap\mathcal M(m,r)$ so that $w'\in\mathcal D(m-1)$. We express $w$ as $axb$ where the length $i$ of $a$ is maximal such that $i,decorate,decoration={coil,aspect=0}] (11.5,2) -- (14.5,2); \draw [->] (5,4) -- (5,3.3); \end{tikzpicture} \caption{Inserting a peak at the third maximal peak from the right} \label{fig:insertpeak} \end{figure} \section{Variable step lengths}\label{sec:nonuniform} In this section we provide a different generalization of Theorem~\ref{thm:half}: we prove that for a random closed walk of variable step size, and with a nonzero fixed number of each type of step, the probability of attaining a unique maximum is at least $\frac12$. \begin{defn} Let $S$ be a finite set. A \emph{length~$\ell$ $S$-walk} $\walk$ is a sequence $\{1,\ldots,\ell\}\to S$. Let $\mathcal W_S(n)$ denote the set of length~$n$ $S$-walks. % Let $v:S\to\mathbb R$. The \emph{$v$-trajectory} of $\walk$ is $\bar \walk_v(j)=\sum_{i=1}^j v(\walk(i))$. % The \emph{$v$-maximum} of $\walk$ is $\max_v(\walk) = \max\{\bar \walk_v(j) : 0\leq j \leq \ell \}$. % Let $\mathcal M_v(n)\subset\mathcal W_S(n)$ denote the subset consisting of those walks $\walk$ for which there is a unique $i\in\{1,\ldots,n\}$ such that $\bar \walk(i)=\max(\walk)$. % The length~$\ell$ $S$-walk $\walk$ is \emph{$v$-closed} if $\bar \walk_v(\ell)=0$. Let $\mathcal D_v(n)\subset\mathcal W_S(n)$ denote the set of length~$N$ $v$-closed $S$-walks with $v$-maximum 0. \end{defn} The proof of Lemma~\ref{lem:Bijective Proof} can be carried over to this more general context: \begin{lem} There is an injection $\psi_v:\mathcal D_v(n)\to\mathcal M_v(n)$ \end{lem} \begin{proof} Let $\walk\in\mathcal D_v(n)$. Let $p0$, and $\bar \walk_v(q+1)=0$. Moreover there can clearly be at most one such representation of $\walk$. The unique pre-image of $\walk$ under $\psi_v$ is then $axb$. \end{proof} \begin{thm}\label{thm:S-half} Let $S$ be a finite set and let $v:S\to\mathbb R$. Then $\card{\mathcal M_v(n)}\ge\frac12\card{\mathcal W_S(n)}$. \end{thm} \begin{proof} The proof is the same as that of Theorem~\ref{thm:half}; we use $\psi_v$ in the same way to define a map $\Psi_v:\mathcal W_S(n)-\mathcal M_v(n)\to\mathcal M_v(n)$ and this is an injection. \end{proof} \begin{rem} Let $X\subset\mathcal W_S(n)$ be any $\Psi_v$-invariant subset. Then by restricting $\Psi_v$ to $X\cap(\mathcal W_S(n)-\mathcal M_v(n))$, we see that $\card{X\cap\mathcal M_v(n)}\ge\frac12\card{X}$. % For example, we could take $X$ to be the set of $v$-closed walks, since $\Psi_v$ takes $v$-closed walks to $v$-closed walks. % Also, note that $\Psi_v$ preserves the cardinality of $S$-fibers in the sense that $\card{\walk^{-1}(s)}=\card{(\Psi_v\walk)^{-1}(s)}$ for each $s\in S$. Hence, we could take $X$ to be the set of walks whose $S$-fibers have some prescribed cardinalities. \end{rem} \begin{rem} We can also consider \emph{weighted} random walks. That is, we let $\mu$ be a probability measure on $S$, and consider the induced measure $\mu$ on $\mathcal W(n)$ that assigns to a walk $\walk$ the probability $\frac1n\sum_{s\in S}\card{\walk^{-1}(s)}\mu(s)$. Theorem~\ref{thm:S-half} also generalizes to this case: with respect to this measure, the measure of $\mathcal M_v(n)$ is at least $\frac12$. This works because the measure is $\Psi_v$-invariant, so \[ \mu_{v}(\mathcal W_S(n)-\mathcal M_v(n))=\hspace{-1cm} \sum_{\walk\in\mathcal W_S(n)-\mathcal M_v(n)}\hspace{-1cm}\mu(\walk)= \sum_{\walk\in\mathcal W_S(n)-\mathcal M_v(n)}\hspace{-1cm}\mu(\Psi(\walk))\le \sum_{w\in\mathcal M_v(n)}\mu(\Psi(\walk))=\mu_{v}(\mathcal M_v(n)) \] \end{rem} \section{Estimating the probability of a unique max and a unique min\label{sec:minmax}} The goal of this section is to prove Theorem~\ref{thm:1/4} which gives a $\frac14$ asymptotic probability that a random walk with uniform step size has both a unique minimum and a unique maximum. The strategy of the proof is to show that there is a dense subset having a partition into four equal cardinality parts lying in: $$ \mathcal M \cap -\mathcal M \ \ \ \ \mathcal M^c \cap -\mathcal M \ \ \ \ \mathcal M \cap (-\mathcal M)^c \ \ \ \ \mathcal M^c \cap (-\mathcal M)^c $$ \begin{defn} Let $w\in\mathcal C(n)$. % If $w\notin\mathcal M(n)$, we define the \emph{max-interval} of $w$ to be the largest subsequence $\{p,\ldots,q\}$ of $\{1,\ldots, 2n\}$ such that $\bar w(p-1)=\max(w)=\bar w(q)$. For $w\in\mathcal M(n)$, we define the \emph{max-interval} of $w$ to be the max-interval of $\Psi^{-1}(w)$. Note that the max-interval subtends the part of $w$ which is modified by $\Psi$ (or $\Psi^{-1}$). % We define the \emph{min-interval} of $w$ to be the max-interval of $-w$. % The \emph{size} of the max-interval is its cardinality and likewise for the min-interval. \end{defn} The max-interval and min-interval are generically small in the following sense: \begin{lem}\label{lem:small intervals} Let $\,\mathcal U_{+}(n, k)\subset\mathcal C(n)$ be the set of walks whose max-interval has size~$2k$. Similarly, $\mathcal U_{-}(n,k)$ denotes the walks with a size~$2k$ min-interval. For any $\epsilon>0$, there exists $N$ such that for all $n\ge N$ we have: \[ \frac1{\card{\mathcal C(n)}} \card{\bigcup_{k=N}^n\mathcal U_+(n,k)} =\sum_{k=N}^n\frac{\card{\mathcal U_+(n,k)}}{\card{\mathcal C(n)}} <\epsilon \] and similarly for $\mathcal U_-$. \end{lem} \begin{proof} We will prove the claim for $\mathcal U_+$ as the proof for $\mathcal U_-$ is identical. For $1\le k\le n$, let $\mathcal U_+^*(n,k)=\mathcal U_+(n,k)\setminus\mathcal M(n)$. From the definitions we have $\card{\mathcal U_+^*(n,k)}=\frac12\card{\mathcal U_+(n,k)}$ so it suffices to prove the claim with $\mathcal U_+$ replaced by $\mathcal U_+^*$. Let $\epsilon>0$. For any $1\le k\le n$, \[ \card{\mathcal U^*_+(n,k)} \ = \ \card{\mathcal D(k)}\cdot\card{\mathcal M(n-k)} \ = \ \frac1{k+1}{2k \choose k}\cdot\frac12{2(n-k) \choose n-k} \] Indeed, each $w\in\mathcal U^*_+(n,k)$ corresponds to a pair $(d,m)$ with $d\in\mathcal D(k)$ and $m~\in~\mathcal M(n~-~k)$. The correspondence arises by inserting $d$ at the maximum of $m$. We now have the following inequality which proves the claim. Its first part holds since $\bigcup_{k=1}^n\mathcal U^*_+(n,k)= \mathcal C(n)\setminus\mathcal M(n)$ and $\card{\mathcal M(n)}=\frac12\card{\mathcal C(n)}$ by Theorem~\ref{thm:half}. Its second part holds by Lemma~\ref{lem:miniwallis} and its last part holds for $N$ sufficiently large by Lemma~\ref{lem:series}. \[ \sum_{k=N}^n\frac{\card{\mathcal U^*_+(n,k)}}{\card{\mathcal C(n)}}= \frac12-\sum_{k=1}^{N-1} \frac{\card{\mathcal U^*_+(n,k)}}{\card{\mathcal C(n)}}\le \frac12-\sum_{k=1}^{N-1} \frac12\frac1{k+1}{2k\choose k}4^{-k}<\epsilon \qedhere \] \end{proof} \begin{lem}\label{lem:miniwallis} ${2(n-k)\choose n-k}/{2n\choose n}\ge 4^{-k}$ for $0\le k\le n$. \end{lem} \begin{proof} For each fixed $n$, we prove this by induction on $k$. Base case: \[ {2(n-0)\choose n-0}/{2n\choose n}=1\ge 4^0 \] Inductive step: For $0\le k4^{-1} \qedhere \] \end{proof} \begin{lem}\label{lem:series} $\sum_{k=1}^\infty\frac12\frac1{k+1}{2k\choose k}4^{-k}=\frac12$. \end{lem} \begin{proof} The well-known generating function for the Catalan numbers is \[ \sum_{k=0}^\infty\frac1{k+1}{2k\choose k}x^k= \frac{1-\sqrt{1-4x}}{2x} \] where this equality holds for $\left|x\right|<1/4$. Setting $x=1/4$, the left-hand side converges by the elementary estimate ${2k\choose k}\le\frac{4^k}{\sqrt{3k+1}}$ of the central binomial coefficient. We thus obtain the following by applying $\lim_{x \nearrow \frac14}$ to each side, and note that Abel's theorem ensures the convergence of this limit on the left. \[ \sum_{k=0}^\infty\frac1{k+1}{2k\choose k}4^{-k}=2 \] The conclusion follows since the 0-th term of this series is $1$. \end{proof} \begin{lem}\label{lem:band} If the max-interval and min-interval of $w$ intersect and have size $s_1$ and $s_2$, then: \[ \max(w)-\min(w)\le\frac12\sup(s_1,s_2) \] \end{lem} \begin{proof} Let $\{a,\ldots, b\}$ be the max-interval of $w$. By hypothesis, there is $c\in \{a,\ldots,b\}$ with $\bar w(c)=\min(w)$. Clearly, the difference between the maximum and minimum on a size~$s$ interval is at most $s$. Since $\max(w)$ and $\min(w)$ are both attained on $\{a,\ldots,c\}$ and on $\{c,\ldots,b\}$, and since one of these intervals is of size at most $\frac{s_1}2$, it follows that $\max(w)-\min(w)\le\frac{s_1}2$. Similarly, $\max(w)-\min(w)\le\frac{s_2}2$. \end{proof} The following is a classical fact about random walks, and we refer to \cite{Renault2008} for an account of its history: \begin{lem}[Reflection principle]\label{lem:reflect} For $h\ge 0$, the number of walks $w\in\mathcal C(n)$ with $\max w\ge h$ is equal to ${2n\choose n+h}$. \end{lem} \begin{proof} For any $w\in\mathcal C(n)$ with $\max(w)\ge h$, define $Rw$ by \[ (Rw)(i)= \begin{cases} w(i);& i\le I(w)\\ -w(i)& i> I(w) \end{cases} \] where $I(w)$ is minimal such that $\bar w(i)=h$. Then $R$ is an injection onto the set of walks $w\in\mathcal W(2n)$ such that $\bar w(2n)=2h$. The cardinality of the latter set is ${2n\choose n+h}$. \end{proof} \begin{lem}[Generically Disjoint]\label{lem:gen disjoint} Let $\mathcal J(n)\subset\mathcal C(n)$ be the subset of walks whose max-interval and min-interval are disjoint. Then $\lim_{n\rightarrow \infty} \frac{\card{\mathcal J(n)}}{\card{\mathcal C(n)}}=1$. \end{lem} \begin{proof} Fix $\epsilon>0$. Let $N$ be as in Lemma~\ref{lem:small intervals} and let $n\ge N$. % Let $\mathcal O(n)=\mathcal C(n)\setminus\mathcal J(n)$ consist of those walks whose max-interval and min-interval overlap. Let \[ \mathcal K_1(n) = \mathcal O(n)\cap \left(\bigcup_{k=N}^n\mathcal U_+(n,k)\cup \bigcup_{k=N}^n\mathcal U_-(n,k)\right) \] (so that $\frac{\card{\mathcal K_1(n)}}{\card{\mathcal C(n)}}\le 2\epsilon$ by Lemma~\ref{lem:small intervals}) and let \[ \mathcal K_2(n) = \mathcal O(n)\cap \left(\bigcup_{k=1}^{N-1}\mathcal U_+(n,k)\cap \bigcup_{k=1}^{N-1}\mathcal U_-(n,k)\right) \] % By Lemma~\ref{lem:band}, for any $w\in\mathcal K_2(n)$ we have $\max(w)0$, which proves the claim. \end{proof} \begin{lem}\label{lem:oneoneoneone} $\mathcal J(n)$ is partitioned into 4 subsets of equal cardinality according to whether there is a unique max and/or unique min. \end{lem} \begin{proof} Since the max-interval and min-interval of elements of $\mathcal J(n)$ are disjoint, it is easily seen that the restrictions of the map $\Psi$ to $\mathcal J(n)$ leaves $\mathcal J(n)\cap-\mathcal M(n)$ invariant and hence provides bijections \[(\mathcal J(n)\cap-\mathcal M(n))\setminus\mathcal M(n)\to (\mathcal J(n)\cap-\mathcal M(n))\cap\mathcal M(n)\] and \[(\mathcal J(n)\setminus-\mathcal M(n))\setminus\mathcal M(n)\to (\mathcal J(n)\setminus-\mathcal M(n))\cap\mathcal M(n).\] Similarly, the map $w\mapsto -\Psi(-w)$ provides bijections \[(\mathcal J(n)\setminus-\mathcal M(n))\cap\mathcal M(n)\to (\mathcal J(n)\cap-\mathcal M(n))\cap\mathcal M(n)\] and \[(\mathcal J(n)\setminus-\mathcal M(n))\setminus\mathcal M(n)\to (\mathcal J(n)\cap-\mathcal M(n))\setminus\mathcal M(n).\] Combining these gives the desired one-to-one-to-one-to-one correspondence. \end{proof} \begin{thm}\label{thm:1/4} $\lim_{n\to\infty} \frac{\card{\mathcal M(n)\cap-\mathcal M(n)}} {\card{\mathcal C(n)}}=\frac14$. \end{thm} \begin{proof} Combine Lemma~\ref{lem:gen disjoint} and Lemma~\ref{lem:oneoneoneone}. \end{proof} \begin{rem}\label{rem:fromabove} The first few terms of the sequence $\card{\mathcal M(n)\cap-\mathcal M(n)}$ are: \[ 0, 2, 4, 18, 64, 230, 852, 3206, 12144, 46188,\ldots \] \begin{com} It appears to be new to the OEIS.\end{com} The convergent sequence $\card{\mathcal M(n)\cap-\mathcal M(n)} / \card{\mathcal C(n)}$ has the following initial terms, where $d=29099070$: {\small \[ \frac{0}{d}, \frac{9699690}{d}, \frac{5819814}{d}, \frac{7482618}{d}, \frac{7390240}{d}, \frac{7243275}{d}, \frac{7223895}{d}, \frac{7248766}{d}, \frac{7268184}{d}, \frac{7274610}{d},\ldots \] } It is not monotonic, but we have verified that its terms are $\ge 1/4$ for all $n\geq 1$. \end{rem} \section{Dyck words with a unique maximum}\label{sec:dyck unimax} In this section we show that, asymptotically, one half of all Dyck words have a unique maximum. We refer to \cite{Deutsch99} for a variety of other elegant counts of frequencies of various configurations within Dyck words. We begin by describing a second, more straightforward, proof of Theorem~\ref{thm:half}. \begin{proof}[Cyclic Permutation Proof] We describe a map $\mathcal M(n)\rightarrow \mathcal D(n-1)$. We cyclically permute so that the maximum appears at the beginning and end. This yields a $(2n-1)$-to-$(1)$ map to length~$2n$ Dyck words whose trajectories are negative except at the endpoints. % After removing the first and last edges, we obtain a $(2n-1)$-to-$(1)$ map from $\mathcal M(n) \rightarrow \mathcal D(n-1)$. % Since $\card{\mathcal D(n-1)} = \frac{1}{n}{2n-2 \choose n-1}$ by Theorem~\ref{thm:counting Dyck words}, we have: $\mathcal M(n) = \frac{2n-1}{n}{2n-2 \choose n-1} = \frac{1}{2}{2n\choose n}$. \end{proof} \begin{thm} $\lim_{n\to\infty}\frac {\card{\mathcal D(n)\cap-\mathcal M(n)}} {\card{\mathcal D(n)}} =\frac12$. \end{thm} \begin{proof} We employ the $(2n-1)$-to-$1$ map $\mathcal M(n)\to\mathcal D(n-1)$ from the above proof of Theorem~\ref{thm:half}. Observe that an element of $\mathcal D(n-1)$ has a unique minimum if and only if $(2n-2)$ of its $(2n-1)$ pre-images have a unique minimum. Thus: \[ \card{\mathcal D(n-1)\cap-\mathcal M(n-1)}= \frac1{2n-2}\card{\mathcal M(n)\cap-\mathcal M(n)} \] and hence \[ \lim_{n\to\infty} \frac {\card{\mathcal D(n-1)\cap\mathcal M(n-1)}} {\card{\mathcal D(n-1)}} =\lim_{n\to\infty} \frac {\frac1{2n-2}\card{\mathcal M(n)\cap-\mathcal M(n)}} {\frac1{2n-1}\card{\mathcal M(n)}} =\frac12 \] where the last equality is by Theorem~\ref{thm:1/4}. \end{proof} \begin{rem} \begin{com} The sequence $\card{\mathcal D(n)\cap-\mathcal M(n)}$ has already been identified. \end{com} As in Remark~\ref{rem:fromabove}, we note that $\frac{\card{\mathcal D(n)\cap-\mathcal M(n)}} {\card{\mathcal D(n)}}\ge\frac12$ for all $n$. \end{rem} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% BIBLIOGRAPHY %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \bibliographystyle{plain} \newpage \def\cprime{$'$} \def\polhk#1{\setbox0=\hbox{#1}{\ooalign{\hidewidth \lower1.5ex\hbox{`}\hidewidth\crcr\unhbox0}}} \def\cprime{$'$} \def\cprime{$'$} \def\polhk#1{\setbox0=\hbox{#1}{\ooalign{\hidewidth \lower1.5ex\hbox{`}\hidewidth\crcr\unhbox0}}} \begin{thebibliography}{99} \bibitem{BlackwellHodges67} David Blackwell and J.~L. Hodges, Jr. \newblock Elementary {P}ath {C}ounts. \newblock {\em Amer. Math. Monthly}, 74(7):801--804, 1967. \bibitem{ChungFeller49} Kai~Lai Chung and W.~Feller. \newblock On fluctuations in coin-tossing. \newblock {\em Proc. Nat. Acad. Sci. U. S. A.}, 35:605--608, 1949. \bibitem{Deutsch99} Emeric Deutsch. \newblock Dyck path enumeration. \newblock {\em Discrete Math.}, 204(1-3):167--202, 1999. \bibitem{DvoretzkyMotzkin47} A.~Dvoretzky and Th. Motzkin. \newblock A problem of arrangements. \newblock {\em Duke Math. J.}, 14:305--313, 1947. \bibitem{Dwass67} Meyer Dwass. \newblock Simple random walk and rank order statistics. \newblock {\em Ann. Math. Statist.}, 38:1042--1053, 1967. \bibitem{Narayana67} T.~V. Narayana. \newblock Cyclic permutation of lattice paths and the {C}hung-{F}eller theorem. \newblock {\em Skand. Aktuarietidskr}, 1967:23--30, 1967. \bibitem{Renault2008} Marc Renault. \newblock Lost (and found) in translation: {A}ndr\'e's actual method and its application to the generalized ballot problem. \newblock {\em Amer. Math. Monthly}, 115(4):358--363, 2008. \end{thebibliography} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % \end{document}