Hostname: page-component-78c5997874-94fs2 Total loading time: 0 Render date: 2024-11-04T18:23:02.924Z Has data issue: false hasContentIssue false
  • English
  • Français

Estimating the Error of a Permutational Central Limit Theorem

Published online by Cambridge University Press:  27 July 2009

Chern-Ching Chao ,
Lincheng Zhao  and
Wen-Qi Liang
Chern-Ching Chao
Affiliation:
Institute of Statistical Science, Academia Sinica, Taipei 11529, Taiwan, R.O.C.
Lincheng Zhao
Affiliation:
Department of Mathematics, University of Science & Technology Hefei, Anhui 230026, China
Wen-Qi Liang
Affiliation:
Institute of Statistical Science, Academia Sinica, Taipei 11529, Taiwan, R.O.C.
Get access Rights & Permissions [Opens in a new window]

Extract

Motivated by two measures of presortedness, number of runs and oscillation of a permutation, related to the sorting problem, we derive an error bound for normal approximation to the distribution of Here, αij's are given real numbers and π is a uniformly distributed random permutation of {l,…, n}. The derivation is based on Stein's method.

Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 10 , Issue 4 , October 1996 , pp. 533 - 541
Copyright
Copyright © Cambridge University Press 1996

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1.Angus, J.E. (1995). A coupling proof of the asymptotic normality of the permutation oscillation. Probability in the Engineering and Informational Sciences 9: 615–621.Google Scholar
2.Barton, D.E. & Mallows, C.L. (1965). Some aspects of the random sequence. Annals of Mathematical Statistics 36: 236–260.CrossRefGoogle Scholar
3.Bender, E.A. (1973). Central and local limit theorems applied to asymptotic enumeration. Journal of Combinatorial Theory, Series A 15: 91–111.Google Scholar
4.Carlitz, L., Kurtz, D.C., Scoville, R., & Stackelberg, O.P. (1972). Asymptotic properties of Eulerian numbers. Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Cebiete 23: 47–54.Google Scholar
5.Chao, C.C., Bai, Z., & Liang, W.Q. (1993). Asymptotic normality for oscillation of permutation. Probability in the Engineering and Informational Sciences 7: 227–235.CrossRefGoogle Scholar
6.David, F.N. & Barton, D.E. (1962). Combinatorial chance. London: Griffin.Google Scholar
7.Dwass, M. (1973). The number of increases in a random permutation. Journal of Combinatorial Theory, Series A 15: 192–199.CrossRefGoogle Scholar
8.Estivill-Castro, V., Mannila, H., & Wood, D. (1993). Right invariant metrics and measures of presortedness. Discrete Applied Mathematics 42: 1–16.Google Scholar
9.Harris, B. & Park, C.J. (1994). A generalization of the Eulerian numbers with a probabilistic application. Statistics & Probability Letters 20: 37–47.Google Scholar
10.Knuth, D.E. (1973). The art of computer programming. Vol. 3: Sorting and searching. Reading, MA: Addison-Wesley.Google Scholar
11.Levcopoulos, C. & Petersson, O. (1989). Heapsort-adapted for prosorted files. Proceedings of the 1989 Workshop on Algorithms and Data Structures, Lecture Notes in Computer Science 382: 499–509. Berlin: Springer.Google Scholar
12.Levcopoulos, C. & Petersson, O. (1993). Adaptive heapsort. Journal of Algorithms 14: 395–413.CrossRefGoogle Scholar
13.Mannila, H. (1985). Measures of presortedness and optimal sorting algorithms. IEEE Transactions on Computers C-34(4): 318–325.Google Scholar
14.Stein, C.M. (1986). Approximate computations of expectations, Lecture Notes-Monograph Series, Vol. 7. Hayward, CA: Institute of Mathematical Statistics.CrossRefGoogle Scholar
15.Tanny, S. (1973). A probabilistic interpretation of Eulerian numbers. Duke Mathematical Journal 40: 717–722.Google Scholar