Name
Title | ||
|---|---|---|
A Poisson * negative binomial convolution law for random polynomials over finite fields |
Abstract | ||
|---|---|---|
Let F-q[X] denote a polynomial ring over a finite field F-q with q elements. Let P-n be the set of monic polynomials over F-q of degree n. Assuming that each of the q(n) possible monic polynomials in P-n is equally likely, we give a complete characterization of the limiting behavior of P(Omega(n) = m) as n --> infinity by a uniform asymptotic formula valid for m greater than or equal to 1 and n - m --> where Omega(n) represents the number (multiplicities counted) of irreducible factors in the factorization of a random polynomial in P-n. The distribution of Omega(n) is essentially the convolution of a Poisson distribution with mean log n and a negative binomial distribution with parameters q and q(-1). Such a convolution law exhibits three modes of asymptotic behaviors: when m is small, it behaves like a Poisson distribution; when m becomes large, its behavior is dominated by a negative binomial distribution, the transitional behavior being essentially a parabolic cylinder function (or some linear combinations of the standard normal law and its iterated integrals). As applications of this uniform asymptotic formula, we derive most known results concerning P( Omega(n), = m) and present many new ones like the unimodality of the distribution. The methods used are widely applicable to other problems on multiset constructions. An extension to Renyi's problem, concerning the distribution of the difference of the (total) number of irreducibles and the number of distinct irreducibles, is also presented. (C) 1998 John Wiley & Sons, Inc. Random Struct. Alg., 13, 17-47,1998. |
Year | DOI | Venue |
|---|---|---|
1998 | 3.0.CO;2-V" target="_self" class="small-link-text"10.1002/(SICI)1098-2418(199808)13:13.0.CO;2-V | Random Struct. Algorithms |
Keywords | Field | DocType |
poisson distribution,polynomial ring,irreducible polynomial,asymptotic behavior,finite field,negative binomial distribution,negative binomial,parabolic cylinder function | Compound Poisson distribution,Discrete mathematics,Unimodality,Binomial distribution,Asymptotic formula,Combinatorics,Binomial type,Monic polynomial,Negative binomial distribution,Law,Beta negative binomial distribution,Mathematics | Journal |
Volume | Issue | ISSN |
13 | 1 | 1042-9832 |
Citations | PageRank | References |
1 | 0.38 | 6 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hsien-Kuei Hwang | 1 | 365 | 38.02 |