\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\begin{center}
\vskip 1cm{\LARGE\bf A Restricted Random Walk defined\\ \vskip .14in
via a Fibonacci Process}
\vskip 1cm
\large
Martin Griffiths\\
School of Education\\
University of Manchester\\
Manchester\\
M13 9PL\\
United Kingdom\\
\url{martin.griffiths@manchester.ac.uk}
\end{center}

\begin{abstract}
In this article we study a random walk on a particularly simple graph.
This walk is determined by a probabilistic process associated with the
Fibonacci sequence.  Exact formulas are derived for the expected
proportions of time spent on each arc of the graph for a walk of length
$n$, giving rise to sequences that do not appear in Sloane's
\textit{On-Line Encyclopedia of Integer Sequences}.  We also obtain
asymptotic relations for these expected proportions.
\end{abstract}

\section{Introduction}\label{section1}
A one-dimensional random walk on the integers $\mathbb{Z}$ might typically be regarded as a process defined by a sequence of random variables $\left\{U_n\right\}$, the $n$th term of which is given by
\[U_n=U_0+\sum_{k=1}^n V_k,\]
where $U_0\in\mathbb{Z}$ is the starting position and $\left\{V_n\right\}$ is a sequence of independent random variables, each term of which takes only values in $\{1,-1\}$.  If the terms in $\left\{V_n\right\}$ are also identically distributed, so that $\textup{P}\left(V_k=1\right)=p$ and $\textup{P}\left(V_k=-1\right)=1-p$ for each $k\in\mathbb{N}$, where $p$ is a fixed number satisfying $0<p<1$, then $\left\{U_n\right\}$ is termed a \textit{simple} random walk.  The mathematics of simple random walks on $\mathbb{Z}$ has been studied extensively, and further details are to be found in \cite{feller,grimmett}.

It is also possible to consider one-dimensional random walks having either absorbing or retaining barriers.  An example of the former is known as `gamblers ruin'; see \cite{grimmett}.  In this case the random walk would start at a point $m$, where $0<m<N$ for some $N\geq2$, and at each stage the outcome of tossing a fair coin would decide whether the walk proceeded to the left or to the right.  The walk would terminate if it reached either 0 or $N$.  If, on the other hand, the random walk has retaining barriers, then instead of stopping once 0 or $N$ is reached, the next point on the walk would be 1 or $N-1$, respectively (the barriers might thus also be thought of as `reflecting' in this case).  Note that those having either absorbing or retaining barriers might be regarded as restricted random walks.  Furthermore, other than at the barriers, these behave as simple random walks.

The particular random walks we consider here have retaining barriers but are not, in the sense described in the opening paragraph, simple.  As opposed to the act of tossing a fair coin at each stage, the walks are determined by a probabilistic process associated with the Fibonacci sequence in which the probabilities do not remain constant.  The reason for this will become apparent in due course.  Also, since we are interested in the paths generated by the walks, we consider them to take place on a graph.

Consider the graph below, which we denote by $\mathcal{G}$.  A \textit{walk} $\mathfrak{W}$ of length $n$ on $\mathcal{G}$ comprises an ordered sequence of $n+1$ adjacent nodes, starting at node 1.  The ordered sequence of $n$ arcs traversed whilst undertaking $\mathfrak{W}$ is called a \textit{path} in $\mathcal{G}$ of length $n$.  To take an example, the walk $(1,2,3,2,3,4,3,2,1,2)$ gives rise to the path $ABBBCCBAA$ of length 9.

\begin{figure}[!h]
\centering
\setlength{\unitlength}{2.5cm}
\begin{picture}(4,1.0)(0.1,0.1)

\put(0.1,0.5){\circle{0.3}}
\put(0.07,0.46){1}
\put(0.25,0.5){\line(1,0){1}}

\put(0.72,0.62){$A$}

\put(1.4,0.5){\circle{0.3}}
\put(1.37,0.46){2}
\put(1.55,0.5){\line(1,0){1}}

\put(2.02,0.62){$B$}

\put(2.7,0.5){\circle{0.3}}
\put(2.67,0.46){3}
\put(2.85,0.5){\line(1,0){1}}

\put(3.32,0.62){$C$}

\put(4.0,0.5){\circle{0.3}}
\put(3.97,0.46){4}

\end{picture}
\end{figure}

\noindent  Since the Fibonacci numbers play a major role in our work here, before describing how they are used to generate random walks on $\mathcal{G}$ we provide a definition of the Fibonacci sequence.

