\documentclass[12pt]{article}
\usepackage{e-jc}
\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{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\\
\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{June 13, 2015}{Dec 24, 2015}\\
\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<m$ and $\bar w(i)=0$. Then
  $\Psi(w)=bxa$ by definition. As $\rank(w)=r$, we have
  $\rank(a)=r-1$. Hence $\rank(w')\ge r-1$ as desired.
\end{proof}


\begin{figure}
    \centering
    \begin{tikzpicture}[scale=.5]
      \foreach \y/\z/\s [count=\i] in
      {1/2/,2/3/,3/2/,2/3/,
        3/2/,2/3/,3/2/,2/3/,
        3/2/,2/1/}
      \draw [\s] (\i,\y) -- ({\i+1},\z);
      \foreach \y/\z/\s [count=\i] in
      {1/2/,2/3/,
        3/2/,2/3/,3/4/very thick,4/3/very thick,3/2/,2/3/,3/2/,2/3/,
        3/2/,2/1/}
      \draw [\s] ({\i+14},\y) -- ({\i+15},\z);

      \draw [->,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 $p<n$ be maximal such that $\bar
  \walk_v(p)=0$.  Regard $\walk$ as a string in $S$, and express $\walk$ as the
  concatenation $axb$ where $a$ is the initial length~$p$ subpath and
  $x$ is a single symbol (which necessarily satisfies $v(x)<0$).
  Define $\psi_v(\walk)$ to be the sequence corresponding to $bxa$. This
  lies in $\mathcal M_v(n)$ since $a$ has $v$-maximum $0$ and $\bar
  b_v$ obtains its unique maximum at the end.

  To see that $\psi_v$ is injective, we describe its
  (left-)inverse. Any walk $\walk$ in the image of $\psi_v$ has the
  form $bxa$, where $\max_v(a)=0$, $b$ has length $q$,
  $\bar \walk_v(q)>0$, 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 k<n$
  \[
  \frac{{2(n-(k+1))\choose n-(k+1)}/{2n\choose n}}
    {{2(n-k)\choose n-k}/{2n\choose n}}=
  \frac{{2(n-k)-2\choose(n-k)-1}}
    {{2(n-k)\choose n-k}}=
  \frac{(n-k)^2}{(2(n-k)-1)(2(n-k))}>4^{-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)<N$. Hence, by Lemma~\ref{lem:reflect}, we have
  \[
  \frac{\card{\mathcal K_2(n)}}{\card{\mathcal C(n)}}\le
  \frac{{2n\choose n}-{2n\choose n+N}}{{2n\choose n}}=
  1-\frac{(n-N+1)\cdots(n-N+N)}{(n+1)\cdots(n+N)}
  \ \ \xrightarrow{n\to\infty}\ \ 0
  \]
  and so
  \[
  \lim_{n\to\infty} \frac{\card{\mathcal O(n)}}{\card{\mathcal C(n)}}=
  \lim_{n\to\infty} \frac{\card{\mathcal K_1(n)}}{\card{\mathcal C(n)}}+
  \lim_{n\to\infty}
  \frac{\card{\mathcal K_2(n)}}{\card{\mathcal C(n)}}<
  2\epsilon+
  \lim_{n\to\infty}
  \frac{\card{\mathcal K_2(n)}}{\card{\mathcal C(n)}}
  =2\epsilon.
\]
Hence,
$\frac{\card{\mathcal J(n)}}{\card{\mathcal C(n)}}\ge 1-2\epsilon$
for every $\epsilon>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}{1}

\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}
