\section{Introduction}
Urn models have provided simple and useful models to study different phenomena since the early works \cite{Polya, PolyaEggenberger}. The model starts with given quantities of objects of finitely many colors. A color is chosen at random, and further objects of each color are added to the urn, where the amount of each color added will depend on the color chosen. The additional amount, which will be nonnegative real valued, of each color can be summarized by a square matrix, called the replacement matrix, where the row corresponding to the color chosen will provide the amount to be added. The replacement matrices can be random, such that they are ``close'' to an irreducible replacement matrix in an appropriate sense. A square matrix $\boldsymbol{A}$ with nonnegative entries is called \textit{irreducible} if, for any $i, j$, there exists a positive integer $N\equiv N_{ij}$, such that the $(i,j)$-th entry of $\boldsymbol{A}^N$ is positive. By Perron-Frobenius theory, the \textit{dominant eigenvalue} of an irreducible matrix, namely the eigenvalue having the largest real part, is simple and positive and has corresponding left and right eigenvectors with all coordinates strictly positive.

In \cite{AthreyaNey}, the replacement matrices formed an i.i.d.\ sequence, with $L \log_+ L$ moments for the entries and irreducible mean matrix. Using branching process techniques, it was shown in \cite{AthreyaNey}, cf.\ Chapter~V.9.3, the normalized color count vector converges almost surely to the (normalized to probability) left eigenvector of the mean matrix corresponding to its dominant eigenvalue. However, the i.i.d.\ assumption on the replacement matrices can be restrictive for applications. The replacement matrices may depend on the entire past. In \cite{BaiHu} and \cite{LaruellePages}, the replacement matrices at any step are independent of the color choice in that step given the entire history. Martingale methods were used in \cite{BaiHu}, while stochastic approximation was used in \cite{LaruellePages}. In both works, the conditional means of the replacement matrices were assumed to concentrate around an irreducible, balanced (i.e., the row sums being same) matrix and almost sure convergence and central limit behavior of the proportion vector was obtained under second or higher moments. In \cite{Zhang12}, the balanced condition was removed and the mode of concentration of the conditional mean replacement matrices was relaxed. It then proved the almost sure convergence under $L (\log_+ L)^p$ moments, for some $p>1$, in general; and, under $L \log_+ L$ moments only for i.i.d.\ replacement matrices. Note that the latter result is essentially same as the one obtained in \cite{AthreyaNey}. Further, convergence in probability was proved in \cite{GangoMaulik} under $L^1$ moments alone.

In this article, we significantly relax the assumptions to obtain almost sure convergence results applying the method of stochastic approximation. Our method obtains almost sure convergence under $L (\log_+ L)^p$ condition for some $p>1$, as in \cite{Zhang12}. However, we relax the moment condition further; and use only $L \log_+ L$ condition with appropriate majorization condition on the norms of the replacement matrices. The additional moments in \cite{Zhang12} or the majorization condition provide the required uniform integrability. We also establish almost sure convergence result for i.i.d.\ replacement matrices under $L^1$ conditions alone, instead of $L \log_+ L$ condition in \cite{AthreyaNey, Zhang12}. As in \cite{GangoMaulik, Renlund, Renlund2}, we use random step sizes instead of deterministic ones considered in \cite{Zhang}, leading to a Lotka-Volterra type first order quadratic differential equation.

In Section~\ref{sec: lv}, we state the model and the main results. In Corollary~\ref{cor: iid}, we extend the result for i.i.d.\ replacement matrices in \cite{AthreyaNey, Zhang12} and prove it under $L^1$ assumptions rather than $L \log_+ L$ conditions. Corollary~\ref{cor: L log L} studies adapted replacement matrices, when they are majorized by a $L \log_+ L$ random variable. In Section~\ref{sec:urn}, the main tool for the proof -- an appropriate result on stochastic approximation -- was provided and the main results were proven. Finally, in Section~\ref{sec:erw}, we apply the results for the urn model to study a delayed elephant random walk on $d$-dimensional nonnegative orthant with randomly reinforced memory.

\section{Urn Model and Main Result} \label{sec: lv}
In this Section, we first collect some notations. In two subsequent subsections, we describe the model; and state the main result. In the following, all the vectors are row vectors, while the transpose of a row vector $\x$ will be $\x^T$. The vector $\bds{1}$ has all components $1$, the dimension being clear from the context. Also, for an event $A$, we shall denote its indicator function by $\bone_A$. For a matrix $\boldsymbol{A}$, define the norm $\mynorm{\boldsymbol{A}} := \max_i\sum_{j}\left|A_{ij}\right|.$ We shall also use the notation $\sigma\left(\boldsymbol{A}\right) := \min_i\sum_{j}\left|A_{ij}\right|$.

\subsection{Urn Model}
Consider an urn model with $K$ colors indexed by $\{1, 2, \ldots, K\}$. The composition vector after $n$-th trial is $\C_n = (C_{n1}, \ldots, C_{nK})$. The total content of the urn after $n$-th trial is $S_n = \sum_{i=1}^K C_{ni}$. The replacement matrix for $n$-th trial will be a random $K\times K$ matrix $\R_n$, with nonnegative entries. For $n$-th trial, $\Chi_n$ is the indicator of the color chosen in that trial, taking value $\bds{e}_i$, the $i$-th coordinate vector in $\ensuremath{\mathbb{R}}^K$ if the color $i$ is chosen in $n$-th trial. In this case, $i$-th row of $\R_n$ is added to the composition vector. Therefore, for $n\geq 1$, the urn composition evolves as:
\begin{equation}
\C_n = \C_{n-1} + \Chi_n\R_n.
\label{EvolutionEqn}
\end{equation}
The count vector after $n$-th trial, $\N_n$, giving the number of times each color is drawn till $n$-th trial, is $\N_n = \sum_{k=1}^n \Chi_k$. For $n\geq 1$, $\FF_{n}$ is the $\sigma$-field containing the information till time $n$, namely, $\FF_n$ is the $\sigma$-field generated by $\C_0$, $\left(\R_m, \Chi_m\right)_{m=1}^{n}$. The conditional expectations of the replacement matrices, denoted as $\bH_{n-1} := \CExp{\R_n}{n-1}$ and their truncated version, denoted as $\widetilde{\bH}_{n-1} := \CExp{\R_n \indic{\mynorm{\R_n}\le n}}{n-1}$, called the \textit{generating matrices} and the \textit{truncated generating matrices} respectively.

