\documentclass[12pt,a4paper,reqno]{amsart}%{article}

%\RequirePackage{theorem}



\hfuzz=10pt

\newtheorem{theorem}{Theorem}%[section]
\newtheorem{proposition}{Proposition}%[section]
\newtheorem{lemma}{Lemma}%[section]
\newtheorem{cor}{Corollary}
\renewcommand{\thecor}{}
\newtheorem{ncor}{Corollary}

\newtheorem{df}{Definition}[section]
\newtheorem{ex}{Example}
\renewcommand{\theex}{}

\def\U{{\cal{U}}}
\def\E{{\cal{E}}}
\def\T{{\cal{T}}}
\def\P{{\cal{P}}}
\def\a{{\bold{a}}}
\def\p{{\bold{p}}}
\def\mcirc{{\bigcirc}}
\def\dilog{\operatorname{dilog}}
\def\N{{\mathcal{N}}}
\def\D{{\mathcal{D}}}
\def\P{{\cal P}}
\def\bl{\operatorname{L}}






\newtheorem{rem}{Remark}
\renewcommand{\therem}{}
\newtheorem{nrem}{Remark}

%\section{packages}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsfonts}
%\usepackage{theorem}
%\usepackage{xspace}

\topmargin 0 pt                        
\textheight 46\baselineskip     
\advance\textheight by \topskip
\setlength{\parindent}{0pt}            
\setlength{\parskip}{5pt plus 2pt minus 1pt}     
\setlength{\textwidth}{155mm}         
\setlength{\oddsidemargin}{5.6mm}     
\setlength{\evensidemargin}{5.6mm}   





\def\Prob{\mathbb{P}}

