Some remarks on pseudorandom sequences

Winkler, Reinhard

Mathematica slovaca, Tome 43 (1993) no. 4, pp. 493-512

Détail

Classification : 11K45, 65C10

Bibliographie

[Cha1] CHAITIN G. J.: Algorithmic Information Theory. Cambridge University Press, 1987, 1988, 1990. | MR | Zbl

[Cha2] CHAITIN G. J.: Information, Randomness and Incompleteness - Papers on Algorithmic Information Theory. World Scientific, Singapore, 1987, 1990. | MR | Zbl

[Cha3] CHAITIN G. J.: Incompleteness theorems for random reals. Adv. in Appl. Math. 8 (1987), 119-146. | MR | Zbl

[Chu] CHURCH A.: On the concept of a random sequence. Bull. Amer. Math. Soc. 46 (1940), 130-135. | MR | Zbl

[D] DÖRGE K.: Zu der von R. v. Mises gegebenen Begrtindung der Wahrscheinlichkeitstheorie. Math. Z. 32 (1930), 232-258. | MR

[Dr-Ti-Wi] DRMOTA M., TICHY R. F., WINKLER R.: Completely uniformly distributed sequences of matrices. In: Number-Theoretic Analysis. Lecture Notes in Math. 1452, Springer, Berlin-Heidelberg-New York, 1990, pp. 43-57. | MR | Zbl

[Dr-Wi] DRMOTA M., WINKLER R.: s(N)-uniform distribution modulo 1. J. Number Theory, (To appear). | MR | Zbl

[Fe1] FELLER W.: An Introduction to Probability Theory and its Applications. John Wiley and Sons Inc., New York-London-Sydney-Toronto, 1966. | MR | Zbl

[Fe2] FELLER W.: Über die Existenz sogenannter Kollektive. Fund. Math. 32 (1939), 87-96.

[Fl-Ki-Ti1] FLAJOLET P., KIRSCHENHOFER P., TICHY R. F.: Discrepancy of Sequences in Infinite Strings. Colloq. Math. Soc. Janos Bolyai, North-Holland, Amsterdam-New York, 1986.

[Fl-Ki-Ti2] FLAJOLET P., KIRSCHENHOFER P., TICHY R. F.: Deviations from uniformity in random strings. Probab. Theory Related Fields 80 (1988), 139-150. | MR | Zbl

[G1] GOLDSTERN M.: An application of Shoenfield's absoluteness theorem to the theory of uniform distribution. Monatsh. Math., (To appear). | MR | Zbl

[G2] GOLDSTERN M.: Two more remarks on pseudorandom sequences. (Preprint).

[Gra] GRABNER P.: Block distribution in random strings. Ann. Inst. Fourier (Grenoble), (To appear). | MR | Zbl

[Gri] GRILL K.: A note on randomness. Statist. Probab. Letters 14 (1992), 229-233. | MR | Zbl

[H] HLAWKA E.: Theorie der Gleichverteilung. Bibl. Inst., Mannheim-Wien-Zürich, 1979. | MR | Zbl

[Ki-Ti] KIRSCHENHOFER P., TICHY R. F.: Some distribution properties of 0-1 -sequences. Manuscripta Math. 54 (1985), 205-219. | MR | Zbl

[Kn] KNUTH D. E.: The Art of Computer Programming. Vol. II. Addison-Wesley, Reading Mass., 1981. | MR

[Ko1] KOLMOGOROFF A. N.: Grundbegriffe der Wahrscheinlichkeitsrechnung. Ergeb. Math. Grenzgeb. (2), Springer, Berlin-New York, 1933. | MR | Zbl

[Ko2] KOLMOGOROFF A. N.: Drei Zugänge zur Definition des Begriffs "Informationsgehalt". (Russian), Problemy Peredachi Informatsii 1 (1965), 3-11.

[Ko3] KOLMOGOROFF A. N.: On tables of random numbers. Sankhya Ser. A 25 (1963), 369-376. | MR

[Ku-N] KUIPERS L., NIEDERREITER H.: Uniform Distribution of Sequences. Wiley, New York, 1974. | MR | Zbl

[vL] van LAMBALGEN M.: Von Mises' definition of random sequences reconsidered. J. Symbolic Logic 52 (1987), 725-755. | MR | Zbl

[L] LEVIN L. A.: On the notion of a random sequence. Soviet Math. Dokl. 14 (1973), 1414-1416. | Zbl

[Le1] LEVINE M. B.: On the uniform distribution of the sequence {αλx}. (Russian), Mat. Sb. 98 (1975), 207-222, (Translation: Math. USSR-Sb. 27 (1975), 183-197). | MR

[Le2] LEVINE M. B.: On the completely uniform distribution of fractional parts of the exponentional function. (Russian, English Summary), Trudy Sem. Im. Petrovsk. 7 (1981), 245-256. | MR

