Algorithmically random sequence - Revision history

Rhododendron canadensis: /* growthexperiments-addlink-summary-summary:3|0|0 */

2025-04-03T13:10:10Z

Link suggestions feature: 3 links added.

JBW: Each one: singular.

2025-01-05T21:43:54Z

Each one: singular.

← Previous revision		Revision as of 21:43, 5 January 2025
Line 7:		Line 7:
	As different types of algorithms are sometimes considered, ranging from algorithms with specific bounds on their running time to algorithms which may ask questions of an [[oracle machine]], there are different notions of randomness. The most common of these is known as '''Martin-Löf randomness''' ('''K-randomness''' or '''1-randomness'''), but stronger and weaker forms of randomness also exist. When the term "algorithmically random" is used to refer to a particular single (finite or infinite) sequence without clarification, it is usually taken to mean "incompressible" or, in the case the sequence is infinite and prefix algorithmically random (i.e., K-incompressible), "Martin-Löf–Chaitin random".		As different types of algorithms are sometimes considered, ranging from algorithms with specific bounds on their running time to algorithms which may ask questions of an [[oracle machine]], there are different notions of randomness. The most common of these is known as '''Martin-Löf randomness''' ('''K-randomness''' or '''1-randomness'''), but stronger and weaker forms of randomness also exist. When the term "algorithmically random" is used to refer to a particular single (finite or infinite) sequence without clarification, it is usually taken to mean "incompressible" or, in the case the sequence is infinite and prefix algorithmically random (i.e., K-incompressible), "Martin-Löf–Chaitin random".

	Since its inception, Martin-Löf randomness has been shown to admit many equivalent characterizations—in terms of [[data compression\|compression]], randomness tests, and [[gambling]]—that bear little outward resemblance to the original definition, but each of which ~~satisfy~~ our intuitive notion of properties that random sequences ought to have: random sequences should be incompressible, they should pass statistical tests for randomness, and it should be difficult to make money [[betting]] on them. The existence of these multiple definitions of Martin-Löf randomness, and the stability of these definitions under different models of computation, give evidence that Martin-Löf randomness is natural and not an accident of Martin-Löf's particular model.		Since its inception, Martin-Löf randomness has been shown to admit many equivalent characterizations—in terms of [[data compression\|compression]], randomness tests, and [[gambling]]—that bear little outward resemblance to the original definition, but each of which satisfies our intuitive notion of properties that random sequences ought to have: random sequences should be incompressible, they should pass statistical tests for randomness, and it should be difficult to make money [[betting]] on them. The existence of these multiple definitions of Martin-Löf randomness, and the stability of these definitions under different models of computation, give evidence that Martin-Löf randomness is natural and not an accident of Martin-Löf's particular model.

	It is important to disambiguate between algorithmic randomness and stochastic randomness. Unlike algorithmic randomness, which is defined for computable (and thus deterministic) processes, stochastic randomness is usually said to be a property of a sequence that is a priori known to be generated by (or is the outcome of) an [[Independence (probability theory)\|independent]] identically [[Probability distribution\|distributed]] equiprobable stochastic process.		It is important to disambiguate between algorithmic randomness and stochastic randomness. Unlike algorithmic randomness, which is defined for computable (and thus deterministic) processes, stochastic randomness is usually said to be a property of a sequence that is a priori known to be generated by (or is the outcome of) an [[Independence (probability theory)\|independent]] identically [[Probability distribution\|distributed]] equiprobable stochastic process.

JBW: Restoring removed content which gave context to what is stared here. If course anyone could find that context by searching in Church's biography, but why would they be searching there, and in any case it makes sense to make this information easier to find, in view of its relevance.

2025-01-05T21:39:01Z

Restoring removed content which gave context to what is stared here. If course anyone could find that context by searching in Church's biography, but why would they be searching there, and in any case it makes sense to make this information easier to find, in view of its relevance.