\begin{definition}
The $n$th term of the \textit{Fibonacci sequence} $F_n$ is defined by
the recurrence relation $F_n=F_{n-1}+F_{n-2}$, $n\in\mathbb{N}$, where
$F_{-1}=1$ and $F_0=0$; note that we index the Fibonacci numbers here
from $-1$ simply out of mathematical convenience (the need for this
will become apparent in later sections of this paper).  The sequence
$\left\{F_n\right\}$ appears in Sloane's \textit{On-Line Encyclopedia
of Integer Sequences} as \seqnum{A000045} \cite{sloane}.  For further details
regarding the Fibonacci numbers, see \cite{burton,cameron,knuth}.
\end{definition}

We start the random walk at node 1 with $F_{n+1}$ green discs, and carry them with us to node 2.  Once at node 2, $F_{n-1}$ of these discs are painted red.  A disc is then chosen at random.  If the disc is red we proceed to node 1, carrying the $F_{n-1}$ red discs with us.  Otherwise, we take the $F_{n+1}-F_{n-1}=F_{n}$ green discs with us to node 3.  In the former case we continue simply by carrying the $F_{n-1}$ red discs to node 2, while in the latter case we paint $F_{n-2}$ of the green discs red, and choose one of the discs at random.  If the disc is green we proceed to node 2 but if it is red we go to node 4.  This process continues until a path of length $n$ has been achieved, and may be formalized as follows:
\begin{enumerate}
\item [(i)]  If at node 1 or node 4 then carry the discs to the next node.
\item [(ii)]  If at node 2(3) with $F_k$ green discs then paint $F_{k-2}$ of them red and choose one at random.  If the disc is green then take the $F_{k-1}$ green discs to node 3(2).  Otherwise, take the $F_{k-2}$ red discs to node 1(4).
\item [(iii)]  If at node 2(3) with $F_k$ red discs then paint $F_{k-1}$ of them green and choose one at random.  If the disc is green then take the $F_{k-1}$ green discs to node 3(2).  Otherwise, take the $F_{k-2}$ red discs to node 1(4).
\item [(iv)]  The process stops once the path length has reached $n$.
\end{enumerate}
\noindent We see, in Figure \ref{fig1}, the probability tree that results on considering this process for the case
$n=4$.

\begin{figure}[!h]
\centering
\setlength{\unitlength}{2.5cm}
\begin{picture}(4.0,3.0)(0.8,0.7)

\put(0.07,2.2){$1$}
\put(0.19,2.25){\line(1,0){0.8}}

\put(1.1,2.2){$2$}
\put(1.3,2.3){\line(5,3){1.0}}
\put(1.3,2.23){\line(5,-3){1.0}}

\put(2.4,2.85){$1$}
\put(2.55,2.92){\line(5,1){1.0}}

\put(2.4,1.56){$3$}
\put(2.55,1.66){\line(5,2){1.0}}
\put(2.55,1.59){\line(5,-2){1.0}}

\put(3.65,3.07){$2$}
\put(3.8,3.15){\line(5,1){1.0}}
\put(3.8,3.08){\line(5,-1){1.0}}

\put(3.65,2.02){$2$}
\put(3.8,2.1){\line(5,1){1.0}}
\put(3.8,2.03){\line(5,-1){1.0}}

\put(3.65,1.13){$4$}
\put(3.8,1.2){\line(5,0){1.0}}

\put(4.9,3.3){$1$}
\put(4.9,2.83){$3$}
\put(4.9,2.25){$1$}
\put(4.9,1.76){$3$}
\put(4.9,1.13){$3$}

\put(0.55,2.35){$\tfrac{5}{5}$}
\put(1.7,2.72){$\tfrac{2}{5}$}
\put(1.7,1.75){$\tfrac{3}{5}$}
\put(3.05,3.15){$\tfrac{2}{2}$}
\put(3.05,2.0){$\tfrac{2}{3}$}
\put(3.05,1.15){$\tfrac{1}{3}$}
\put(4.3,3.37){$\tfrac{1}{2}$}
\put(4.3,2.77){$\tfrac{1}{2}$}
\put(4.3,2.32){$\tfrac{1}{2}$}
\put(4.3,1.72){$\tfrac{1}{2}$}
\put(4.3,1.0){$\tfrac{1}{1}$}

\end{picture}
\caption{A probability tree for the case $n=4$.}\label{fig1}
\end{figure}

The aim of this paper is to determine, for any given $n\in\mathbb{N}$, the expected proportions of time spent on each of the three arcs during a random walk of length $n$ on $\mathcal{G}$, where it is to be assumed that the time taken to get from one node to the next remains constant during the walk.  The scenario considered here is related to one given in \cite{griffiths}, although the resulting mathematics turns out to be considerably more complicated.  Furthermore, no probabilistic aspects were taken account of in \cite{griffiths}.