We make the following assumptions on choice of colors and reinforcement matrices.
\begin{assumption} \label{Assmp: basic}
The adapted sequence $((\Chi_n, \R_n), \FF_n)$ has distribution, which satisfies:
\begin{enumerate}[label={\normalfont (\roman*)},ref={\normalfont \roman*}]
\item The initial configuration $\C_0$ is nonzero with nonnegative entries and finite mean. \label{Assmp: init}
\item For all $i$, $\Prob\left(\Chi_n=\boldsymbol{e}_i|\C_0,(\R_m)_{m=1}^{n-1}, (\Chi_m)_{m=1}^{n-1}\right)=C_{n-1,i}/S_{n-1}$.
\item Given the past information $\FF_{n-1}$, $\Chi_n$ and $\R_n$ are conditionally independent.
\end{enumerate}
\end{assumption}

We also make uniform integrability type conditions on the replacement matrices.
\begin{assumption}
The sequence $(\mynorm{\R_n})$ satisfy one of the following: \label{Assmp: unif tail}
\begin{enumerate}[label={\normalfont (\alph*)},ref={\normalfont \alph*}]
  \item \label{Assmp: maj} The unconditional distributions of $\mynorm{\R_n}$ are majorized: there exists $c\in (0,\infty)$ and a positive random variable $R$ with finite expectation such that, for all $x>0$, \[\Prob\left(\mynorm{\R_n}>x\right) \le c \Prob(R>x).\]
  \item \label{Assmp: alt tail} For some nonnegative function $\phi$ on $[0, \infty)$ which is eventually positive and nondecreasing, satisfying $\sum 1/(n\phi(n))< \infty$ and $x/\phi(x)$ eventually monotone nondecreasing, we have, the following bounded moment condition:
      \begin{equation}
      \sup_n \Exp(\mynorm{\R_n}\phi(\mynorm{\R_n}) < \infty. \label{eq: exp bd}
      \end{equation}
\end{enumerate}
\end{assumption}

\begin{remark}
Under Assumption~\ref{Assmp: unif tail}, for all $n, i, j$, $R_{nij}$ have finite mean. \label{Rem: fin mean}
\end{remark}

\begin{remark} \label{rem: identical}
Assumption~\ref{Assmp: unif tail}\eqref{Assmp: maj} holds if $\left(\mynorm{\R_n}\right)$ have same marginal distribution.
\end{remark}

\begin{remark} \label{Rem: alt tail} One of the useful choices for $\phi(x) = (\log_+ x)^p$ for some $p>1$, has been considered by~\cite{Zhang12}. Other choices can include $\phi(x) = \log_+x (\log_+ \log_+ x)^p$ for some $p>1$.
\end{remark}

Finally, we state the conditions for closeness of the replacement matrices to an irreducible matrix.
\begin{assumption}
There exists a (possibly random) almost surely irreducible matrix $\bH$ with nonnegative entries, such that the truncated generating matrices $\widetilde{\bH}_n$ converge to $\bH$ in Cesaro sense in the operator norm almost surely, i.e., \label{Assmp: ae}
\[\frac1n \sum_{k=0}^{n-1} \mynorm{\widetilde{\bH}_{k}-\bH}\to 0 \text{ almost surely.}\]
The dominant eigenvalue of $\bH$ will be denoted by $\pfval$. By Perron-Frobenius theory, there exists unique left eigenvector $\lpf$ of $\bH$ corresponding to $\pfval$ such that $\lpf$ has all coordinates strictly positive and is normalized to be a probability vector.
\end{assumption}

\begin{remark} \label{Rem: sigma}
Since $\bH$ is irreducible, no row can be the zero vector and hence $\sigma(\bH)>0$.
\end{remark}

\begin{remark} \label{Rem: L1}
Both Assumptions~\ref{Assmp: unif tail}\eqref{Assmp: maj} and~\ref{Assmp: unif tail}\eqref{Assmp: alt tail} imply uniform integrability of  $\left(\mynorm{\R_n}\right)$ and, hence, of $\left(\R_n\indic{\mynorm{\R_n}\le n}\right)$. Thus, under either condition, the convergence in Assumption~\ref{Assmp: ae} is also in $L^1$.
\end{remark}

\begin{remark}
Different sufficient notions of closeness between the generating matrix and the limiting matrix $\bH$ have been considered in \cite{BaiHu, GangoMaulik, LaruellePages, Zhang12, Zhang}. See \cite{GangoMaulik} for further discussion on such assumptions.
\end{remark}

\subsection{Main Results} \label{subsec: result}
In this subsection, we state the main result and some corollaries covering the most relevant situations.
\begin{theorem} \label{Main}
Under Assumptions~{\normalfont \ref{Assmp: basic}},~{\normalfont \ref{Assmp: unif tail}} and~{\normalfont \ref{Assmp: ae}}, we have, almost surely, as well as in $L^1$,
\begin{equation}\label{strong conv}
  \frac{\C_n}{S_n} \to \boldsymbol{\pi}_{\bH}; \quad \frac{S_n}n \to \lambda_{\bH}; \quad
  \frac{\C_n}n \to \lambda_{\bH} \boldsymbol{\pi}_{\bH}; \quad \text{and} \quad
  \frac{\N_n}n \to \boldsymbol{\pi}_{\bH}.
\end{equation}
\end{theorem}

\begin{remark}
It is interesting to compare the assumptions in this article with those required to establish convergence in probability and in $L^1$ in \cite{GangoMaulik}. Note that Assumption~\ref{Assmp: basic} is same as Assumption~3.1 of \cite{GangoMaulik}. As noted in Remark~\ref{Rem: fin mean}, the finite mean of replacement matrices, as in Assumption~3.1~(ii) of \cite{GangoMaulik} follows from Assumption~\ref{Assmp: unif tail}.

As noted in Remark~\ref{Rem: L1}, Assumption~\ref{Assmp: unif tail} is the analog of the uniform integrability of $(\mynorm{\R_n})$ in Assumption~3.4 of \cite{GangoMaulik}. However, in this article, we need somewhat stronger conditions than uniform integrability, namely, either majorization condition in Assumption~\ref{Assmp: unif tail}\eqref{Assmp: maj} or appropriate uniform moment bounds in Assumption~\ref{Assmp: unif tail}\eqref{Assmp: alt tail}, as has been considered by~\cite{Zhang12}.

Finally, Assumption~\ref{Assmp: ae} corresponds to Assumptions~3.2 and~3.3 of \cite{GangoMaulik}. While Assumption~3.2 of \cite{GangoMaulik} on the properties of the matrix $\bH$ remain unchanged, given the almost sure convergence in conclusion, we naturally strengthen the mode of convergence to almost sure from convergence in probability. We further require the truncated generating matrices $\widetilde{\bH}_n$ to converge to $\bH$ instead of the generating matrices, as considered in \cite{GangoMaulik}. We shall provide sufficient conditions in Proposition~\ref{prop: suff tail ce} for convergence of $\bH_n$, as in \cite{GangoMaulik}, to become equivalent to Assumption~\ref{Assmp: ae}.
\end{remark}

There are simpler sufficient conditions which imply Assumptions~\ref{Assmp: basic},~\ref{Assmp: unif tail} and~\ref{Assmp: ae} and improve existing results. Chapter~V.9.3 of \cite{AthreyaNey}, and Theorem~2.1(a) of \cite{Zhang12} considered the urn model with i.i.d.\ replacement matrices having $L \log_+ L$ moments. In the following corollary we show $L^1$ moments suffice.

\begin{corollary} \label{cor: iid}
Let the adapted sequence $\left( \left( \Chi_n, \R_n\right), \FF_n\right)$ satisfy:
\begin{enumerate}[label={\normalfont (\roman*)},ref={\normalfont \roman*}]
\item The initial configuration $\C_0$ is nonzero with nonnegative entries and finite mean.
\item The replacement matrices $\R_n$ are i.i.d.\ with $\Exp\left(\mynorm{\R_1}\right)<\infty$. \item The colors chosen form the sequence $\left(\Chi_n\right)$, obtained using an i.i.d.\ Uniform$(0,1)$ sequence $(U_n)$ independent of the sequence $(\R_n)$ as:
\[\Chi_n = \sum_{i=1}^d \boldsymbol{e}_i \indic{U_n \in (\sum_{j=1}^{i-1} C_{n-1,j}/S_{n-1}, \sum_{j=1}^i C_{n-1,j}/S_{n-1}]}.\]
\end{enumerate}
Then the convergence~\eqref{strong conv} in Theorem~{\normalfont \ref{Main}}, namely,
\[\frac{\C_n}{S_n} \to \boldsymbol{\pi}_{\bH}; \quad \frac{S_n}n \to \lambda_{\bH}; \quad \frac{\C_n}n \to \lambda_{\bH} \boldsymbol{\pi}_{\bH}; \quad \text{and} \quad \frac{\N_n}n \to \boldsymbol{\pi}_{\bH}\]
hold both almost surely and in $L^1$.
\end{corollary}

While only $L^1$ condition suffices for i.i.d.\ replacement matrices, $L \log_+ L$ condition allows us to study adaptive urns. It is also natural to consider the generating matrices in Assumption~\ref{Assmp: ae} instead of the truncated ones.
\begin{assmprime}{Assmp: ae} \label{Assmp: aeprime}
There exists a (possibly random) matrix $\bH$ with nonnegative entries, which is almost surely irreducible, such that the generating matrices $\bH_n$ converge to $\bH$ in Cesaro sense in the operator norm almost surely:
    \[\frac1n \sum_{k=0}^{n-1} \mynorm{\bH_{k}-\bH}\to 0 \text{ almost surely.}\]
\end{assmprime}

\begin{remark} \label{Rem: tail ce}
Assumption~\ref{Assmp: aeprime} becomes equivalent to Assumption~\ref{Assmp: ae}, when considered along with the following negligibility condition on the tail conditional expectation:
\begin{equation}
\frac1n \sum_{k=1}^{n} \CExp{\mynorm{\R_{k}}\indic{\mynorm{\R_{k}}>k}}{k-1}\to 0 \text{ almost surely.} \label{eq: tail ce neg}
\end{equation}
\end{remark}

The following corollary shows Assumption~\ref{Assmp: aeprime}, along with $L \log_+ L$ condition on the majorizing variable in Assumption~\ref{Assmp: unif tail}\eqref{Assmp: maj} is again sufficient.
\begin{corollary} \label{cor: L log L}
The adapted sequence $\left( \left( \Chi_n, \R_n\right), \FF_n\right)$ satisfy Assumptions~{\normalfont\ref{Assmp: basic}},~{\normalfont\ref{Assmp: unif tail}\eqref{Assmp: maj}} and~{\normalfont\ref{Assmp: aeprime}}, where the majorizing random variable $R$, considered in Assumption~{\normalfont\ref{Assmp: unif tail}\eqref{Assmp: maj}} satisfy $\Exp(R \log_+ R) < \infty$. Then the convergence~\eqref{strong conv} in Theorem~{\normalfont \ref{Main}}, namely, ${\C_n}/{S_n} \to \boldsymbol{\pi}_{\bH}$; ${S_n}/n \to \lambda_{\bH}$; ${\C_n}/n \to \lambda_{\bH} \boldsymbol{\pi}_{\bH}$ and ${\N_n}/n \to \boldsymbol{\pi}_{\bH}$ hold both almost surely and in $L^1$.
\end{corollary}
Corollary~\ref{cor: L log L} extends the result on i.i.d.\ sequence of replacement matrices given in \cite{AthreyaNey} to adapted sequence with similar $L \log_+ L$ moment for the majorizing random variable. This corollary is also similar to the result in~\cite{Zhang12} for adapted sequence with $L (\log_+ L)^p$-bounded moments, for some $p>1$. In this corollary $L (\log_+ L)^p$-boundedness conditions is replaced by $L \log_+ L$ moment of the majorizing random variable.

The following corollary generalizes $L (\log_+ L)^p$ condition, for some $p>1$, used in Assumption~2.2(a) of \cite{Zhang12} in terms of Assumption~\ref{Assmp: unif tail}\eqref{Assmp: alt tail}. See also Remark~\ref{Rem: alt tail}.
\begin{corollary} \label{cor: phi}
Assumptions~{\normalfont \ref{Assmp: basic}},~{\normalfont \ref{Assmp: unif tail}\eqref{Assmp: alt tail}} and~\ref{Assmp: aeprime} imply the convergence~\eqref{strong conv} in Theorem~{\normalfont \ref{Main}} both almost surely and in $L^1$.
\end{corollary}

\section{Proofs of the Main Results} \label{sec:urn}
In the first subsection, we prove the relevant result on stochastic approximation and a couple other technical results. In the next subsection, we check the conditions of stochastic approximation for the urn model. In the last two subsections, we prove the theorem and corollaries of Section~\ref{subsec: result}.

\subsection{Stochastic Approximation and Other Results}
The main tool for proving Theorem~\ref{Main} is Stochastic Approximation. We shall use the following theorem on Stochastic Approximation, which follows from a special case of Theorem~9.2.8 of \cite{Duflo}, which in turn was adapted from \cite{KushnerClark}.
\begin{theorem} \label{Thm: SA}
Let $\left(\x_n\right)_{n=0}^\infty$ be a sequence that takes values in a compact convex subset $S$ of $\ensuremath{\mathbb{R}}^K$. Let $\left( a_n\right)_{n=0}^\infty$ be a nonincreasing sequence of positive real numbers, called the step sizes, such that
\begin{equation} \label{eq: step order}
0<\liminf {n}{a_n} \le \limsup {n}{a_n} <\infty.
\end{equation}
Define for $n\geq 0$ and $T>0$
\begin{equation} \label{eq: tau}
\Tau{n}{T}:=\inf\left\{  k\geq n: a_n+\cdots+a_k\geq T\right\}.
\end{equation}
Let $\left(\bgamma_n\right)_{n=0}^\infty$ be a sequence, called the error sequence, in $\ensuremath{\mathbb{R}}^K$ such that $\left(\bgamma_n\right)$ goes to $0$ in Cesaro sense, i.e., $\frac1n \bds{\Gamma}_n \to \bds{0}$, where $\bds{\Gamma}_n := \sum_{i=1}^n \bgamma_i$.
Let $h:S\to\ensuremath{\mathbb{R}}^K$ be a continuous function. Suppose for all $n\geq 0$
\[
\x_{n+1}=\x_n+a_n h(\x_n)+a_n\bgamma_n.
\]
If the ODE $\dot{\x}=h(\x)$ has a unique solution $\z:\ensuremath{\mathbb{R}}\to S$, then $\lim_{n\to\infty}\x_n=\z(0)$.
\end{theorem}
\begin{proof}
It is immediate from~\eqref{eq: step order} that $\lim_{n\to\infty} a_n=0$ and $\sum_{n=0}^\infty a_n=\infty$. Then, using Theorem~9.2.8 of \cite{Duflo}, it is enough to show that, for all $T>0$,
\[\lim_{n\to\infty}\sup_{n\leq j\leq\Tau{n}{T}}\Lone{\sum_{k=n}^j a_k\bgamma_k}=0.\]

Fix $T>0$. First observe that
\[a_n\bgamma_n = \left( a_n\bds{\Gamma}_n - a_{n-1}\bds{\Gamma}_{n-1}\right) + a_n a_{n-1}\bds{\Gamma}_{n-1} \left( \frac1{a_n} - \frac1{a_{n-1}} \right).\]
Since $(a_n)$ is nonincreasing, for $n\leq j\leq\Tau{n}{T}$, we have,
\[\Lone{\sum_{k=n}^j a_k\bgamma_k} \le \Lone{a_j\bds{\Gamma}_j} + \Lone{a_{n-1}\bds{\Gamma}_{n-1}} + \sup_{k\ge n-1} \Lone{a_k \bds{\Gamma}_k} \frac{a_n}{a_j}.\]
Hence, we have
\[\sup_{n\leq j\leq\Tau{n}{T}}\Lone{\sum_{k=n}^j a_k\bgamma_k} \le \sup_{j\ge n-1} \Lone{a_j\bds{\Gamma}_j} \left( 2 + na_n \cdot \frac{\Tau{n}{T}}{n} \cdot \frac1{\Tau{n}{T}a_{\Tau{n}{T}}}\right).\]
Again, using~\eqref{eq: step order}, we have $n a_n$ bounded away from both $0$ and $\infty$, and, further, $a_n \bds{\Gamma}_n \to \bds{0}$. So, it is enough to show that $\Tau{n}{T}/n$ is bounded for any $T>0$. Since $\liminf na_n >0$, choose $a^*>0$ such that $n a_n > a^*$ for all large enough $n$. Further note that $a_n < T$ for all large enough $n$. Hence, from~\eqref{eq: tau}, we have $\Tau{n}{T}>n$ for all large enough $n$ and
\[a^*\left[\log (\Tau{n}{T}-1) - \log (n-1) -1\right] \le \frac{a^*}{n} + \cdots + \frac{a^*}{\Tau{n}{T}-1} \le a_n + \ldots + a_{\Tau{n}{T}-1} \le T.\]
Thus, $\Tau{n}{T}/n \le (\Tau{n}{T}-1)/(n-1) \le \exp(T/a^*+1)$, as required.
\end{proof}

Next we prove two technical results. The first result studies average of a dominated adapted sequence, where the terms are centered by a truncated conditional expectation.
\begin{proposition} \label{prop: trunc mg}
Let $(X_n, \FF_n)$ be a adapted sequence, such that $|X_n|\le c' \mynorm{\R_n}$ for some $c'\in(0,\infty)$. Then, under Assumptions~{\normalfont \ref{Assmp: basic}} and~{\normalfont \ref{Assmp: unif tail}}, we have, with probability 1,
$\frac1n \sum_{k=1}^n \left( X_k - \CExp{X_k \indic {\mynorm{\R_k}\le k}}{k-1} \right) \to 0$. \end{proposition}
\begin{proof}
The proof follows Theorem~2.19 of \cite{HH}. By Kronecker's lemma, it is enough to show 
\[
\sum_{k=1}^n\frac1{k} \left( X_k - \CExp{X_k \indic {\mynorm{\R_k}\le k}}{k-1}\right)< \mbox{ converges almost surely.}
\]
We write
\begin{multline} \label{eq: trunc mg}
  \sum_{k=1}^n \frac1k \left( X_k - \CExp{X_k \indic{\mynorm{\R_k}\le k}}{k-1} \right)\\
  = \sum_{k=1}^n \frac1k \left[\MGD{X_k \indic{\mynorm{\R_k}\le k}}{k-1}\right] + \sum_{k=1}^n \frac1k X_k \indic{\mynorm{\R_k}> k}.
\end{multline}

The first sum is a martingale and, since $|X_n|\le c' \mynorm{\R_n}$, it is almost surely convergent if 
\[
\sum_n \frac{1}{n^2}\CExp{\mynorm{\R_n}^2 \indic{\mynorm{\R_n}\le n}}{n-1}< \infty\mbox{ almost surely.}
\]
Under Assumption~\ref{Assmp: unif tail}\eqref{Assmp: maj}, we show its expectation to be finite. We have
\begin{align*}
  &\sum_{n\ge1} \frac1{n^2} \Exp\left(\mynorm{\R_n}^2 \indic{\mynorm{\R_n}\le n}\right) = \sum_n \frac1{n^2} \int_0^n 2r \Prob(\mynorm{\R_n}>r) dr\\
  &\qquad \qquad \le 2c \sum_{j\ge1} \sum_{n\ge j} \frac1{n^2} \int_{j-1}^j r \Prob(R>r) dr \le 8c \int_0^\infty \Prob(R>r) dr < \infty.
\end{align*}
Under Assumption~\ref{Assmp: unif tail}\eqref{Assmp: alt tail}, for all large enough $n$, we have
\[\CExp{\mynorm{\R_n}^2 \indic{\mynorm{\R_n}\le n}}{n-1} \le \frac{n}{\phi(n)} \CExp{\mynorm{\R_n} \phi(\mynorm{\R_n})}{n-1},\]
since $x/\phi(x)$ is eventually monotone nondecreasing. The result follows from summability of $1/(n\phi(n))$.

For the second sum on the right side of~\eqref{eq: trunc mg}, note that $\Prob(\mynorm{\R_n}>n)$ is summable under Assumption~\ref{Assmp: unif tail}\eqref{Assmp: maj} by finiteness of the moment of the majorizing distribution. Markov type inequality gives
\[\Prob(\mynorm{\R_n}>n) \le \frac1{n \phi(n)} \Exp{\mynorm{\R_n} \phi(\mynorm{\R_n})},\] which is again summable under Assumption~\ref{Assmp: unif tail}\eqref{Assmp: alt tail}. Then, by Borel-Cantelli lemma, the second sum on the right of~\eqref{eq: trunc mg} has at most finitely many terms with nonzero indicator functions and hence converges almost surely.
\end{proof}

The next result provides SLLN for martingale differences.
\begin{proposition} \label{prop: mg SLLN}
Let $\left( U_n, \FF_n \right)$ be a martingale difference sequence. Let $\left( V_n \right)$ be a sequence of random variables having common distribution with finite mean, such that $V_n$ is independent of $\FF_{n-1}$ and $|U_n|\le V_n$ for all $n$. Then $\frac1n \sum_{k=1}^{n} U_k \to 0$ almost surely.
\end{proposition}
\begin{proof}
Since the martingale difference sequence is dominated by a sequence of random variables with common distribution with finite mean, as in derivation of~(2.20) of~\cite{HH}, we have
$\frac1n \sum_{k=1}^{n} \left( U_k - \CExp{U_k \indic{[|U_k|\le k]}}{k-1} \right) \to 0$ almost surely.

Further, since $V_n$ dominates $U_n$, we have
$\CExp{U_n \indic{[|U_n| > n]}}{n-1} \le \Exp{V_n \indic{[V_n| > n]}} \to 0$, which takes care of the remainder term in the centering.
\end{proof}

\subsection{Analysis of the Urn Model} \label{subsec: analysis}
In this subsection, we check that the evolution equation~\eqref{EvolutionEqn} of the urn model forms stochastic approximation and check the conditions of Theorem~\ref{Thm: SA}.

Total amount added to the urn in each step is denoted by $Y_n$ for $n\ge 0$. Define $Y_0:=S_0$ and for $n\geq 1$, $Y_n:=S_n-S_{n-1}=\Chi_n\R_n\boldsymbol{1}^T$. It is immediate to observe that
\begin{equation}
  0\leq Y_n=\Chi_n\R_n\boldsymbol{1}^T\leq\mynorm{\R_n} \text{ almost surely.} \label{Y bd}
\end{equation}

Following~\cite{GangoMaulik}, we rewrite the evolution equation \eqref{EvolutionEqn} as
\begin{equation} \label{eq: Mod SA}
\csd{n} = \csd{n-1} + \frac{1}{S_n}h_{\bH}\left(\csd{n-1}\right) + \frac{\bds{\delta}_n}{S_n} + \frac{\bxi_n}{S_n},
\end{equation}
where $h_{\bH}$, $\bds{\delta}_n$, $\bxi_n$ are defined as follows. The drift $h_{\bH}$, indexed by $K\times K$ matrices, is defined as $h_{\bH}\left(\bX\right) := \bX\bH - \bX\left(\bX\bH\boldsymbol{1}^T\right)$. For each $n\geq 1$, define the martingale difference term
\begin{align*}
\bds{\delta}_n := &\left(\Chi_n\R_n-\csd{n-1}Y_n\right) - \CExp{\left(\Chi_n\R_n-\csd{n-1}Y_n\right) \indic{\mynorm{\R_n}\le n}}{n-1},
\intertext{and adjusted truncated conditional expectation term}
\bxi_n := &\csd{n-1}\left(\widetilde{\bH}_{n-1}-\bH\right) - \csd{n-1}\left(\csd{n-1}\left(\widetilde{\bH}_{n-1}-\bH\right)\boldsymbol{1}^T\right)
= h_{\widetilde{\bH}_{n-1}-\bH} \left(\csd{n-1}\right),
\end{align*}
We shall refer to~\eqref{eq: Mod SA} as the stochastic approximation equation. Note that the stochastic approximation for the sequence $\left(\csl{n}\right)$ takes values in the closed bounded convex set of probability simplex in $\ensuremath{\mathbb{R}}^K$. The corresponding ODE $\dot{\x}=h_{\bH}\left(\x\right)$ defined in terms of $h_{\bH}$ is a first order quadratic equation of Lotka-Volterra type. Since $h_{\bH}(\x)$ is polynomial in $\x$, it is continuous, as required in Theorem~\ref{Thm: SA}. Further, we have, from Proposition~3.3 of~\cite{GangoMaulik}, that the Lotka-Volterra equation has unique solution in the probability simplex given by $\x(t)=\lpf$ for all $t$.

Next we consider the step sizes. Unlike the usual step size $(1/n)$, we use, as in \cite{GangoMaulik} the random step size $1/S_{n+1}$ of the stochastic approximation equation~\eqref{eq: Mod SA}. The step size $1/S_{n+1}$ has also been used to analyze two color urn models with fixed replacement unbalanced matrices in \cite{Renlund, Renlund2}. The choice of this random step size makes $\C_n/S_n$ take values in the $k$-dimensional probability simplex, which is compact and convex, as required in Theorem~\ref{Thm: SA}. Since $S_n$'s are partial sum of nonnegative $Y_n$'s, the step sizes are nonincreasing, as required in Theorem~\ref{Thm: SA}. In the next proposition, we check the condition~\eqref{eq: step order} as required in Theorem~\ref{Thm: SA}.

\begin{proposition} Under Assumptions~{\normalfont \ref{Assmp: basic}},~{\normalfont \ref{Assmp: unif tail}} and~{\normalfont \ref{Assmp: ae}}, we have:
\[0 < \sigma\left(\bH\right) \leq \liminf_{n\to\infty} \frac{S_n}n \leq \limsup_{n\to\infty} \frac{S_n}n \leq \mynorm{\bH} < \infty.\]
\end{proposition}
\begin{proof} Define
\[
\eta_n := \frac{S_n}n - \frac1n \sum_{m=1}^n \CExp{Y_m \indic {\mynorm{\R_m}\le m}}{m-1} + \frac1n \sum_{m=1}^n \csd{m-1}\left(\widetilde{\bH}_{m-1}-\bH\right)\boldsymbol{1}^T.
\]
Since $0\le Y_n\le \mynorm{\R_n}$, using Proposition~\ref{prop: trunc mg}, sum of the first two terms of $\eta_n$ satisfies
\begin{equation}\label{eq: eta two}
  \frac{S_n}n - \frac1n \sum_{m=1}^n \CExp{Y_m \indic {\mynorm{\R_m}\le m}}{m-1} \to 0 \text{ almost surely.}
\end{equation}
The third term of $\eta_n$ is bounded by $\frac1n \sum_{m=1}^n \mynorm{\widetilde{\bH}_{m-1}-\bH}$, which is also negligible almost surely by Assumption~\ref{Assmp: ae}. Thus $\eta_n\to 0$ almost surely. Further, we have
\[
0 < \sigma\left(\bH\right) \leq \left|\frac{S_n}n - \eta_n\right| \leq \mynorm{\bH} < \infty,
\]
which, along with Remark~\ref{Rem: sigma}, proves the result.
\end{proof}

Finally, we show Cesaro negligibility of the error terms $(\bds{\delta}_n)$ and $(\bxi_n)$ of the stochastic approximation equation~\eqref{eq: Mod SA}, as required in Theorem~\ref{Thm: SA}. \begin{lemma} Under Assumptions~{\normalfont \ref{Assmp: basic}} and~{\normalfont \ref{Assmp: unif tail}}, we have, with probability $1$, $\frac1n\sum_{m=1}^n \bds{\delta}_m \to \bds{0}$ and $\frac1n\sum_{m=1}^n \bxi_m \to \bds{0}$.
\end{lemma}
\begin{proof}
Each coordinate of $(\Chi_n\R_n-\csl{n-1}Y_n)$ is bounded by $2\mynorm{\R_n}$. Hence, using Proposition~\ref{prop: trunc mg}, each coordinate of $\frac1n\sum_{m=1}^n \bds{\delta}_m$ is negligible. Further, recall that \[\bxi_n = \csd{n-1}\left(\widetilde{\bH}_{n-1}-\bH\right) - \csd{n-1}\left(\csd{n-1}\left(\widetilde{\bH}_{n-1}-\bH\right)\boldsymbol{1}^T\right).\] Then $\Lone{\bxi_n} \le 2 \mynorm{\widetilde{\bH}_{n-1}-\bH}$, and by Assumption~\ref{Assmp: ae}, the result follows.
\end{proof}

\subsection{Proof of the Main Theorem}
We prove Theorem~\ref{Main} in this Subsection.

\begin{proof}[Proof of Theorem~{\normalfont\ref{Main}}]
Since the relevant conditions of Theorem~\ref{Thm: SA} have been checked for the proportion vector $\left(\C_n/S_n\right)$ in Section~\ref{subsec: analysis}, we have the almost sure convergence of the proportion vector to $\boldsymbol{\pi}_{\bH}$.

Next we consider the almost sure convergence of $S_n/n$. Using~\eqref{eq: eta two}, it is enough to show that
\begin{equation} \label{eq: Cesaro}
\frac{1}n\sum_{m=1}^n\CExp{Y_m\indic {\mynorm{\R_m}\le m}}{m-1}\to\pfval
\end{equation}
almost surely. Recall that
\[\frac{1}{n}\sum_{m=1}^n\CExp{Y_m\indic {\mynorm{\R_m}\le m}}{m-1}\\ = \frac{1}{n}\sum_{m=1}^n\csd{m-1}\left(\widetilde{\bH}_{m-1}-\bH\right)\boldsymbol{1}^T + \frac{1}{n}\sum_{m=1}^n\csd{m-1}\bH\boldsymbol{1}^T.\]
The first term on the right side converges to 0 almost surely by Assumption~\ref{Assmp: ae}. Further, since $\csl{n}\to\lpf$ almost surely, we get
$\left(\C_n/S_n\right)\bH\boldsymbol{1}^T\to\lpf\bH\boldsymbol{1}^T=\pfval\lpf\boldsymbol{1}^T=\pfval$
almost surely and~\eqref{eq: Cesaro} follows using Cesaro. Then, the almost sure limit of $\C_n/n$ follows easily from those of $\C_n/S_n$ and $S_n/n$.

From the almost sure convergence of the proportion vector, $\frac{1}{n}\sum_{m=0}^{n-1}\C_m/S_m \to \lpf$ holds almost surely. Hence, the almost sure limit of $\N_n/n$ will follow from
\[
\frac{\N_n}{n} - \frac{1}{n}\sum_{m=0}^{n-1}\csd{m} = \frac{1}{n}\sum_{m=1}^n\left(\Chi_m-\csd{m-1}\right) \to \boldsymbol{0} \text{ almost surely.}
\]
By Kronecker's Lemma, it is enough to show that $\sum_n\frac{1}{n}\left(\Chi_n-\C_{n-1}/S_{n-1}\right)$ is convergent almost surely, which holds since $\Lone{\Chi_n/n}^2=1/n^2$ is
summable.

Next we consider $L^1$ convergence. Since $\csl{n}$ and $\N_n/n$ are bounded, their almost sure convergence will imply convergence in $L^1$ as well by Dominated Convergence Theorem. If the convergence of $S_n/n$ is shown to hold in $L^1$, then by Lemma~3.5 of \cite{GangoMaulik}, the convergence of $\C_n/n$ will be in $L^1$ as well. So we consider $L^1$ convergence of $S_n/n$.

Observe that, from~\eqref{Y bd}, $0\leq Y_n\leq\mynorm{\R_n}$ for $n\ge 1$ and $Y_0= \C_0 \bds{1}^T$ is integrable by Assumption~\ref{Assmp: basic}\eqref{Assmp: init}. Further, as noted in Remark~\ref{Rem: L1}, Assumption~\ref{Assmp: basic}\eqref{Assmp: maj} or bounded moment condition~\eqref{eq: exp bd} of Assumption~\ref{Assmp: unif tail}\eqref{Assmp: alt tail} implies uniform integrability of $(\mynorm{\R_n})$. Hence $\left( Y_n\right)_{n=0}^\infty$, and thus $S_n/n=\sum_{k=0}^n Y_k/n$ are also uniformly integrable. So the almost sure convergence of $S_n/n$ becomes $L^1$ as well.
\end{proof}

\subsection{Proofs of Corollaries~\ref{cor: iid},~\ref{cor: L log L} and~\ref{cor: phi}}
Since the conclusions of Corollaries~\ref{cor: iid},~\ref{cor: L log L} and~\ref{cor: phi} are same as those of Theorem~\ref{Main}, we check that the assumptions of the corollaries imply those of the theorem.

\begin{proof}[Proof of Corollary~{\normalfont \ref{cor: iid}}]
  Assumption~\ref{Assmp: basic} clearly holds. Assumption~\ref{Assmp: unif tail}\eqref{Assmp: maj} holds as in Remark~\ref{rem: identical}. Further, the i.i.d.\ sequences $(\Chi_n)$ and $(\R_n)$ give Assumption~\ref{Assmp: aeprime}. Also, finite mean of $\mynorm{\R_n}$ implies~\eqref{eq: tail ce neg}. Assumption~\ref{Assmp: ae} then follows from Remark~\ref{Rem: tail ce}.
\end{proof}

Next we consider the other two corollaries.
\begin{proof}[Proof of Corollaries~~{\normalfont\ref{cor: L log L}} and~{\normalfont\ref{cor: phi}}]
Note that Corollaries~\ref{cor: L log L} and~\ref{cor: phi} assume Assumption~\ref{Assmp: basic},~\ref{Assmp: unif tail} and~\ref{Assmp: aeprime}, together with $L \log_+ L$ condition on the majorizing random variable. Hence, using Remark~\ref{Rem: tail ce}, it is enough to check~\eqref{eq: tail ce neg}, which we do next.
\end{proof}

\begin{proposition} \label{prop: suff tail ce}
Assumption~{\normalfont \ref{Assmp: basic}} and either of the following is sufficient for~\eqref{eq: tail ce neg}:
\begin{enumerate}[label={\normalfont (\roman*)},ref={\normalfont \roman*}]
\item Assumption~{\normalfont \ref{Assmp: unif tail}\eqref{Assmp: maj}} and the majorizing variable $R$ satisfies $\Exp(R \log_+R)<\infty$.
\item Assumption~{\normalfont \ref{Assmp: unif tail}\eqref{Assmp: alt tail}}.
\label{Assmp: phi}
\end{enumerate}
\end{proposition}

\begin{proof}
By Kronecker's lemma, it is enough to show
$\sum_{n=1}^{\infty} \frac1n \CExp{\mynorm{\R_{n}}\indic{\mynorm{\R_{n}}>n}}{n-1} < \infty \text{ almost surely}$.
\begin{enumerate}[label={\normalfont (\roman*)},ref={\normalfont \roman*}]
\item We show that the random variable on the left side above has finite expectation. Now, using Assumption~\ref{Assmp: unif tail}\eqref{Assmp: maj}, we have
\begin{align*}
&\sum_{n=1}^{\infty} \frac1n \Exp\left(\mynorm{\R_{n}}\indic{\mynorm{\R_{n}}>n}\right) \leq c\sum_{n=1}^{\infty} \frac1n \Exp\left( R\indic{R>n}\right)\\
&\qquad \qquad \le c \sum_{n=1}^{\infty} \sum_{j=n}^\infty \frac1n \Exp\left( R\indic{R\in (j, j+1]}\right) \le c \sum_{j=1}^{\infty} \Exp\left( R\indic{R\in (j, j+1]}\right) \sum_{n=1}^j \frac1n\\
&\qquad \qquad \le c \sum_{j=1}^{\infty} \Exp\left( R\indic{R\in (j, j+1]} (1+ \log_+ R)\right) \le c \Exp\left( R (1+ \log_+ R)\right) < \infty.
\end{align*}
\item Since $\phi$ is eventually nondecreasing, we have, for some $m$,
\[
\sum_{n=m}^\infty \frac1n \Exp{\mynorm{\R_{n}}\indic{\mynorm{\R_{n}}>n}} \le \sum_{n=m}^\infty \frac1{n \phi(n)} \Exp{\mynorm{\R_{n}}\phi\left(\mynorm{\R_{n}}\right)}
\]
and the result follows from the summability of $1/(n\phi(n))$.
\end{enumerate}
\end{proof}

\section{Applications to Elephant Random Walk} \label{sec:erw}
In this section, we consider the delayed elephant random walk (ERW) on nonnegative integer lattice in dimension $d$ with randomly reinforced memory. The walk was introduced in \cite{ERWoriginal} and has been studied extensively in both statistical physics and literature. We analyze the model using the results obtained in this article utilizing an interesting connection between the urn model and ERW, which was discovered in \cite{Bertoin}.

The location of the walk at the epoch $n$ is denoted by $\bds{L}_n$, while the step taken at that epoch is denoted by $\bds{X}_n$, where $\bds{L}_n = \bds{L}_{n-1} + {\bds{X}_n}$. At every epoch, the step can be a no move or can move unit step along one of the $d$ coordinate axes. The corresponding values of the step are $\bds{e}_0, \bds{e}_1, \ldots, \bds{e}_d$. The walk starts at the origin, i.e., $\bds{L}_0 = \bds{e}_0$. The walk takes the first step $\bds{X}_1$ at random among all the possibilities $\bds{e}_0, \ldots, \bds{e}_d$.

Like an elephant, the walk has memory about all the past steps. At every epoch $n>1$, the walk chooses $\tau_n$, one of the past epochs based on the memories associated with them and the step $\bds{X}_{\tau_n}$, associated with the selected epoch, has its memory reinforced randomly based on its value. The memory at epoch $j$ for the step $\bds{X}_n$ is $M_n^{(j)}$. It starts growing only after the step is taken. Thus $M_n^{(j)}=0$ for $j = 0, 1, \ldots, n-1$. For any $u = 1, \ldots, n-1$, we have $P[ X_{\tau_n} = X_u | \mathcal F_{n-1}] = {M_u^{(n-1)}}/{\left( M_1^{(n-1)}+\cdots+M_{n-1}^{(n-1)}\right)}$, where $\mathcal F_n$ denotes the history up to and including time $n$. The reinforcement is summarized by an i.i.d.\ sequence of random vectors $\left((A_{0n}, A_{1n}, \ldots, A_{dn})\right)_{n\ge 1}$ with nonnegative coordinates and common finite first moments $a$. If the selected step $\bds{X}_{\tau_n} = \bds{e}_i$ for some $i = 0, 1, \ldots, d$, then the associated memory $M_{\tau_n}^{(n-1)}$ is reinforced by $A_{in}$, that is $M_{\tau_n}^{(n)} = M_{\tau_n}^{(n-1)} + A_{in}$. Other memories remain unchanged.

To choose the $n$-th step, $\bds{X}_n$ the model requires two other parameters $p, q \in (0, 1)$ other than the mean memory reinforcement $a$. If the selected step $\bds{X}_{\tau_n}$ is no move, the new step $\bds{X}_n$ is also $\bds{e}_0$ with probability $p$ or one of the directions along the axes with equal probability $(1-p)/d$. If the selected step is a move along a direction $\bds{e}_i$ for some $i = 1, \ldots, d$, then the next step $\bds{X}_n$ is the same step $\bds{e}_i$ with probability $q$ or it is no move, i.e., $\bds{e}_0$ with probability $1-q$. The step $\bds{X}_n$ is chosen independently of the entire past till epoch $(n-1)$, $\tau_n$ and $(A_{0n}, A_{1n}, \ldots, A_{dn})$. Finally, the new step $\bds{X}_n$ is given memory $1$ i.e., $M_n^{(n)} = 1$.

The asymptotic behavior of the ERW above is given by the theorem below.

\begin{theorem} Let us consider a delayed elephant random walk on the positive orthant in dimension $d$ with random reinforcement of memory, parametrized by $a$, $p$ and $q$ as described above. Then the location $\bds{L}_n$ at epoch $n$ grows linearly and
$$\frac1n \bds{L}_n \to \frac{1}{d(1-q+a(1-p))} (a(1-p), \ldots, a(1-p)) \quad \text{almost surely and in $L^1$.}$$
\end{theorem}
\begin{proof} We use the connection between ERW and urn model established in \cite{Bertoin}. We consider the memory vector of each type of step at epoch $n$, denoted by $\boldsymbol{W}^{(n)}:=(W_0^{(n)}, \ldots, W_d^{(n)})$, where, for $i = 0, 1, \ldots, d$, we have $W_i^{(n)}:=\sum_{k\leq n} M_k^{(n)}\indic{\bds{X}_k=\bds{e}_i}.$ Every time a step is taken, memory of the type corresponding to the selected past epoch is increased by the random reinforcement. Further, memory of the type corresponding to the new step is increased by 1. Thus $\left(\boldsymbol{W}^{(n)}\right)_{n\geq 0}$ behaves as an urn model of $(d+1)$ types (indexed by $0, 1, \ldots, d$) with i.i.d.\ replacement matrix sequence and mean replacement matrix
\[ \R =
\begin{pmatrix}
  1+pa & (1-p)\frac{a}{d} & \cdots & (1-p)\frac{a}{d}\\
  1-q & q+a & \cdots & q+a\\
  \vdots & \vdots & \ddots & \vdots\\
  1-q & q+a & \cdots & q+a
\end{pmatrix}.\]
Clearly, the dominant eigenvalue of $\R$ is $(1+a)$ and the corresponding left eigenvector normalized to probability is
\[\frac{1}{d(1-q+a(1-p))} \left( d(1-q), a(1-p), \ldots, a(1-p)\right).\]

Finally, note that, for $i = 1, \ldots, d$,
\[W_i^{(n)}=\sum_{k=1}^{n} \left( 1 + \sum_{l=k+1}^n A_{il} \indic{\tau_l = k} \right) \indic{\bds{X}_k=\bds{e}_i} = \bds{L}_{ni} + a \sum_{l=1}^n \indic{\bds{X}_{\tau_l}=\bds{e}_i} + \sum_{l=1}^n (A_{il}-a) \indic{\bds{X}_{\tau_l}=\bds{e}_i}.\] By Corollary~\ref{cor: iid}, we have, for the composition vector, $W_i^{(n)}/n \to (1+a) {a(1-p)}/(d(1-q+a(1-p)))$ and, for the count vector, $\sum_{l=1}^n \indic{\bds{X}_{\tau_l}=\bds{e}_i}/n \to {a(1-p)}/(d(1-q+a(1-p)))$. Finally, the last term on the right is a sum of martingale differences, which are dominated by $(A_{il}+a)$, and hence, by Proposition~\ref{prop: mg SLLN}, the last term scaled by $n$ converges to 0 almost surely. Combining the result follows.
\end{proof}

\section*{Acknowledgment}
The research of the second author was partly supported by MATRICS grant number MTR/2019/001448 from SERB, Govt.\ of India.

\providecommand{\bysame}{\leavevmode\hbox to3em{\hrulefill}\thinspace}
\providecommand{\MR}{\relax\ifhmode\unskip\space\fi MR }
\providecommand{\MRhref}[2]{%
  \href{http://www.ams.org/mathscinet-getitem?mr=#1}{#2}
}
\providecommand{\href}[2]{#2}
