Skip to main content
SpringerLink
Log in

Impugning Randomness, Convincingly

  • Published:
Studia Logica Aims and scope Submit manuscript

Abstract

John organized a state lottery and his wife won the main prize. You may feel that the event of her winning wasn’t particularly random, but how would you argue that in a fair court of law? Traditional probability theory does not even have the notion of random events. Algorithmic information theory does, but it is not applicable to real-world scenarios like the lottery one. We attempt to rectify that.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Batanero C.: ‘Controversies around the role of statistical tests in experimental research’. Mathematical Thinking and Learning 2(1-2), 75–98 (2000)

    Article  Google Scholar 

  2. Bazhanov, V. R., ‘Logic and Ideologized Science Phenomenon (Case of the URSS)’, in G. Sica (ed.), Essays on the foundations of mathematics and logic, Polimetrica International Scientific Publisher, 2005, pp. 43–48.

  3. Bernoulli, J., Ars Conjectandi, Thurneysen Brothers, Basel, 1713.

  4. Bezhanishvili M., Mchedlishvili L.: Logic in Georgia. Meridian Publishers, Tbilisi (1995)

    Google Scholar 

  5. Borel, E., Les Probabilités et la Vie, Presses Universitaires de France, Paris, 1943. English: Probabilities and Life, Dover, 1962.

  6. Bradley, J., ‘Why Dembski’s Design Inference Doesn’t Work’, The Biologos Foundation, 2009.

  7. Büchi J. R.: ‘Weak second-order arithmetic and finite automata’. Zeitschrift für Mathematische Logik und Grundlagen der Mathematik 6, 66–92 (1960)

    Article  Google Scholar 

  8. Bzip2, http://bzip.org/.

  9. Calude, C. S., K. S. Salomaa, and T. K. Roblot, ‘Finite State Complexity’, Theoretical Computer Science, to appear.

  10. Chaitin G. J.: ‘On the length of programs for computing finite binary sequences’. Journal of ACM 13, 547–569 (1966)

    Article  Google Scholar 

  11. Chaitin G. J.: Algorithmic Information Theory. Cambridge University Press, New York, NY, USA (1987)

    Book  Google Scholar 

  12. Chater N.: ‘The search for simplicity: a fundamental cognitive principle?’. The Quarterly Journal of Experimental Psychology Section A 52(2), 273–302 (1999)

    Article  Google Scholar 

  13. Chen X., Francia B., Li M., McKinnon B., Seker A.: ‘Shared information and program plagiarism detection’. IEEE Transactions on Information Theory 50(7), 1545–1551 (2004)

    Article  Google Scholar 

  14. Cilibrasi R., Vitányi P.: ‘The Google Similarity Distance’. IEEE Transactions on Knowledge and Data Engineering 19(3), 370–383 (2007)

    Article  Google Scholar 

  15. Cilibrasi R., Vitányi P., De Wolf R.: ‘Algorithmic clustering of music based on string compression’. Comput. Music J. 28, 49–67 (2004)

    Article  Google Scholar 

  16. Cohen J.: ‘The Earth Is Round (p < .05)’. American Psychologist 49(12), 997–1003 (1994)

    Article  Google Scholar 

  17. Cournot, A. A., Exposition de la Théorie des Chances et des Probabilités, Hachette, Paris, 1843.

  18. Cox, D. R., and D. V. Hinkley, Theoretical Statistics, Chapman and Hall London, 1974.

  19. Davis B. R., Hardy R. J.: ‘Upper bounds for type I and type II error rates in conditional power calculations’. Communications in Statistics 19(10), 3571–3584 (1990)

    Article  Google Scholar 

  20. Dembski, W. A., The Design Inference: Eliminating Chance Through Small Probabilities, Cambridge University Press, 1998.

  21. Dembski, W. A., No Free Lunch: Why Specified Complexity Cannot Be Purchased Without Intelligence, Rowman and Littlefield, 2006.

  22. Elsberry W., Shallit J.: ‘Information theory, evolutionary computation, and Dembski’s “complex specified information”’. Synthese 128(2), 237–270 (2011)

    Article  Google Scholar 

  23. Ferragina P., Giancarlo R., Greco V., Manzini G., Valiente G.: ‘Compression-based classification of biological sequences and structures via the universal similarity metric: experimental assessment’. BMC Bioinformatics 8(1), 252 (2007)

    Article  Google Scholar 

  24. Fisher, R. A., Statistical Methods for Research Workers, Oliver and Boyd, Edinburgh, 1925.

  25. Fisher, R. A., Statistical Methods and Scientific Inference, Hafner, 1926.

  26. Fisher R. A.: ‘The arrangement of field experiments’. Journal of the Ministry of Agriculture of Great Britain 33, 503–513 (1956)

    Google Scholar 

  27. Fraley, R. C., The Statistical Significance Testing Controversy: A Critical Analysis, http://www.uic.edu/classes/psych/psych548/fraley/.

  28. Friedman, L., C. Furberg, and D. DeMets, Fundamentals of Clinical Trials, 3rd edition, Mosby, 1996.

  29. Gilbert D., Rossello F., Valiente G., Veeramalai M.: ‘Alignment-free comparison of tops strings’. London Algorithmics and Stringology 2006(8), 177–1979 (2007)

    Google Scholar 

  30. Granovetter M. S.: ‘The strength of weak ties’. The American Journal of Sociology 78(6), 1360–1380 (1973)

    Article  Google Scholar 

  31. Kirchherr W., Li M., Vitányi P.: ‘The miraculous universal distribution’. The Mathematical Intelligencer 19(4), 7–15 (1997)

    Article  Google Scholar 

  32. Kolmogorov A. N.: Grundbegriffe der Wahrscheinlichkeitsrechnung. Springer, Berlin (1933)

    Google Scholar 

  33. Kolmogorov A. N.: ‘Three approaches to the quantitative definition of information’. Problems Inform. Transmission 1(1), 1–7 (1965)

    Google Scholar 

  34. Krasnogor, N., and D. A. Peltai, ‘Measuring the similarity of protein structures by means of the universal similarity metric’, Bioinformatics 20:1015–1021, May 2004.

    Google Scholar 

  35. Levin L. A.: ‘Randomness Conservation Inequalities; Information and Independence in Mathematical Theories’. Information and Control 61, 15–37 (1984)

    Article  Google Scholar 

  36. Lévy P.: Calcul de probabilités. Gauthier-Villars, Paris (1925)

    Google Scholar 

  37. Li M., Badger J.H., Chen X., Kwong S., Kearney P., Zhang H.: ‘An information-based sequence distance and its application to whole mitochondrial genome phylogeny’. Bioinformatics 17(2), 149–154 (2001)

    Article  Google Scholar 

  38. Li, M., and P. Vitányi, An Introduction to Kolmogorov Complexity and its Applications, 2nd edition, Springer, 1997.

  39. Meinert, C. L., Clinical Trials Design, Conduct, and Analysis, Oxford University Press, 1986.

  40. Merton, R. K., Social Theory and Social Structure, Free Press, (Glencoe, Il.), 1957.

  41. Morrison, D. E., and R. E. Henkel (eds.), The Significance Test Controversy, Aldine. Oxford, England, 1970.

  42. Moye L. A.: ‘P-value interpretation and alpha allocation in clinical trials’. Annals of Epidemiology 8(6), 351–357 (1998)

    Article  Google Scholar 

  43. Richardson M., Domingos P.: ‘Markov logic networks’. Machine Learning 62(1-2), 107–136 (2006)

    Article  Google Scholar 

  44. Shafer, G., ‘Why did Cournot’s Principle disappear?’, Lecture at École des Hautes Études en Sciences Sociales, http://www.glennshafer.com/assets/downloads/disappear.pdf, 2006.

  45. Shafer, G., and V. Vovk, Probability and Finance: It’s Only a Game, John Wiley and Sons, 2001.

  46. Shen, A., ‘Algorithmic Information Theory and Foundations of Probability’, arXiv 0906.4411, 2009.

  47. Solomonoff, R., ‘A formal theory of inductive inference, part 1 and part 2’, Information and Control 7(1):1–22, and 7(2):224–254, 1964.

  48. Wasserman, S., and K. Faust, Social Network Analysis: Methods and Applications, Cambridge University Press, 1994.

  49. Wein, R., ‘Not a Free Lunch But a Box of Chocolates: A critique of William Dembski’s book “No Free Lunch”’, http://www.talkorigins.org/design/faqs/nfl.

  50. Welch T.: ‘A Technique for High-Performance Data Compression’. IEEE Computer 17(6), 8–19 (1984)

    Article  Google Scholar 

  51. Wells, R., ‘41.6% the US Population Has a Facebook Account’, Posted August 8, 2010 at http://socialmediatoday.com/index.php?q=roywells1/158020/416-us-population-has-facebook-account.

  52. Wikipedia, ‘Prediction by partial matching’, http://en.wikipedia.org/wiki/PPM_compression_algorithm.

  53. Wikipedia, ‘P-value’, http://en.wikipedia.org/wiki/P-value.

  54. Ziv J., Lempel A.: ‘A universal algorithm for sequential data compression’. IEEE Transactions on Information Theory 23(3), 337–343 (1977)

    Article  Google Scholar 

  55. Ziv J., Lempel A.: ‘Compression of individual sequences via variable-rate coding’. IEEE Transactions on Information Theory 24(5), 530–536 (1978)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Microsoft Research, One Microsoft Way, Redmond, Washington, 98052, USA

    Yuri Gurevich

  2. Clare Hall, University of Cambridge and LFCS, University of Edinburgh, Herschel Road, Cambridge, CB3 9AL, UK

    Grant Olney Passmore

Authors
  1. Yuri Gurevich
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Grant Olney Passmore
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Yuri Gurevich.

Additional information

In memoriam Leo Esakia

Rights and permissions

Reprints and permissions

About this article

Cite this article

Gurevich, Y., Passmore, G.O. Impugning Randomness, Convincingly. Stud Logica 100, 193–222 (2012). https://doi.org/10.1007/s11225-012-9375-1

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11225-012-9375-1

Keywords

Search

Navigation