Before obtaining several useful results in connection with our problem, we define some notation that will be used in due course.  Let $S(n)$ be the set of all possible paths in $\mathcal{G}$ of length $n$.  Suppose all the elements of $S(n)$ are placed in lexicographical order.  Then $P_j(n)$ represents the $j$th path, $1\leq j\leq|S(n)|$, under this ordering.  We use $M_n$ to denote the $|S(n)|\times n$ matrix, the element $m_{i,j}(n)$ of which is defined to be the $j$th letter of $P_i(n)$.  Two examples, $M_5$ and $M_6$, are shown in Table \ref{matrices}.  In addition, we use $r_j(n)$ and $c_k(n)$ to refer to the $j$th row and $k$th column of $M_n$, respectively.

\begin{table}[h!]
\begin{equation*}
M_5=
\left(
\begin{array}{ccccc}
A & A & A & A & A \\
A & A & A & B & B \\
A&A&A&B&C\\
A&B&B&A&A\\
A&B&B&B&B\\
A&B&B&B&C\\
A&B&C&C&B\\
A&B&C&C&C
\end{array}\right),\,\,\,\,\,
M_6=
\left(
\begin{array}{cccccc}
A & A & A & A & A &A \\
A & A & A & A & A &B \\
A&A&A&B&B&A\\
A&A&A&B&B&B\\
A&A&A&B&C&C\\
A&B&B&A&A&A\\
A&B&B&A&A&B\\
A&B&B&B&B&A\\
A&B&B&B&B&B\\
A&B&B&B&C&C\\
A&B&C&C&B&A\\
A&B&C&C&B&B\\
A&B&C&C&C&C\\
\end{array}\right).
\end{equation*}\label{matrices}
\caption{The matrices $M_5$ and $M_6$.}
\end{table}


\section{Some structural results concerning $M_n$}\label{sectionstructural}
\begin{definition}
  Let $P$ be a path in $\mathcal{G}$ having length $n$ and ending in $A$.  If $P$ arises from the walk $\mathfrak{W}$ then $s(A,n)$ denotes the set of arcs emanating from the final node of $\mathfrak{W}$.  We term $s(A,n)$ the \textit{successor set} of $P$ since it provides us with information on how $P$ may be extended by one arc.  Corresponding definitions follow for paths ending in $B$ and $C$, respectively.
\end{definition}

Note that $s(A,n)$, $s(B,n)$ and $s(C,n)$ are each well-defined since $n$ will always be even if $\mathfrak{W}$ finishes at node 1 or node 3, but odd if $\mathfrak{W}$ finishes at node 2 or node 4.  It is in fact clear that $s(A,2k-1)=\{a,b\}$, $s(A,2k)=\{a\}$, $s(B,2k-1)=\{a,b\}$, $s(B,2k)=\{b,c\}$, $s(C,2k-1)=\{c\}$ and $s(C,2k)=\{b,c\}$.

As was alluded to earlier, it transpires that the Fibonacci numbers feature strongly in both the structural and combinatorial aspects of $M_n$.  In connection with this, it is, as we shall see, judicious to consider particular sections of the columns of $M_n$, defined as follows:

\begin{definition}
 A \textit{block} of $A$s of length $q\geq 1$ in the $k$th column of $M_n$ is defined to be a series of entries such that $m_{p,k}(n)= m_{p+1,k}(n)=\ldots=m_{p+q-1,k}(n)=A$ for some $p,q\in\mathbb{N}$ such that either $p=1$ or $m_{p-1,k}(n)\neq A$ and either $p+q-1=|S(n)|$ or $m_{p+q,k}(n)\neq A$.  Corresponding definitions apply for blocks consisting of $B$s and $C$s.
\end{definition}

In the lemma below it is shown that for each block in $M_n$ the corresponding series of entries in $c_n(n)$ consist of singleton blocks of $A$s, $B$s and $C$s.  The following definition eases the notation somewhat in this regard.

\begin{definition}
  For any block $X$ in $M_n$, $X\left[p,q,r\right]$ denotes that the corresponding section of $c_n(n)$ comprises $p$, $q$ and $r$ singleton blocks of $A$s, $B$s and $C$s respectively.
\end{definition}