← Previous revision		Revision as of 21:39, 5 January 2025
Line 29:		Line 29:
	* The frequency of each letter converges to a limit greater than zero.		* The frequency of each letter converges to a limit greater than zero.
	* For any "admissible" rule, such that it picks out an infinite subsequence <math>(x_{m_i})_i</math> from the string, the frequency of each letter in the subsequence still converges to the same limit.		* For any "admissible" rule, such that it picks out an infinite subsequence <math>(x_{m_i})_i</math> from the string, the frequency of each letter in the subsequence still converges to the same limit.
	Usually the admissible rules are defined to be rules computable by a Turing machine, and we require <math>p=1/2</math>. With this, we have the '''Mises–Wald–Church random sequences'''. This is not a restriction, since given a sequence with <math>p=1/2</math>, we can construct random sequences with any other computable <math>p \in (0, 1)</math>.<ref>{{Cite book \|last1=Li \|first1=Ming \|title=An introduction to Kolmogorov complexity and its applications \|last2=Vitányi \|first2=P. M. \|date=2019 \|publisher=Springer \|isbn=978-3-030-11298-1 \|edition=Fourth \|location=Cham \|chapter=1.9 Randomness}}</ref> (Here, "Church" refers to [[Alonzo Church]].<ref>{{~~cite~~ journal \|~~last1~~=~~Church~~ \|~~first1~~=~~Alonzo~~ \|title=On the concept of a random sequence ~~\|journal=~~Bulletin of the American Mathematical Society \|~~date~~=~~1940~~ \|volume=46 \|issue=2 \|pages=~~130‒135~~ \|doi=10.~~1090~~/~~S0002-9904-1940-07154-X~~ \|~~url~~=~~https://projecteuclid.org/journals/bulletin-of-the-american-mathematical-society/volume-46/issue-2/On-the-concept-of-a-random-sequence/bams/1183502434.full~~\|~~doi-access~~=~~free~~ }}</ref>)		Usually the admissible rules are defined to be rules computable by a Turing machine, and we require <math>p=1/2</math>. With this, we have the '''Mises–Wald–Church random sequences'''. This is not a restriction, since given a sequence with <math>p=1/2</math>, we can construct random sequences with any other computable <math>p \in (0, 1)</math>.<ref>{{Cite book \|last1=Li \|first1=Ming \|title=An introduction to Kolmogorov complexity and its applications \|last2=Vitányi \|first2=P. M. \|date=2019 \|publisher=Springer \|isbn=978-3-030-11298-1 \|edition=Fourth \|location=Cham \|chapter=1.9 Randomness}}</ref> (Here, "Church" refers to [[Alonzo Church]], whose 1940 paper proposed using Turing-computable rules.<ref>{{Cite journal \|last=Copeland \|first=Arthur H. \|date=June 1940 \|title=Alonzo Church. On the concept of a random sequence. ''Bulletin of the American Mathematical Society'', vol. 46 (1940), pp. 130–135. \|type=Review \|journal=The Journal of Symbolic Logic \|language=en \|volume=5 \|issue=2 \|pages=71–72 \|doi=10.2307/2266178 \|jstor=2266178 \|s2cid=124646586 \|issn=0022-4812}}</ref>)

	{{block indent\|		{{block indent\|

Kaarelh: improved language

2025-01-03T20:45:51Z

improved language

← Previous revision		Revision as of 20:45, 3 January 2025
Line 7:		Line 7:
	As different types of algorithms are sometimes considered, ranging from algorithms with specific bounds on their running time to algorithms which may ask questions of an [[oracle machine]], there are different notions of randomness. The most common of these is known as '''Martin-Löf randomness''' ('''K-randomness''' or '''1-randomness'''), but stronger and weaker forms of randomness also exist. When the term "algorithmically random" is used to refer to a particular single (finite or infinite) sequence without clarification, it is usually taken to mean "incompressible" or, in the case the sequence is infinite and prefix algorithmically random (i.e., K-incompressible), "Martin-Löf–Chaitin random".		As different types of algorithms are sometimes considered, ranging from algorithms with specific bounds on their running time to algorithms which may ask questions of an [[oracle machine]], there are different notions of randomness. The most common of these is known as '''Martin-Löf randomness''' ('''K-randomness''' or '''1-randomness'''), but stronger and weaker forms of randomness also exist. When the term "algorithmically random" is used to refer to a particular single (finite or infinite) sequence without clarification, it is usually taken to mean "incompressible" or, in the case the sequence is infinite and prefix algorithmically random (i.e., K-incompressible), "Martin-Löf–Chaitin random".

	Since its inception, Martin-Löf randomness has been shown to admit many equivalent characterizations—in terms of [[data compression\|compression]], randomness tests, and [[gambling]]—that bear little outward resemblance to the original definition, but each of which satisfy our intuitive notion of properties that random sequences ought to have: random sequences should be incompressible, they should pass statistical tests for randomness, and it should be difficult to make money [[betting]] on them. The existence of these multiple definitions of Martin-Löf randomness, and the stability of these definitions under different models of computation, give evidence that Martin-Löf randomness is ~~a fundamental property of mathematics~~ and not an accident of Martin-Löf's particular model.		Since its inception, Martin-Löf randomness has been shown to admit many equivalent characterizations—in terms of [[data compression\|compression]], randomness tests, and [[gambling]]—that bear little outward resemblance to the original definition, but each of which satisfy our intuitive notion of properties that random sequences ought to have: random sequences should be incompressible, they should pass statistical tests for randomness, and it should be difficult to make money [[betting]] on them. The existence of these multiple definitions of Martin-Löf randomness, and the stability of these definitions under different models of computation, give evidence that Martin-Löf randomness is natural and not an accident of Martin-Löf's particular model.

	It is important to disambiguate between algorithmic randomness and stochastic randomness. Unlike algorithmic randomness, which is defined for computable (and thus deterministic) processes, stochastic randomness is usually said to be a property of a sequence that is a priori known to be generated by (or is the outcome of) an [[Independence (probability theory)\|independent]] identically [[Probability distribution\|distributed]] equiprobable stochastic process.		It is important to disambiguate between algorithmic randomness and stochastic randomness. Unlike algorithmic randomness, which is defined for computable (and thus deterministic) processes, stochastic randomness is usually said to be a property of a sequence that is a priori known to be generated by (or is the outcome of) an [[Independence (probability theory)\|independent]] identically [[Probability distribution\|distributed]] equiprobable stochastic process.

Kaltenmeyer: clean up

2024-12-14T23:36:18Z

clean up

← Previous revision		Revision as of 23:36, 14 December 2024
Line 1:		Line 1:
	{{Short description\|Binary sequence}}		{{Short description\|Binary sequence}}
	{{~~distinguish-~~redirect\|Algorithmic randomness\|Randomized algorithms}}Intuitively, an '''algorithmically random sequence''' (or '''[[random sequence]]''') is a [[Sequence#Infinite sequences in theoretical computer science\|sequence]] of binary digits that appears random to any algorithm running on a (prefix-free or not) [[universal Turing machine]]. The notion can be applied analogously to sequences on any finite alphabet (e.g. decimal digits). Random sequences are key objects of study in [[algorithmic information theory]].		{{redirect-distinguish\|Algorithmic randomness\|Randomized algorithms}}
			Intuitively, an '''algorithmically random sequence''' (or '''[[random sequence]]''') is a [[Sequence#Infinite sequences in theoretical computer science\|sequence]] of binary digits that appears random to any algorithm running on a (prefix-free or not) [[universal Turing machine]]. The notion can be applied analogously to sequences on any finite alphabet (e.g. decimal digits). Random sequences are key objects of study in [[algorithmic information theory]].

	In [[measure-theoretic probability theory]], introduced by [[Andrey Kolmogorov]] in 1933, there is ''no such thing'' as a random sequence. For example, consider flipping a fair coin infinitely many times. Any particular sequence, be it <math>0000\dots</math> or <math>011010\dots</math>, has equal probability of exactly zero. There is no way to state that one sequence is "more random" than another sequence, using the language of measure-theoretic probability. However, it is intuitively obvious that <math>011010\dots</math> looks more random than <math>0000\dots</math>. Algorithmic randomness theory formalizes this intuition.		In [[measure-theoretic probability theory]], introduced by [[Andrey Kolmogorov]] in 1933, there is ''no such thing'' as a random sequence. For example, consider flipping a fair coin infinitely many times. Any particular sequence, be it <math>0000\dots</math> or <math>011010\dots</math>, has equal probability of exactly zero. There is no way to state that one sequence is "more random" than another sequence, using the language of measure-theoretic probability. However, it is intuitively obvious that <math>011010\dots</math> looks more random than <math>0000\dots</math>. Algorithmic randomness theory formalizes this intuition.
Line 106:		Line 107:
	By [[Stirling approximation]], <math>\log_2 \binom{N}{pN} \approx N H(p)</math> where <math>H</math> is the [[binary entropy function]]. Thus, the number of bits in this description is:<math display="block"> 2(1 + \epsilon) \log_2 N + (1 + \epsilon) N H(p) + O(1) </math>The first term is for prefix-coding the numbers <math>N</math> and <math>M</math>. The second term is for prefix-coding the number <math>i</math>. (Use [[Elias omega coding]].) The third term is for prefix-coding the rest of the description.		By [[Stirling approximation]], <math>\log_2 \binom{N}{pN} \approx N H(p)</math> where <math>H</math> is the [[binary entropy function]]. Thus, the number of bits in this description is:<math display="block"> 2(1 + \epsilon) \log_2 N + (1 + \epsilon) N H(p) + O(1) </math>The first term is for prefix-coding the numbers <math>N</math> and <math>M</math>. The second term is for prefix-coding the number <math>i</math>. (Use [[Elias omega coding]].) The third term is for prefix-coding the rest of the description.
	When <math> N</math> is large, this description has just <math> \sim H(p) N </math> bits, and so it is compressible, with compression ratio <math> \sim H(p) </math>. In particular, the compression ratio is exactly one (incompressible) only when <math> p = 1/2</math>. (Example 14.2.8 <ref name=":0">{{Cite book \|last1=Cover \|first1=Thomas M. \|title=Elements of Information Theory 2nd Edition \|last2=Thomas \|first2=Joy A. \|date=2006-07-18 \|publisher=Wiley-Interscience \|isbn=978-0-471-24195-9 \|edition=2nd \|location=Hoboken, N.J \|language=en}}</ref>)		When <math> N</math> is large, this description has just <math> \sim H(p) N </math> bits, and so it is compressible, with compression ratio <math> \sim H(p) </math>. In particular, the compression ratio is exactly one (incompressible) only when <math> p = 1/2</math>. (Example 14.2.8 <ref name=":0">{{Cite book \|last1=Cover \|first1=Thomas M. \|title=Elements of Information Theory 2nd Edition \|last2=Thomas \|first2=Joy A. \|date=2006-07-18 \|publisher=Wiley-Interscience \|isbn=978-0-471-24195-9 \|edition=2nd \|location=Hoboken, N.J \|language=en}}</ref>)

	=== Impossibility of a gambling system ===		=== Impossibility of a gambling system ===
	{{Main\|Impossibility of a gambling system}}		{{Main\|Impossibility of a gambling system}}
Line 182:		Line 184:
	\| year = 1997		\| year = 1997
	\| edition = Second}}		\| edition = Second}}
	* {{Cite journal \| last1 = Martin-Löf \| first1 = P. \| author-link=Per Martin-Löf\| year = 1966 \| title = The definition of random sequences \| journal = Information and Control \| volume = 9 \| issue = 6 \| pages = 602–619 \| doi=10.1016/s0019-9958(66)80018-9\| doi-access = }}		* {{Cite journal \| last1 = Martin-Löf \| first1 = P. \| author-link=Per Martin-Löf\| year = 1966 \| title = The definition of random sequences \| journal = Information and Control \| volume = 9 \| issue = 6 \| pages = 602–619 \| doi=10.1016/s0019-9958(66)80018-9\| doi-access =}}
	* {{cite book \| zbl=1169.03034 \| last=Nies \| first=André \| title=Computability and randomness \| series=Oxford Logic Guides \| volume=51 \| location=Oxford \| publisher=Oxford University Press \| year=2009 \| isbn=978-0-19-923076-1 }}		* {{cite book \| zbl=1169.03034 \| last=Nies \| first=André \| title=Computability and randomness \| series=Oxford Logic Guides \| volume=51 \| location=Oxford \| publisher=Oxford University Press \| year=2009 \| isbn=978-0-19-923076-1 }}
	* {{cite journal		* {{cite journal

Citation bot: Removed parameters. | Use this bot. Report bugs. | #UCB_CommandLine

2024-12-02T04:16:13Z

Removed parameters. | Use this bot. Report bugs. | #UCB_CommandLine

← Previous revision		Revision as of 04:16, 2 December 2024
Line 28:		Line 28:
	* The frequency of each letter converges to a limit greater than zero.		* The frequency of each letter converges to a limit greater than zero.
	* For any "admissible" rule, such that it picks out an infinite subsequence <math>(x_{m_i})_i</math> from the string, the frequency of each letter in the subsequence still converges to the same limit.		* For any "admissible" rule, such that it picks out an infinite subsequence <math>(x_{m_i})_i</math> from the string, the frequency of each letter in the subsequence still converges to the same limit.
	Usually the admissible rules are defined to be rules computable by a Turing machine, and we require <math>p=1/2</math>. With this, we have the '''Mises–Wald–Church random sequences'''. This is not a restriction, since given a sequence with <math>p=1/2</math>, we can construct random sequences with any other computable <math>p \in (0, 1)</math>.<ref>{{Cite book \|last1=Li \|first1=Ming \|title=An introduction to Kolmogorov complexity and its applications \|last2=Vitányi \|first2=P. M. \|date=2019 \|publisher=Springer \|isbn=978-3-030-11298-1 \|edition=Fourth \|location=Cham \|chapter=1.9 Randomness}}</ref> (Here, "Church" refers to [[Alonzo Church]].<ref>{{cite journal \|last1=Church \|first1=Alonzo \|title=On the concept of a random sequence \|journal=Bulletin of the American Mathematical Society \|date=1940 \|volume=46 \|issue=2 \|pages=130‒135 \|doi=10.1090/S0002-9904-1940-07154-X ~~\|doi-broken-date=2024-11-20~~ \|url=https://projecteuclid.org/journals/bulletin-of-the-american-mathematical-society/volume-46/issue-2/On-the-concept-of-a-random-sequence/bams/1183502434.full\|doi-access=free }}</ref>)		Usually the admissible rules are defined to be rules computable by a Turing machine, and we require <math>p=1/2</math>. With this, we have the '''Mises–Wald–Church random sequences'''. This is not a restriction, since given a sequence with <math>p=1/2</math>, we can construct random sequences with any other computable <math>p \in (0, 1)</math>.<ref>{{Cite book \|last1=Li \|first1=Ming \|title=An introduction to Kolmogorov complexity and its applications \|last2=Vitányi \|first2=P. M. \|date=2019 \|publisher=Springer \|isbn=978-3-030-11298-1 \|edition=Fourth \|location=Cham \|chapter=1.9 Randomness}}</ref> (Here, "Church" refers to [[Alonzo Church]].<ref>{{cite journal \|last1=Church \|first1=Alonzo \|title=On the concept of a random sequence \|journal=Bulletin of the American Mathematical Society \|date=1940 \|volume=46 \|issue=2 \|pages=130‒135 \|doi=10.1090/S0002-9904-1940-07154-X \|url=https://projecteuclid.org/journals/bulletin-of-the-american-mathematical-society/volume-46/issue-2/On-the-concept-of-a-random-sequence/bams/1183502434.full\|doi-access=free }}</ref>)

	{{block indent\|		{{block indent\|

OAbot: Open access bot: doi updated in citation with #oabot.

2024-11-25T03:26:51Z

Open access bot: doi updated in citation with #oabot.

← Previous revision		Revision as of 03:26, 25 November 2024
Line 28:		Line 28:
	* The frequency of each letter converges to a limit greater than zero.		* The frequency of each letter converges to a limit greater than zero.
	* For any "admissible" rule, such that it picks out an infinite subsequence <math>(x_{m_i})_i</math> from the string, the frequency of each letter in the subsequence still converges to the same limit.		* For any "admissible" rule, such that it picks out an infinite subsequence <math>(x_{m_i})_i</math> from the string, the frequency of each letter in the subsequence still converges to the same limit.
	Usually the admissible rules are defined to be rules computable by a Turing machine, and we require <math>p=1/2</math>. With this, we have the '''Mises–Wald–Church random sequences'''. This is not a restriction, since given a sequence with <math>p=1/2</math>, we can construct random sequences with any other computable <math>p \in (0, 1)</math>.<ref>{{Cite book \|last1=Li \|first1=Ming \|title=An introduction to Kolmogorov complexity and its applications \|last2=Vitányi \|first2=P. M. \|date=2019 \|publisher=Springer \|isbn=978-3-030-11298-1 \|edition=Fourth \|location=Cham \|chapter=1.9 Randomness}}</ref> (Here, "Church" refers to [[Alonzo Church]].<ref>{{cite journal \|last1=Church \|first1=Alonzo \|title=On the concept of a random sequence \|journal=Bulletin of the American Mathematical Society \|date=1940 \|volume=46 \|issue=2 \|pages=130‒135 \|doi=10.1090/S0002-9904-1940-07154-X \|doi-broken-date=2024-11-20 \|url=https://projecteuclid.org/journals/bulletin-of-the-american-mathematical-society/volume-46/issue-2/On-the-concept-of-a-random-sequence/bams/1183502434.full}}</ref>)		Usually the admissible rules are defined to be rules computable by a Turing machine, and we require <math>p=1/2</math>. With this, we have the '''Mises–Wald–Church random sequences'''. This is not a restriction, since given a sequence with <math>p=1/2</math>, we can construct random sequences with any other computable <math>p \in (0, 1)</math>.<ref>{{Cite book \|last1=Li \|first1=Ming \|title=An introduction to Kolmogorov complexity and its applications \|last2=Vitányi \|first2=P. M. \|date=2019 \|publisher=Springer \|isbn=978-3-030-11298-1 \|edition=Fourth \|location=Cham \|chapter=1.9 Randomness}}</ref> (Here, "Church" refers to [[Alonzo Church]].<ref>{{cite journal \|last1=Church \|first1=Alonzo \|title=On the concept of a random sequence \|journal=Bulletin of the American Mathematical Society \|date=1940 \|volume=46 \|issue=2 \|pages=130‒135 \|doi=10.1090/S0002-9904-1940-07154-X \|doi-broken-date=2024-11-20 \|url=https://projecteuclid.org/journals/bulletin-of-the-american-mathematical-society/volume-46/issue-2/On-the-concept-of-a-random-sequence/bams/1183502434.full\|doi-access=free }}</ref>)

	{{block indent\|		{{block indent\|

Citation bot: Added doi-broken-date. | Use this bot. Report bugs. | Suggested by Dominic3203 | Category:Algorithmic information theory | #UCB_Category 14/22

2024-11-20T11:45:00Z

Added doi-broken-date. | Use this bot. Report bugs. | Suggested by Dominic3203 | Category:Algorithmic information theory | #UCB_Category 14/22

← Previous revision		Revision as of 11:45, 20 November 2024
Line 28:		Line 28:
	* The frequency of each letter converges to a limit greater than zero.		* The frequency of each letter converges to a limit greater than zero.
	* For any "admissible" rule, such that it picks out an infinite subsequence <math>(x_{m_i})_i</math> from the string, the frequency of each letter in the subsequence still converges to the same limit.		* For any "admissible" rule, such that it picks out an infinite subsequence <math>(x_{m_i})_i</math> from the string, the frequency of each letter in the subsequence still converges to the same limit.
	Usually the admissible rules are defined to be rules computable by a Turing machine, and we require <math>p=1/2</math>. With this, we have the '''Mises–Wald–Church random sequences'''. This is not a restriction, since given a sequence with <math>p=1/2</math>, we can construct random sequences with any other computable <math>p \in (0, 1)</math>.<ref>{{Cite book \|last1=Li \|first1=Ming \|title=An introduction to Kolmogorov complexity and its applications \|last2=Vitányi \|first2=P. M. \|date=2019 \|publisher=Springer \|isbn=978-3-030-11298-1 \|edition=Fourth \|location=Cham \|chapter=1.9 Randomness}}</ref> (Here, "Church" refers to [[Alonzo Church]].<ref>{{cite journal \|last1=Church \|first1=Alonzo \|title=On the concept of a random sequence \|journal=Bulletin of the American Mathematical Society \|date=1940 \|volume=46 \|issue=2 \|pages=130‒135 \|doi=10.1090/S0002-9904-1940-07154-X \|url=https://projecteuclid.org/journals/bulletin-of-the-american-mathematical-society/volume-46/issue-2/On-the-concept-of-a-random-sequence/bams/1183502434.full}}</ref>)		Usually the admissible rules are defined to be rules computable by a Turing machine, and we require <math>p=1/2</math>. With this, we have the '''Mises–Wald–Church random sequences'''. This is not a restriction, since given a sequence with <math>p=1/2</math>, we can construct random sequences with any other computable <math>p \in (0, 1)</math>.<ref>{{Cite book \|last1=Li \|first1=Ming \|title=An introduction to Kolmogorov complexity and its applications \|last2=Vitányi \|first2=P. M. \|date=2019 \|publisher=Springer \|isbn=978-3-030-11298-1 \|edition=Fourth \|location=Cham \|chapter=1.9 Randomness}}</ref> (Here, "Church" refers to [[Alonzo Church]].<ref>{{cite journal \|last1=Church \|first1=Alonzo \|title=On the concept of a random sequence \|journal=Bulletin of the American Mathematical Society \|date=1940 \|volume=46 \|issue=2 \|pages=130‒135 \|doi=10.1090/S0002-9904-1940-07154-X \|doi-broken-date=2024-11-20 \|url=https://projecteuclid.org/journals/bulletin-of-the-american-mathematical-society/volume-46/issue-2/On-the-concept-of-a-random-sequence/bams/1183502434.full}}</ref>)

	{{block indent\|		{{block indent\|

Citation bot: Removed parameters. | Use this bot. Report bugs. | Suggested by Dominic3203 | Category:Algorithmic information theory | #UCB_Category 13/22

2024-11-20T11:31:19Z

Removed parameters. | Use this bot. Report bugs. | Suggested by Dominic3203 | Category:Algorithmic information theory | #UCB_Category 13/22

← Previous revision		Revision as of 11:31, 20 November 2024
Line 28:		Line 28:
	* The frequency of each letter converges to a limit greater than zero.		* The frequency of each letter converges to a limit greater than zero.
	* For any "admissible" rule, such that it picks out an infinite subsequence <math>(x_{m_i})_i</math> from the string, the frequency of each letter in the subsequence still converges to the same limit.		* For any "admissible" rule, such that it picks out an infinite subsequence <math>(x_{m_i})_i</math> from the string, the frequency of each letter in the subsequence still converges to the same limit.
	Usually the admissible rules are defined to be rules computable by a Turing machine, and we require <math>p=1/2</math>. With this, we have the '''Mises–Wald–Church random sequences'''. This is not a restriction, since given a sequence with <math>p=1/2</math>, we can construct random sequences with any other computable <math>p \in (0, 1)</math>.<ref>{{Cite book \|last1=Li \|first1=Ming \|title=An introduction to Kolmogorov complexity and its applications \|last2=Vitányi \|first2=P. M. \|date=2019 \|publisher=Springer \|isbn=978-3-030-11298-1 \|edition=Fourth \|location=Cham \|chapter=1.9 Randomness}}</ref> (Here, "Church" refers to [[Alonzo Church]].<ref>{{cite journal \|last1=Church \|first1=Alonzo \|title=On the concept of a random sequence \|journal=Bulletin of the American Mathematical Society \|date=1940 \|volume=46 \|issue=2 \|pages=130‒135 \|doi=10.1090/S0002-9904-1940-07154-X ~~\|doi-broken-date=2024-11-20~~ \|url=https://projecteuclid.org/journals/bulletin-of-the-american-mathematical-society/volume-46/issue-2/On-the-concept-of-a-random-sequence/bams/1183502434.full}}</ref>)		Usually the admissible rules are defined to be rules computable by a Turing machine, and we require <math>p=1/2</math>. With this, we have the '''Mises–Wald–Church random sequences'''. This is not a restriction, since given a sequence with <math>p=1/2</math>, we can construct random sequences with any other computable <math>p \in (0, 1)</math>.<ref>{{Cite book \|last1=Li \|first1=Ming \|title=An introduction to Kolmogorov complexity and its applications \|last2=Vitányi \|first2=P. M. \|date=2019 \|publisher=Springer \|isbn=978-3-030-11298-1 \|edition=Fourth \|location=Cham \|chapter=1.9 Randomness}}</ref> (Here, "Church" refers to [[Alonzo Church]].<ref>{{cite journal \|last1=Church \|first1=Alonzo \|title=On the concept of a random sequence \|journal=Bulletin of the American Mathematical Society \|date=1940 \|volume=46 \|issue=2 \|pages=130‒135 \|doi=10.1090/S0002-9904-1940-07154-X \|url=https://projecteuclid.org/journals/bulletin-of-the-american-mathematical-society/volume-46/issue-2/On-the-concept-of-a-random-sequence/bams/1183502434.full}}</ref>)

	{{block indent\|		{{block indent\|

Citation bot: Add: doi-broken-date, doi. | Use this bot. Report bugs. | Suggested by Dominic3203 | Category:Algorithmic information theory | #UCB_Category 18/22

2024-11-20T11:20:21Z

Add: doi-broken-date, doi. | Use this bot. Report bugs. | Suggested by Dominic3203 | Category:Algorithmic information theory | #UCB_Category 18/22

← Previous revision		Revision as of 11:20, 20 November 2024
Line 28:		Line 28:
	* The frequency of each letter converges to a limit greater than zero.		* The frequency of each letter converges to a limit greater than zero.
	* For any "admissible" rule, such that it picks out an infinite subsequence <math>(x_{m_i})_i</math> from the string, the frequency of each letter in the subsequence still converges to the same limit.		* For any "admissible" rule, such that it picks out an infinite subsequence <math>(x_{m_i})_i</math> from the string, the frequency of each letter in the subsequence still converges to the same limit.
	Usually the admissible rules are defined to be rules computable by a Turing machine, and we require <math>p=1/2</math>. With this, we have the '''Mises–Wald–Church random sequences'''. This is not a restriction, since given a sequence with <math>p=1/2</math>, we can construct random sequences with any other computable <math>p \in (0, 1)</math>.<ref>{{Cite book \|last1=Li \|first1=Ming \|title=An introduction to Kolmogorov complexity and its applications \|last2=Vitányi \|first2=P. M. \|date=2019 \|publisher=Springer \|isbn=978-3-030-11298-1 \|edition=Fourth \|location=Cham \|chapter=1.9 Randomness}}</ref> (Here, "Church" refers to [[Alonzo Church]].<ref>{{cite journal \|last1=Church \|first1=Alonzo \|title=On the concept of a random sequence \|journal=Bulletin of the American Mathematical Society \|date=1940 \|volume=46 \|issue=2 \|pages=130‒135 \|url=https://projecteuclid.org/journals/bulletin-of-the-american-mathematical-society/volume-46/issue-2/On-the-concept-of-a-random-sequence/bams/1183502434.full}}</ref>)		Usually the admissible rules are defined to be rules computable by a Turing machine, and we require <math>p=1/2</math>. With this, we have the '''Mises–Wald–Church random sequences'''. This is not a restriction, since given a sequence with <math>p=1/2</math>, we can construct random sequences with any other computable <math>p \in (0, 1)</math>.<ref>{{Cite book \|last1=Li \|first1=Ming \|title=An introduction to Kolmogorov complexity and its applications \|last2=Vitányi \|first2=P. M. \|date=2019 \|publisher=Springer \|isbn=978-3-030-11298-1 \|edition=Fourth \|location=Cham \|chapter=1.9 Randomness}}</ref> (Here, "Church" refers to [[Alonzo Church]].<ref>{{cite journal \|last1=Church \|first1=Alonzo \|title=On the concept of a random sequence \|journal=Bulletin of the American Mathematical Society \|date=1940 \|volume=46 \|issue=2 \|pages=130‒135 \|doi=10.1090/S0002-9904-1940-07154-X \|doi-broken-date=2024-11-20 \|url=https://projecteuclid.org/journals/bulletin-of-the-american-mathematical-society/volume-46/issue-2/On-the-concept-of-a-random-sequence/bams/1183502434.full}}</ref>)

	{{block indent\|		{{block indent\|

← Previous revision		Revision as of 13:10, 3 April 2025
Line 9:		Line 9:
	Since its inception, Martin-Löf randomness has been shown to admit many equivalent characterizations—in terms of [[data compression\|compression]], randomness tests, and [[gambling]]—that bear little outward resemblance to the original definition, but each of which satisfies our intuitive notion of properties that random sequences ought to have: random sequences should be incompressible, they should pass statistical tests for randomness, and it should be difficult to make money [[betting]] on them. The existence of these multiple definitions of Martin-Löf randomness, and the stability of these definitions under different models of computation, give evidence that Martin-Löf randomness is natural and not an accident of Martin-Löf's particular model.		Since its inception, Martin-Löf randomness has been shown to admit many equivalent characterizations—in terms of [[data compression\|compression]], randomness tests, and [[gambling]]—that bear little outward resemblance to the original definition, but each of which satisfies our intuitive notion of properties that random sequences ought to have: random sequences should be incompressible, they should pass statistical tests for randomness, and it should be difficult to make money [[betting]] on them. The existence of these multiple definitions of Martin-Löf randomness, and the stability of these definitions under different models of computation, give evidence that Martin-Löf randomness is natural and not an accident of Martin-Löf's particular model.

	It is important to disambiguate between algorithmic randomness and stochastic randomness. Unlike algorithmic randomness, which is defined for computable (and thus deterministic) processes, stochastic randomness is usually said to be a property of a sequence that is a priori known to be generated by (or is the outcome of) an [[Independence (probability theory)\|independent]] identically [[Probability distribution\|distributed]] equiprobable stochastic process.		It is important to disambiguate between algorithmic randomness and stochastic randomness. Unlike algorithmic randomness, which is defined for computable (and thus deterministic) processes, stochastic randomness is usually said to be a property of a sequence that is a priori known to be generated by (or is the outcome of) an [[Independence (probability theory)\|independent]] identically [[Probability distribution\|distributed]] equiprobable [[stochastic process]].

	Because infinite sequences of binary digits can be identified with real numbers in the unit interval, random binary sequences are often called '''(algorithmically) random real numbers'''. Additionally, infinite binary sequences correspond to characteristic functions of sets of natural numbers; therefore those sequences might be seen as sets of natural numbers.		Because infinite sequences of binary digits can be identified with real numbers in the unit interval, random binary sequences are often called '''(algorithmically) random real numbers'''. Additionally, infinite binary sequences correspond to characteristic functions of sets of natural numbers; therefore those sequences might be seen as sets of natural numbers.
Line 22:		Line 22:
	* For any "admissible" rule, such that it picks out an infinite subsequence <math>(x_{m_i})_i</math> from the string, we still have <math>\lim_n \frac 1n \sum_{i=1}^n x_{m_i} = p </math>. He called this principle "[[impossibility of a gambling system]]".		* For any "admissible" rule, such that it picks out an infinite subsequence <math>(x_{m_i})_i</math> from the string, we still have <math>\lim_n \frac 1n \sum_{i=1}^n x_{m_i} = p </math>. He called this principle "[[impossibility of a gambling system]]".

	To pick out a subsequence, first pick a binary function <math>\phi</math>, such that given any binary string <math>x_{1:k}</math>, it outputs either 0 or 1. If it outputs 1, then we add <math>x_{k+1}</math> to the subsequence, else we continue. In this definition, some admissible rules might abstain forever on some sequences, and thus fail to pick out an infinite subsequence. We only consider those that do pick an infinite subsequence.		To pick out a [[subsequence]], first pick a binary function <math>\phi</math>, such that given any binary string <math>x_{1:k}</math>, it outputs either 0 or 1. If it outputs 1, then we add <math>x_{k+1}</math> to the subsequence, else we continue. In this definition, some admissible rules might abstain forever on some sequences, and thus fail to pick out an infinite subsequence. We only consider those that do pick an infinite subsequence.

	Stated in another way, each infinite binary string is a coin-flip game, and an admissible rule is a way for a gambler to decide when to place bets. A collective is a coin-flip game where there is no way for one gambler to do better than another over the long run. That is, there is no gambling system that works for the game.		Stated in another way, each infinite binary string is a coin-flip game, and an admissible rule is a way for a gambler to decide when to place bets. A collective is a coin-flip game where there is no way for one gambler to do better than another over the long run. That is, there is no gambling system that works for the game.
Line 70:		Line 70:
	* '''Algorithmic complexity''' (Chaitin 1969, Schnorr 1973, Levin 1973): Algorithmic complexity (also known as (prefix-free) [[Kolmogorov complexity]] or program-size complexity) can be thought of as a lower bound on the algorithmic compressibility of a finite sequence (of characters or binary digits). It assigns to each such sequence ''w'' a natural number ''K(w)'' that, intuitively, measures the minimum length of a computer program (written in some fixed programming language) that takes no input and will output ''w'' when run. The complexity is required to be prefix-free: The program (a sequence of 0 and 1) is followed by an infinite string of 0s, and the length of the program (assuming it halts) includes the number of zeroes to the right of the program that the universal Turing machine reads. The additional requirement is needed because we can choose a length such that the length codes information about the substring. Given a natural number ''c'' and a sequence ''w'', we say that ''w'' is '''''c''-incompressible''' if <math>K(w) \geq \|w\| - c </math>.		* '''Algorithmic complexity''' (Chaitin 1969, Schnorr 1973, Levin 1973): Algorithmic complexity (also known as (prefix-free) [[Kolmogorov complexity]] or program-size complexity) can be thought of as a lower bound on the algorithmic compressibility of a finite sequence (of characters or binary digits). It assigns to each such sequence ''w'' a natural number ''K(w)'' that, intuitively, measures the minimum length of a computer program (written in some fixed programming language) that takes no input and will output ''w'' when run. The complexity is required to be prefix-free: The program (a sequence of 0 and 1) is followed by an infinite string of 0s, and the length of the program (assuming it halts) includes the number of zeroes to the right of the program that the universal Turing machine reads. The additional requirement is needed because we can choose a length such that the length codes information about the substring. Given a natural number ''c'' and a sequence ''w'', we say that ''w'' is '''''c''-incompressible''' if <math>K(w) \geq \|w\| - c </math>.
	:''An infinite sequence ''S'' is Martin-Löf random if and only if there is a constant ''c'' such that all of ''S''{{'s}} finite [[Prefix (computer science)\|prefixes]] are ''c''-incompressible. More succinctly, <math>K(w) \geq \|w\| - O(1) </math>''.		:''An infinite sequence ''S'' is Martin-Löf random if and only if there is a constant ''c'' such that all of ''S''{{'s}} finite [[Prefix (computer science)\|prefixes]] are ''c''-incompressible. More succinctly, <math>K(w) \geq \|w\| - O(1) </math>''.
	* '''Constructive null covers''' (Martin-Löf 1966): This is Martin-Löf's original definition. For a finite binary string ''w'' we let ''C<sub>w</sub>'' denote the '''cylinder generated by''' ''w''. This is the set of all infinite sequences beginning with ''w'', which is a basic open set in [[Cantor space]]. The '''product [[measure (mathematics)\|measure]]''' μ(''C<sub>w</sub>'') of the cylinder generated by ''w'' is defined to be 2<sup>−\|''w''\|</sup>. Every open subset of Cantor space is the union of a countable sequence of disjoint basic open sets, and the measure of an open set is the sum of the measures of any such sequence. An ''effective open set'' is an open set that is the union of the sequence of basic open sets determined by a [[recursively enumerable]] sequence of binary strings. A ''constructive null cover'' or ''effective measure ''0'' set'' is a recursively enumerable sequence <math>U_i</math> of effective open sets such that <math>U_{i+1} \subseteq U_i</math> and <math>\mu (U_i) \leq 2^{-i}</math> for each natural number ''i''. Every effective null cover determines a [[G-delta set\|<math>G_\delta</math> set]] of measure 0, namely the intersection of the sets <math>U_i</math>.		* '''Constructive null covers''' (Martin-Löf 1966): This is Martin-Löf's original definition. For a finite binary string ''w'' we let ''C<sub>w</sub>'' denote the '''cylinder generated by''' ''w''. This is the set of all infinite sequences beginning with ''w'', which is a basic [[open set]] in [[Cantor space]]. The '''product [[measure (mathematics)\|measure]]''' μ(''C<sub>w</sub>'') of the cylinder generated by ''w'' is defined to be 2<sup>−\|''w''\|</sup>. Every open subset of Cantor space is the union of a countable sequence of disjoint basic open sets, and the measure of an open set is the sum of the measures of any such sequence. An ''effective open set'' is an open set that is the union of the sequence of basic open sets determined by a [[recursively enumerable]] sequence of binary strings. A ''constructive null cover'' or ''effective measure ''0'' set'' is a recursively enumerable sequence <math>U_i</math> of effective open sets such that <math>U_{i+1} \subseteq U_i</math> and <math>\mu (U_i) \leq 2^{-i}</math> for each natural number ''i''. Every effective null cover determines a [[G-delta set\|<math>G_\delta</math> set]] of measure 0, namely the intersection of the sets <math>U_i</math>.
	:''A sequence is defined to be Martin-Löf random if it is not contained in any <math>G_\delta</math> set determined by a constructive null cover.''		:''A sequence is defined to be Martin-Löf random if it is not contained in any <math>G_\delta</math> set determined by a constructive null cover.''
	* '''Constructive martingales''' (Schnorr 1971): A [[Martingale (probability theory)\|martingale]] is a function <math>d:\{0,1\}^\to[0,\infty)</math> such that, for all finite strings ''w'', <math>d(w) = (d(w^\smallfrown 0) + d(w^\smallfrown 1))/2</math>, where <math>a^\smallfrown b</math> is the [[concatenation]] of the strings ''a'' and ''b''. This is called the "fairness condition": if a martingale is viewed as a betting strategy, then the above condition requires that the bettor plays against fair odds. A martingale ''d'' is said to '''succeed''' on a sequence ''S'' if <math>\limsup_{n\to\infty} d(S \upharpoonright n) = \infty,</math> where <math>S \upharpoonright n</math> is the first ''n'' bits of ''S''. A martingale ''d'' is '''constructive''' (also known as '''weakly computable''', '''lower semi-computable''') if there exists a computable function <math>\widehat{d}:\{0,1\}^\times\N\to{\mathbb{Q}}</math> such that, for all finite binary strings ''w''		* '''Constructive martingales''' (Schnorr 1971): A [[Martingale (probability theory)\|martingale]] is a function <math>d:\{0,1\}^\to[0,\infty)</math> such that, for all finite strings ''w'', <math>d(w) = (d(w^\smallfrown 0) + d(w^\smallfrown 1))/2</math>, where <math>a^\smallfrown b</math> is the [[concatenation]] of the strings ''a'' and ''b''. This is called the "fairness condition": if a martingale is viewed as a betting strategy, then the above condition requires that the bettor plays against fair odds. A martingale ''d'' is said to '''succeed''' on a sequence ''S'' if <math>\limsup_{n\to\infty} d(S \upharpoonright n) = \infty,</math> where <math>S \upharpoonright n</math> is the first ''n'' bits of ''S''. A martingale ''d'' is '''constructive''' (also known as '''weakly computable''', '''lower semi-computable''') if there exists a computable function <math>\widehat{d}:\{0,1\}^\times\N\to{\mathbb{Q}}</math> such that, for all finite binary strings ''w''