\newcommand{\Res}[1]{\mathop{\textrm{Res}}\nolimits\left\ldlm#1\right\rdlm}
                                                   % Residue
\newcommand{\ffact}[2]{#1^{\underline{#2}}}
\newcommand{\img}{\text{i}}
\newcommand{\bigOh}{\mathop{\mathcal{O}}\nolimits}  
\newcommand{\Pm}{\operatorname{pm}}
\def\bb#1{[\![#1]\!]}
\newcommand{\gauss}[2]{\genfrac{[}{]}{0pt}{}{#1}{#2}_q}  



%\section{preamble}
\title[analysis of an
 algorithm to generate a random cyclic permutation]
{On the analysis of an
 algorithm to generate a random cyclic permutation}

\author{Helmut Prodinger}
%\thanks{}

\address{ Helmut Prodinger,
The John Knopfmacher
Centre for Applicable Analysis and Number Theory,
 Department of Mathematics,
University of the Witwatersrand, P.~O. Wits, 
2050 Johannesburg, South Africa, email:
{\tt helmut@gauss.cam.wits.ac.za},\newline
homepage: {\tt http://www.wits.ac.za/helmut/index.htm}
}
\date{January 16, 2000}









\begin{document}

\begin{abstract}
Sattolo has presented an algorithm to generate cyclic
permutations at random. In this note the two parameters
``number of moves'' and ``distance'' are analyzed.
\end{abstract}


\maketitle

\section{Introduction}

Sattolo \cite{Sattolo86} generates a random cyclic permutation
as follows: She starts with $12\dots n$, then a random
integer between 1 and $n-1$  is chosen, say $i$, and
 the numbers in positions $i$ and $n$   are interchanged.
Then a random
integer between 1 and $n-2$  is chosen, say $j$, and
 the numbers in positions $j$ and $n-1$   are interchanged,
and so on. After $n-1$ iterations, a  random cyclic permutation
has been obtained. 

Here is an example, with $n=5$ 
and the random numbers $4,1,2,1$:
\begin{align*}
&1\ 2\ 3\ \underline{4}\ \bold{5}\\
&\underline{1}\ 2\ 3\ \bold{5}\ 4\\
&5\ \underline{2}\ \bold{3}\ 1\ 4\\
&\underline{5}\ \bold{3}\ 2\ 1\ 4\\
&3\ 5\ 2\ 1\ 4\\
\end{align*}

The result is the cyclic permutation $1\to3\to2\to5\to4\to1$. 

In this note we are interested in the (average) number of times
digit $k$ moves; in the example we obtain the numbers
$1,\,1,\,2,\,1,\,3$
for $k=1,\dots,5$. 
Altogether that means $1+1+2+1+3=8$ moves, which
is clear, since each iteration moves exactly 2 digits. 
  


We are also considering the (average) distance
digit $k$ travels. In the example we obtain the numbers
$3,\,1,\,2,\,1,\,5$ for $k=1,\dots,5$.

 

\section{The number of moves}

The probability generating functions $\varphi_{n,k}(u)$
are defined as follows: 
\begin{equation*}   
\varphi_{n,k}(u)=
\sum_{l}a_{n,k;l}u^l=
\sum_{l}\Prob\{
\text{digit $k$ makes $l$ moves}\}u^l
.
\end{equation*}

The probability that position $k$ is never chosen by the
random number generator, is given by
\begin{equation*}   
\frac{n-2}{n-1}\cdot
\frac{n-3}{n-2}\cdots
\frac{k-1}{k}=\frac{k-1}{n-1}.
\end{equation*}

If position $k$ is chosen by the random generator, 
digit $k$ is moved once (to the right) and never moves again.
If position $k$ is never chosen by the random generator, 
it starts moving (to the left) when the positions 
$k+1,\dots,n$ have already been dealt with. This leads to the
recursion


\begin{equation*}   
\varphi_{n,k}(u)=\frac{n-k}{n-1}\,u
+\frac{k-1}{n-1}\, \varphi_{k,k}(u),\qquad 1\le k< n.
\end{equation*}

It remains to discuss the instance $k=n$. The recursion
is 
\begin{equation*}   
\varphi_{n,n}(u)=\frac{u}{n-1}\Big[
\varphi_{n-1,1}(u)+\varphi_{n-1,2}(u)+\dots+
\varphi_{n-1,n-1}(u)
\Big], \quad n\ge2, \ 
\varphi_{1,1}(u)=1.
\end{equation*}


To understand it, note that one move is made, and,
according to the random generator, each position
$1,2,\dots,n-1$ might be chosen with probability $\frac{1}{n-1}$.
Then digit $n$  is in position $k$, say, and the further
moves are described by $\varphi_{n-1,k}(u)$.  


Let us start with the numbers $a_{n,k;1}$. It is easy to
see that
\begin{equation*}   
a_{n,1;1}=1, \quad a_{n,2;1}=1, \quad
a_{n,k;1}=\frac{n-k}{n-1}, \quad k\ge3, \quad n\ge 2,
\quad a_{1,1;1}=0.
\end{equation*} 

The recursions tell us furthermore that
\begin{equation*}   
a_{n,k;2}=
\frac{1}{n-1}\Big[
a_{k-1,1;1}+a_{k-1,2;1}+\dots+a_{k-1,k-1;1}
\Big].	
\end{equation*}

Hence
\begin{equation*}   
a_{n,k;2}=\frac{1}{n-1}\Big[\frac{k-1}{2}+\frac{1}{k-2}\Big],
\quad n\ge k\ge 3, \quad  \text{$a_{n,k;2}=0$ otherwise}.
\end{equation*} 

Similarly
\begin{equation*}   
a_{n,k;3}=
\frac{1}{n-1}\Big[
a_{k-1,1;2}+a_{k-1,2;2}+\dots+a_{k-1,k-1;2}
\Big]	
\end{equation*}
and thus

\begin{equation*}   
a_{n,k;3}=\frac{1}{(n-1)(k-2)}
\Big[-1+\frac{(k-1)(k-2)}{4}+H_{k-3}\Big],
\quad n\ge k\ge 3.
\end{equation*} 

We can also compute the next ones as

\begin{equation*}   
a_{n,k;4}=\frac{1}{(n-1)(k-2)}
\bigg[-H_{k-3}-\frac{1}{4}+\frac{(k-1)(k-2)}{8}+\frac{1}{2}
\Big(H_{k-3}^2-H_{k-3}^{(2)}\Big)\bigg],
\ n\ge k\ge 3,
\end{equation*} 
but it is clear the expressions become very messy.

The numbers $H_n=\sum_{k=1}^n\frac{1}{k}$ 
and $H_n^{(2)}=\sum_{k=1}^n\frac{1}{k^2}$ are
harmonic numbers of the first and second order. 

Now we proceed to the expected numbers of moves
$E_{n,k}=\varphi'_{n,k}(1)$. The recursions are

\begin{equation*}   
E_{n,k}=\frac{n-k}{n-1}
+\frac{k-1}{n-1}\, E_{k,k},
\end{equation*}
and
\begin{equation*}   
E_{n,n}=1+\frac{1}{n-1}\Big[
E_{n-1,1}+E_{n-1,2}+\dots+E_{n-1,n-1}
\Big].
\end{equation*}
It is a simple task to find the answers


\begin{equation*}   
E_{n,k}=\frac{n+2k-5}{n-1}, \qquad k\ge2, \quad 
E_{n,1}=1, \quad n\ge2, \quad E_{1,1}=0
\end{equation*} 
and prove them by induction. Since this can be done
by Maple, it is omitted. 

Note that
\begin{equation*}   
\sum_{k=1}^nE_{n,k}=1+\sum_{k=2}^n\frac{n+2k-5}{n-1}=2(n-1),
\end{equation*}
as it should.




The second factorial moments can be computed in a similar
fashion; 
\begin{equation*}   
\varphi_{n,k}^{\prime\prime}(1)=\frac{1}{n-1}(8k-4H_{k-2}-16)
\end{equation*}
for $k\ge2$, otherwise 0. 

\begin{theorem}
The average number of moves of digit $k$ 
in Sattolo's algorithm
and the variance
are given by
\begin{align*}
E_{n,k}&=\frac{n+2k-5}{n-1}, \qquad k\ge2, \quad 
E_{n,1}=1, \quad n\ge2, \quad E_{1,1}=0,\\
V_{n,k}&=
\frac{2(k-2)(3n+1-2k)}{(n-1)^2}-\frac{4H_{k-2}}{n-1}
, \qquad k\ge2, \quad 
V_{n,1}=0.\qed
\end{align*}
\end{theorem}

\section{The distance}


It is not too hard to change things appropriately.

The recursions for the probability generating functions are now


\begin{align*}   
\varphi_{n,k}(u)&=\frac{u^{n-k}}{n-1}
+\frac{n-2}{n-1}\, \varphi_{n-1,k}(u),\qquad 1\le k< n,\\
\varphi_{n,n}(u)&=\frac{1}{n-1}\Big[
\varphi_{n-1,1}(u)u^{n-1}+\varphi_{n-1,2}(u)u^{n-2}+\dots+
\varphi_{n-1,n-1}(u)u
\Big], \quad n\ge2, \\ 
\varphi_{1,1}(u)&=1.
\end{align*}

From this we get the expectation
\begin{equation*}   
E_{n,k}=\frac{n}{2}-k+1+\frac{k(3k-5)}{2(n-1)}, \quad
k\ge2, \qquad E_{n,1}=\frac{n}{2}, \quad n\ge2, 
\quad E_{1,1}=0,
\end{equation*}
and the second factorial moment


\begin{align*}   
E_{n,k}^{(2)}&=\frac{n^2}{3}-n(k-\tfrac{1}{3})+k(k-1)+
\frac{(k-2)(14k^2+k-21)}{18(n-1)}
, \quad
k\ge2,\\
 E_{n,1}^{(2)}&=\frac{n(n-2)}{3}, \quad n\ge2, 
\qquad E_{1,1}^{(2)}=0.
\end{align*}  


\begin{theorem}
The average distance that digit $k$ travels
in Sattolo's algorithm
and the variance
are given by
\begin{align*}
E_{n,k}&=\frac{n}{2}-k+1+\frac{k(3k-5)}{2(n-1)}, \quad
k\ge2, \qquad E_{n,1}=\frac{n}{2}, \quad n\ge2, 
\quad E_{1,1}=0,\\
V_{n,k}&=
\frac{(n-1)^2}{12}
-\frac{18k^2-30k+1}{12}
+\frac{(4k-7)(17k^2-13k-6)}{18(n-1)}
-\frac{k^2(3k-5)^2}{4(n-1)^2}
, \quad k\ge2, \\
V_{n,1}&=\frac{n(n-2)}{12}. \qed
\end{align*}
\end{theorem}

Averaging over all digits we find the average distance
that a random element travels:
\begin{equation*}   
\frac{1}{n}\sum_{k=1}^nE_{n,k}=\frac{n+1}{2}-\frac{1}{n}.
\end{equation*}





\bibliographystyle{plain}
\begin{thebibliography}{1}


\bibitem{Sattolo86}
S.~Sattolo.
\newblock 
An algorithm to generate a random cyclic permutation.
\newblock {\em Information Processing Letters},
 22:315--317, 1986.


\end{thebibliography}






\end{document}

 