\begin{lemma}\label{structurelemma}
For any $k$ with $1\leq k\leq n$ there are $F_{k+1}$ blocks in $c_k(n)$.  The length of any block $Y$ of $B$s is of the form $F_j$, $j\geq 2$.  If $n$ is odd then $Y\left[F_{j-3},F_{j-2},F_{j-2}\right]$, while if $n$ is even then $Y\left[F_{j-2},F_{j-2},F_{j-3}\right]$.

If $n$ is odd then the length of any block $X$ of $A$s is of the form $F_{2j}$, $j\geq 1$.  In this case $X\left[F_{2j-3},F_{2j-2},F_{2j-2}\right]$.  On the other hand, if $n$ is even then the length of any block $X$ of $A$s is of the form $F_{2j-1}$, $j\geq 2$, and $X\left[F_{2j-3},F_{2j-3},F_{2j-4}\right]$ so long as $X$ is not in $c_n(n)$.  If $X$ is in $c_n(n)$ then $X[1,0,0]$.

Finally, if $n$ is odd then the length of any block $Z$ of $C$s is of the form $F_{2j-1}$, $j\geq 2$, and $Z\left[F_{2j-4},F_{2j-3},F_{2j-3}\right]$ so long as $X$ is not in $c_n(n)$. If $Z$ is in $c_n(n)$ then $Z[0,0,1]$.  If $n$ is even then the length of any block $Z$ of $C$s is of the form $F_{2j}$, $j\geq 1$, and $Z\left[F_{2j-2},F_{2j-2},F_{2j-3}\right]$.
\end{lemma}

\begin{proof}
Let $T(n)$ denote the statement of the lemma.  We proceed by induction on $n$.  It is easily checked that both $T(1)$ and $T(2)$ are true.  Now assume that $T(n)$ is true for some $n\geq2$.  Let us consider a particular block $X$ of $A$s in $c_k(n)$ for some $k$ such that $1\leq k\leq n$.  Suppose first that $n$ is odd.  By the inductive hypothesis $X$ has length $F_{2j}$ for some $j\in\mathbb{N}$, and $X\left[F_{2j-3},F_{2j-2},F_{2j-2}\right]$.  It is clear, on considering both the lexicographical ordering and the successor sets when $n$ is odd, that $X$ gives rise to a corresponding block $W$ in $c_k(n+1)$ of length $F_{2j}+F_{2j-3}+F_{2j-2}=F_{2j+1}$; the number of blocks in $c_k(n+1)$ is therefore $F_{k+1}$, the same number as in $c_k(n)$.  Furthermore, the section corresponding to $W$ in $c_{n+1}(n+1)$ comprises $F_{2j-3}+F_{2j-2}=F_{2j-1}$ singleton blocks of $A$s, $F_{2j-3}+F_{2j-2}=F_{2j-1}$ singleton blocks of $B$s and $F_{2j-2}$ singleton blocks of $C$s.

Suppose now that $n$ is even.  Using the inductive hypothesis once more, $X$ has length $F_{2j-1}$ for some $j\in\mathbb{N}$, and $X\left[F_{2j-3},F_{2j-3},F_{2j-4}\right]$ unless $X$ is in $c_n(n)$.   If $X$ is not in $c_n(n)$ then, by considering both the lexicographical ordering and the successor sets when $n$ is even, we see that $X$ gives rise to a corresponding block $W$ in $c_k(n+1)$ of length $F_{2j-1}+F_{2j-3}+F_{2j-4}=F_{2j}$.  Also, the section corresponding to $W$ in $c_{n+1}(n+1)$ comprises $F_{2j-3}$ singleton blocks of $A$s, $F_{2j-3}+F_{2j-4}=F_{2j-2}$ singleton blocks of $B$s and $F_{2j-3}+F_{2j-4}=F_{2j-2}$ singleton blocks of $C$s.  If, on the other hand, $X$ is in $c_n(n)$ then $X[1,0,0]$.  Note that, since $n$ is even, $X$ gives rise to a corresponding block $W$ in $c_{n+1}(n+1)$ consisting simply of one $A$.  As a block in $M_{n+1}$ this may be written as $W\left[F_{-1},F_0,F_0\right]$, which is equal to $W\left[F_{2j-3},F_{2j-2},F_{2j-2}\right]$ for $j=1$.

By continuing in this manner for all the remaining cases, the proof of the lemma follows by the principle of mathematical induction.
\end{proof}

\begin{corollary}\label{rowcorollary}
\[|S(n)|=F_{n+1}.\]
\end{corollary}

\begin{proof}
First, it is clear that $c_1(n)$ comprises simply a block of $A$s.  Thus, from Lemma \ref{structurelemma}, we know that $c_n(n)$ consists solely of singletons.  However, Lemma \ref{structurelemma} also tells us that there are $F_{n+1}$ blocks in $c_n(n)$, thereby proving the corollary.
\end{proof}