[Lev-Sh-So-Tu] LEVITAN, YU. L., SHUKHMAN B. V., SOBOL I. M., TURCHANINOV V. I.: Quasirandom Sequence Generators. Keldysh Inst., of Appl. Math., Russian Acad, of Sciences, 1992. | MR

[M1] MARTIN-LÖF P.: The definition of random sequences. Inform. Control 9 (1966), 602-619. | MR

[M2] MARTIN-LÖF P.: On the notion of randomness. In: Intuitionism Proof Theory Proc. Summer Conf. Buffalo N.Y. 1968, 1970, pp. 73-78. | MR

[vM1] von MISES R.: Grundlagen der Wahrscheinlichkeitstheorie. Math. Z. 5 (1919), 52-99. | MR

[vM2] von MISES R.: Wahrscheinlichkeit, Statistik und Wahrheit. Springer, Wien, 1951. | Zbl

[vM3] von MISES R.: Mathematical Theory of Probability and Statistics. Acad. Press, New York-London, 1964. | MR | Zbl

[N1] NIEDERREITER H.: Quasi-Monte Carlo methods and pseudorandom numbers. Bull. Amer. Math. Soc. 84 (1978), 957-1041. | MR

[N2] NIEDERREITER H.: Pseudozufallszahlen und die Theorie der Gleichverteilung. Sitzungsber. Österreich. Akad. Wiss. Math.-Natur. Kl. Abt. II 195 (1986), 109-138. | MR

[N3] NIEDERREITER H.: Point sets and sequences with small discrepancy. Monatsh. Math. 104 (1987), 273-337. | MR | Zbl

[N4] NIEDERREITER H.: Pseudorandom numbers generated from shift register sequences. In: Number-Theoretic Analysis. Lecture Notes in Math. 1452 (E. Hlawka, R. F. Tichy, eds.), Springer, Berlin-Heidelberg-New York, 1990, pp. 165-177. | MR | Zbl

[N5] NIEDERREITER H.: Random Number Generation and Quasi-Monte Carlo Methods. Society for industrial and applied mathematics, Philadelphia, Pennsylvania, 1992. | MR | Zbl

[N-Ti] NIEDERREITER H., TICHY R. F.: Solution of a problem of Knuth on complete uniform distribution of sequences. Mathematika 23 (1985), 26-32. | MR | Zbl

[P] POPPER K.: Logik der Forschung, Achte, weitere verbesserte und vermehrte Auflage. J. C. B. Mohr (Paul Siebeck), Tübingen, 1984. | MR

[S1] SCHNORR C. P.: Zufälligkeit und Wahrscheinlichkeit, Eine algorithmische Begründung der Wahrscheinlichkeitstheorie. Lecture Notes in Math. 218, Springer, Berlin-Heidelberg-New York, 1971. | MR | Zbl

[S2] SCHNORR C. P.: Process complexity and effective random tests. J. Comput. System Sci. 7 (1973), 376-388. | MR | Zbl

[So1] SOBOL I. M.: Quasi-Monte Carlo methods. Progress in Nuclear Energy 24 (1990), 55-61. | MR

[So2] SOBOL I. M.: Die Monte-Carlo-Methode. Deutscher Verlag der Wissenschaften, Berlin, 1991. | MR | Zbl

[Sv] SVOZIL K.: The mathematical foundations of physical randomness and indeterminisness. In: Jahrb. Kurt-Gödel-Ges., Wien, 1988, pp. 53-85. | MR

[Ta] TAUSWORTHE R. C.: Random numbers generated by linear recurrence modulo two. Math. Comp. 19 (1965), 201-209. | MR | Zbl

[Te1] TEZUKA S.: On the discrepancy of GFSR pseudorandom numbers. J. Assoc. Comput. Math. 34 (1987), 939-949. | MR | Zbl

[Te2] TEZUKA S.: On optimal GFSR pseudorandom number generators. Math. Comp. 50 (1988), 531-533. | MR | Zbl

[Ti1] TICHY R. F.: Ein metrischer Satz über vollständig gleichverteilte Folgen. Acta Arith. 48 (1987), 197-207. | MR | Zbl

[Ti2] TICHY R. F.: Zur Analyse und Anwendung von Zufallszahlen. In: Jahrb. Kurt-Gödel-Ges., Wien, 1990, pp. 109-116. | MR

[V] VILLE J.: Etude critique de la notion de collectif. Gauthier-Villars, Paris, 1939. | Zbl

[Wa1] WALD A.: Sur la notion de collectif dans le calcul des probabilites. C. R. Acad. Sci. Paris 202 (1936), 180-183. | Zbl

[Wa2] WALD A.: Die Widerspruchsfreiheit des Kollektivbegriffs in der Wahrscheinlichkeitsrechnung. Ergebnisse eines math. Koll. 8 (1937), 38-72.

[Wi] WINKLER R.: Some constructive examples in uniform distribution on finite sets and normal numbers. Anz. Österreich. Akad. Wiss. Math.-Natur. Kl. 126 (1989), 1-8. | MR | Zbl