EXACT AND LIMITING DISTRIBUTIONS OF THE NUMBER OF SUCCESSIONS IN A RANDOM PERMUTATION

JAMES C. FU

Institute of Applied Mathematics, National Donghwa University, Hualien, Taiwan, R.O.C.

(Received April 14, 1994; revised November 7, 1994)

Abstract. Traditionally the distributions of the number of patterns and successions in a random permutation of n integers 1, 2, …, and n were studied by combinatorial analysis. In this short article, a simple way based on finite Markov chain imbedding technique is used to obtain the exact distribution of successions on a permutation. This approach also gives a direct proof that the limiting distribution of successions is a Poisson distribution with parameter λ = 1. Furthermore, a direct application of the main result, it also yields the waiting time distribution of a succession.

Key words and phrases: Permutation, succession, Markov chain imbedding, transition probabilities, Poisson convergence, waiting time.