\begin{lemma}\label{blocklemma}
In $c_k(n)$, $1\leq k\leq n$, there are
\begin{enumerate}
\item [(i)] $F_{2\left\lfloor\frac{k}{2}\right\rfloor-1}$ blocks of $A$ of length $F_{n+1-2\left\lfloor\frac{k}{2}\right\rfloor}$ for $k\geq 1$,
\item [(ii)] $F_{k-1}$ blocks of $B$ of length $F_{n+2-k}$ for $k\geq 2$,
\item [(iii)] $F_{2\left\lfloor\frac{k-1}{2}\right\rfloor}$ blocks of $C$ of length $F_{n-2\left\lfloor\frac{k-1}{2}\right\rfloor}$ for $k\geq 3$,
\end{enumerate}
where $\lfloor x\rfloor$ is the floor function, denoting the largest integer not exceeding $x$.
\end{lemma}

\begin{proof}
Each of these results may be proved by induction on $n$.  First, it is a straightforward matter to show that (i) is true when $n=1$.  Now assume that this result is true for all $k$ such that $1\leq k\leq n$ for some $n\geq 1$.  Let us consider $M_{n+1}$.  We know, from Lemma \ref{structurelemma}, that the number of blocks of $A$ in $c_k(n+1)$ is, for any fixed $k$ with $1\leq k\leq n$, the same as the number of blocks of $A$ in $c_k(n)$.  Lemma \ref{structurelemma} also tells us that any block of $A$s of length $F_m$ in $c_k(n)$ has a corresponding block of length $F_{m+1}$ in $c_k(n+1)$.  It just remains therefore to show that (i) is true for $c_{n+1}(n+1)$.  Suppose that $n+1$ is odd.  We know both that $c_{n+1}(n+1)$ consists solely of singletons and that, taking $X$ as $c_1(n+1)$, $X\left[F_{2j-3},F_{2j-2},F_{2j-2}\right]$ for some $j\in\mathbb{N}$.  Since $c_{n+1}(n+1)$ has $F_{n+2}$ singletons, the number of blocks of $A$ in $c_{n+1}(n+1)$ must be $F_{n-1}$.  When $n+1$ is odd then
\[2\left\lfloor\frac{n+1}{2}\right\rfloor=n,\]
in which case, with $k=n+1$,
\[F_{2\left\lfloor\frac{k}{2}\right\rfloor-1}=F_{n-1}\]
and
\[F_{(n+1)+1-2\left\lfloor\frac{k}{2}\right\rfloor}=F_2=1,\]
thereby showing that (i) is true in this case.  The argument for when $n+1$ is even proceeds in a similar manner.  It is possible also to show, adopting the above approach, that both (ii) and (iii) are true.
\end{proof}

\section{Exact formulas}

We utilize here results from Section \ref{sectionstructural} in order to determine, for any given $n\in\mathbb{N}$, the expected proportions of time spent on each of the three arcs during a random walk of length $n$ on $\mathcal{G}$.  Before doing so, however, let us consider what might be regarded as the most obvious way to define a random walk on $\mathcal{G}$.  Note first that when at node 1 we are forced next to visit node 2.  Similarly, when at node 4 then 3 is necessarily the next node in the walk.  Suppose, however, that when we are at node 2 or node 3, the next node to be visited is decided by the outcome of tossing a fair coin.  Thus, with $\textup{P}(2\rightarrow 1)$ denoting the probability that the next node will be 1 given that we are currently at node 2, it is the case that $\textup{P}(2\rightarrow 1)=\frac{1}{2}$.  In fact, on extending this notation in an obvious way, we have
\[\textup{P}(2\rightarrow 1)=\textup{P}(2\rightarrow 3)=\textup{P}(3\rightarrow 2)=\textup{P}(3\rightarrow 4)=\frac{1}{2}.\]
Thus, other than at the barriers, this might be regarded as a simple random walk.  An important point to make here with respect to this scenario is that, for a particular choice of $n$, it is not necessarily the case that all paths of length $n$ are equally likely.  When $n=3$, for example,
\[\textup{P}(AAA)=\textup{P}(1\rightarrow 2)\textup{P}(2\rightarrow 1)\textup{P}(1\rightarrow 2)
=1\times\frac{1}{2}\times 1=\frac{1}{2},\]
while
\[\textup{P}(ABB)=\textup{P}(1\rightarrow 2)\textup{P}(2\rightarrow 3)\textup{P}(3\rightarrow 2)
=1\times\frac{1}{2}\times \frac{1}{2}=\frac{1}{4}.\]
This means, in general, that the proportion of $A$s in $M_n$ does not give the expected proportion of time spent on $A$s during a random walk of length $n$, and similarly for $B$s and $C$s.

