<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 5 Issue 2" %>
Birth Processes and Symmetric Polynomials
T. Bickel, N. Galli, and K. Simon
Institute for Theoretical Computer Science, ETH zentrum, 8092 Zurich, Switzerland
{bickel, galli, simon}@inf.ethz.ch
Annals of Combinatorics 5(2) p.123-139 June, 2001
AMS Subject Classification: 05A30, 05A19, 60J10, 11B65
Many discrete-time pure birth processes are symmetrical in the following sense: The probability that the process is in a fixed state is independent of the sequence of transitions inducing . This is always the case whenever a transition is a time-dependent or a state-dependent random variable or the product of such independent variables. We use this property in order to derive algebraic descriptions in terms of symmetric polynomials. Besides new solutions, our approach offers a uniform point of view on a large class of often considered distributions.
Keywords: generalized Stirling numbers, birth processes, symmetric polynomials


1.  G.E. Andrews, The Theory of Partitions, Addison Wesley, 1976.

2.  G.E. Andrews, D. Crippa, and K. Simon, q-Sries arising from the study of random graphs, SIAM J. Discrete Math. 10 (1997) 41每56.

3.  T. Bickel, The group of generalized Stirling numbers, Adv. Appl. Math., to appear.

4.  C.L. Chiang, An Introduction to Stochastic Processes and Their Applications, R. E. Krieger Publishing Company, 1980.

5.  F. Collenberg, D. Crippa, and K. Simon, On the distribution of the transitive closure in a random acyclic digraph, In: ESA'93: European Symposium on Algorithms, Lecture Notes in Computer Science, Springer 726, 1993, pp. 345每357.

6.  L. Comtet, Nombres de Stirling généraux et fonctions symmetrique, C. R. Acad. Sci. Paris Ser. A 275 (1972) 747每750.

7.  D. Crippa and K. Simon, q-Distributions and Markov processes, Discrete Math. 140 (1996) 81每98.

8.  A. de Médicis and P. Leroux, Generalized Stirling numbers, convolution formulae and p;qanalogues, Canad. J. Math. 47 (1995) 474每499.

9.  W. Feller, An Introduction to Probability Theory and Its Applications, Vol. 1, 2nd Edition, John Wiley & Sons, 1971.

10.  P. Flajolet and R. Sedgewick, Analysis of Algorithms, Addison-Wesley, 1996.

11.  H. Gould, The q-Stirling numbers of first and second kinds, Duke Math. J. 28 (1961) 281每 289.

12.  I. Goulden and C. Greene, A new tableau representation for supersymmetric Schur functions, J. Algebra 170 (2) (1994) 687每703.

13.  R.L. Graham, D. Knuth, and O. Patashnik, Concrete Mathematics, Addison Wesley, 1989.

14.  N.L. Johnson and S. Kotz, Urn Model and Their Application, John Wiley & Sons, 1977.

15.  M. Loeve, Probability Theory, Vol. 1, 4th Edition, Springer, 1977, pp. 373.

16.  I.G. MacDonald, Symmetric Functions and Hall Polynomials, Oxford University Press, New York, 1979.

17.  P.A. MacMahon, Collected Papers, Vol. 1, G.E. Andrews Ed., M.I.T. Press, 1978.

18.  P.A. MacMahon, Symmetric functions and the theory of distributions, Proc. London Math. Soc. 19 (1889) 220每256.

19.  N. Metropolis, G. Nicoletti, and G.-C. Rota, A new class of symmetric functions, In: Mathematical Analysis and Applications, Advances in Mathematics Supplementary Studies, Vol. 7B, Academic Press, New York, 1981, pp. 563每575.

20.  R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge University Press, 1995.

21.  G. Pólya and D. Szeg?, Aufgaben und Lehrsátze aus der Analysis, Springer, 1964.

22.  P. Theoret, Relations matricielles pour hyperbinomiales, Ann. Sci. Math. Québec 19 (2) (1995) 197每212.