However, for the Fibonacci process described in Section \ref{section1} it is in fact true that all possible paths of length $n$ are equally likely, and we have
\[\textup{P}\left(P_j(n)\right)=\frac{1}{F_{n+1}}\]
for each $j$ with $1\leq j\leq F_{n+1}$.  To see that this is indeed true, we may consider the resulting probability tree for some fixed value of $n$.  Choose any set of $n$ branches that form a connected path through the tree.  From the way that the tree is constructed, it follows that the product of the probabilities on the leftmost $k$ branches is, for $k\geq 2$, given by
\[\frac{F_{n+1-k}}{F_{n+1}}\qquad\textup{or}\qquad\frac{F_{n+2-k}}{F_{n+1}}.\]
This means that in order to obtain the expected proportions of time spent on each of the three arcs during a random walk of length $n$ on $\mathcal{G}$, it remains to calculate the number of $A$s, $B$s and $C$s in $M_n$.

\begin{definition}
We use $N_n(A)$, $N_n(B)$ and $N_n(C)$ to denote the multiplicities of $A$s, $B$s and $C$s in $M_n$, respectively.  Furthermore, let $N_n=N_n(A)+N_n(B)+N_n(C)$, the total number of entries in $M_n$.  Corollary \ref{rowcorollary} implies that $N_n=nF_{n+1}$.  The sequence $\left\{nF_{n+1}\right\}$ appears in \cite{sloane} as \seqnum{A023607}.
\end{definition}

\begin{theorem}\label{bformula}
\[N_n(B)=\frac{1}{5}\left(nF_{n+1}+(2n-3)F_n\right).\]
\end{theorem}

\begin{proof}
From Lemma \ref{blocklemma}, we know that
\begin{align*}
N_n(B)
&=\sum_{k=2}^n F_{k-1}F_{n+2-k}\\
&=\sum_{k=0}^{n+1} F_kF_{n+1-k}-F_n.
\end{align*}
The sum on the right is the well-known Fibonacci convolution, which, using a result from \cite{graham,knuth}, gives
\begin{align*}
N_n(B)
&=\frac{1}{5}\left(nF_{n+1}+2(n+1)F_n\right)-F_n\\
&=\frac{1}{5}\left(nF_{n+1}+(2n-3)F_n\right).
\end{align*}
\end{proof}

\begin{theorem}\label{aformula}
\[N_n(A)=\frac{1}{5}\left((n+4)F_n+2nF_{n-1}+5F_{2\left\lfloor\frac{n}{2}\right\rfloor}\right).\]
\end{theorem}

\begin{proof}
By Lemma \ref{blocklemma} the total number of $A$s in $M_n$ is given by
\begin{equation}\label{asum}
\sum_{k=1}^n F_{2\left\lfloor\frac{k}{2}\right\rfloor-1}F_{n+1-2\left\lfloor\frac{k}{2}\right\rfloor}.
\end{equation}
For even $n$ this may be written as
\begin{align}\label{intresult}
F_{-1}F_{n+1}+2F_1F_{n-1}+&2F_3F_{n-3}+\ldots+2F_{n-3}F_3+F_{n-1}F_1\nonumber\\
&=F_{n+1}+2\left(F_1F_{n-1}+F_3F_{n-3}+\ldots+F_{n-1}F_1\right)-F_{n-1}\nonumber\\
&=F_n+2\left(F_1F_{n-1}+F_3F_{n-3}+\ldots+F_{n-1}F_1\right).
\end{align}
We now calculate the generating function $U_{even}(x)$ for the sum
\[F_1F_{n-1}+F_3F_{n-3}+\ldots+F_{n-1}F_1,\]
which might be regarded as a `stretched' convolution.

First, let $G(x)$ be the ordinary generating function for the Fibonacci numbers.  Then from \cite{knuth} we know that
\begin{align*}
G(x)
&=F_1x+F_2x^2+F_3x^3+\ldots\\
&=\frac{x}{1-x-x^2}\\
&=\frac{1}{\sqrt{5}}\left(\frac{1}{1-\phi x}-\frac{1}{1-\hat{\phi}x}\right),
\end{align*}
where
\[\phi=\frac{1+\sqrt{5}}{2}\qquad\textup{and}\qquad\hat{\phi}=\frac{1-\sqrt{5}}{2}.\]
Now, noting that
\begin{align*}
F_1x+F_3x^3+F_5x^5+\ldots
&=\frac{1}{2}\left(G(x)-G(-x)\right)\\
&=\frac{1}{2\sqrt{5}}\left(\frac{1}{1-\phi x}-\frac{1}{1-\hat{\phi}x}\right)-\frac{1}{2\sqrt{5}}\left(\frac{1}{1+\phi x}-\frac{1}{1+\hat{\phi}x}\right)\\
&=\frac{x}{\sqrt{5}}\left(\frac{\phi}{1-\phi^2 x^2}-\frac{\hat{\phi}}{1-\hat{\phi}^2x^2}\right),
\end{align*}
we see that
\begin{align}\label{genfuncforAodd}
U_{even}(x)
&=\left(F_1+F_3x+F_5x^2+\ldots\right)^2\nonumber\\
&=\frac{1}{5}\left(\frac{\phi}{1-\phi^2 x}-\frac{\hat{\phi}}{1-\hat{\phi}^2x}\right)^2.
\end{align}
The right-hand side of (\ref{genfuncforAodd}) is multiplied out and then, employing the method of partial fractions, written as
\begin{equation}\label{multipliedout}
U_{even}(x)=\frac{1}{5}\left[\left(\frac{\phi}{1-\phi^2 x}\right)^2+\left(\frac{\hat{\phi}}{1-\hat{\phi}^2x}\right)^2\right]+
\frac{2}{5\sqrt{5}}\left[\frac{\phi^2}{1-\phi^2 x}-\frac{\hat{\phi}^2}{1-\hat{\phi}^2x}\right].
\end{equation}
This may be expanded as a power series in $x$.  Subsequently, on comparing coefficients on both sides of (\ref{multipliedout}) and using the well-known results
\[F_n=\frac{1}{\sqrt{5}}\left(\phi^n-\hat{\phi}^n\right)\quad\textup{and}\quad F_n+2F_{n-1}=\phi^n+\hat{\phi}^n,\]
which may be found in \cite{burton,knuth}, it can be shown that
\[F_1F_{n-1}+F_3F_{n-3}+\ldots+F_{n-1}F_1=\frac{1}{10}\left(4(n+2)F_{n-2}+(3n+4)F_{n-3}\right).\]
Then, on setting $n=2m$ and using (\ref{intresult}), we obtain
\begin{equation}\label{evenformula}
N_{2m}(A)=\frac{1}{5}\left((2m+9)F_{2m}+4mF_{2m-1}\right).
\end{equation}

For odd $n$ we can write (\ref{asum}) as
\begin{align*}
F_{-1}F_{n+1}+2F_1F_{n-1}+&2F_3F_{n-3}+\ldots+2F_{n-2}F_2\\
&=F_{n+1}+2\left(F_1F_{n-1}+F_3F_{n-3}+\ldots+F_{n-2}F_2\right)
\end{align*}
and then calculate the generating function
\[U_{odd}(x)=\left(F_1+F_3x+F_5x^2+\ldots\right)\left(F_0+F_2x+F_4x^2+\ldots\right)\]
for the sum
\[F_1F_{n-1}+F_3F_{n-3}+\ldots+F_{n-2}F_2,\]
which is another `stretched' convolution.  This leads, on using the result
\[F_0+F_2x^2+F_4x^4+\ldots=\frac{1}{2}\left(G(x)+G(-x)\right),\]
to
\[N_{2m-1}(A)=\frac{1}{5}\left((4m+3)F_{2m}-2mF_{2m-1}\right),\]
which can be rearranged to give
\begin{equation}\label{oddformula}
N_{2m-1}(A)=\frac{1}{5}\left(((2m-1)+4)F_{2m-1}+(2(2m-1)+5)F_{(2m-1)-1}\right).
\end{equation}
From (\ref{evenformula}) and (\ref{oddformula}) we see that
\[N_{n}(A)=\frac{1}{5}\left((n+9)F_{n}+2nF_{n-1}\right).\]
and
\[N_{n}(A)=\frac{1}{5}\left((n+4)F_{n}+(2n+5)F_{n-1}\right)\]
for $n$ even and odd, respectively, thereby completing the proof of the theorem.
\end{proof}

Now, since $N_n=N_n(A)+N_n(B)+N_n(C)=nF_{n+1}$, we may easily obtain, using Theorems \ref{bformula} and \ref{aformula}, the results
\[N_{2m-1}(C)=\frac{1}{5}\left(((2m-1)-1)F_{2m-1}-(2(2m-1)-5)F_{(2m-1)-1}\right)\]
 and
\[N_{2m}(C)= \frac{1}{5}\left((2m-6)F_{2m}+4mF_{2m-1}\right).\]
From this it may be seen that
\[N_n(C)=\frac{1}{5}\left((n-1)F_n+2nF_{n-1}-5F_{2\left\lfloor\frac{n}{2}\right\rfloor}\right).\]

Thus, for a path of length $n$, exact formulas for the expected proportions of time spent traveling along arcs $A$, $B$ and $C$ are given by
\[\frac{(n+4)F_n+2nF_{n-1}+5F_{2\left\lfloor\frac{n}{2}\right\rfloor}}{5nF_{n+1}},\]
\[\frac{nF_{n+1}+(2n-3)F_n}{5nF_{n+1}}\]
and
\[\frac{(n-1)F_n+2nF_{n-1}-5F_{2\left\lfloor\frac{n}{2}\right\rfloor}}{5nF_{n+1}},\]
respectively.  We note that neither $\left\{N_n(A)\right\}$ nor $\left\{N_n(C)\right\}$ appears in \cite{sloane}.  However, $\left\{N_n(B)\right\}$ is to be found there as \seqnum{A023610}, a Fibonacci convolution.

\section{Asymptotic results}
Using the fact  that $F_n$ is equal to the nearest integer to $\phi^n/\sqrt{5}$ (see \cite{knuth}), we have
\begin{align*}
N_n(A)
&=\frac{1}{5}\left((n+4)F_n+2nF_{n-1}+5F_{2\left\lfloor\frac{n}{2}\right\rfloor}\right)\\
&\sim\frac{1}{5}\left(\frac{n\phi^n}{\sqrt{5}}+\frac{2n\phi^{n-1}}{\sqrt{5}}\right)\\
&=\frac{n\phi^{n-1}}{5\sqrt{5}}\left(\phi+2\right).
\end{align*}
Likewise, it is straightforward to show that
\[N_n(B)\sim\frac{n\phi^n}{5\sqrt{5}}\left(\phi+2\right)\qquad\textup{and}\qquad
N_{n}(C)\sim\frac{n\phi^{n-1}}{5\sqrt{5}}\left(\phi+2\right).\]
Therefore
\[\lim_{n\rightarrow\infty}\frac{N_{n}(A)}{N_{n}(B)}=\lim_{n\rightarrow\infty}\frac{N_{n}(C)}{N_{n}(B)}
=\frac{1}{\phi}=\phi-1,\]
from which we see that
\[\lim_{n\rightarrow\infty}\frac{N_n(B)}{N_n}=\frac{1}{2\phi-1}\]
and
\[\lim_{n\rightarrow\infty}\frac{N_n(A)}{N_n}
=\lim_{n\rightarrow\infty}\frac{N_n(C)}{N_n}=\frac{\phi-1}{2\phi-1}=\frac{1}{\phi+2}.\]

\begin{thebibliography}{99}
\bibitem{burton} D. M. Burton.  \textit{Elementary Number Theory}.  McGraw-Hill, 1998.
\bibitem{cameron}  P. J. Cameron.  \textit{Combinatorics: Topics, Techniques, Algorithms}.  Cambridge University Press, 1994.
\bibitem{feller}  W. Feller.  \textit{An Introduction to Probability Theory and its Applications Volume 1}.  Wiley, 1968. 
\bibitem{graham} R. L. Graham, D. E. Knuth and O. Patashnik. \textit{Concrete Mathematics}. Addison-Wesley, 1990.
\bibitem{griffiths} M. Griffiths.  Learning Russian.  \textit{Mathematical Gazette}, \textbf{92} (2008), 551--555.
\bibitem{grimmett} G. Grimmett and D. Stirzaker.  \textit{Probability and Random Processes}.  Oxford University Press, 2001.
\bibitem{knuth} D. E. Knuth, D. E.  \textit{The Art of Computer Programming Volume 1}.  Addison-Wesley, 1968.
\bibitem{sloane} N. Sloane, The On-Line Encyclopedia of Integer Sequences, 2010. \url{http://www.research.att.com/~njas/sequences}
\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}:
Primary 05A15; Secondary 05A16, 05C81, 11B39.

\noindent \emph{Keywords: } Random walks, Fibonacci numbers, generating functions, probabilities.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A000045},
\seqnum{A023607}, and
\seqnum{A023610}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received October 10 2010;
revised version received April 24 2011. 
Published in {\it Journal of Integer Sequences}, May 2 2011.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}