258:
than martingales used in traditional probability theory. Schnorr showed how the existence of a selective betting strategy implied the existence of a selection rule for a biased sub-sequence. If one only requires a recursive martingale to succeed on a sequence instead of constructively succeed on a
106:
The sub-sequence selection criterion imposed by von Mises is important, because although 0101010101... is not biased, by selecting the odd positions, we get 000000... which is not random. Von Mises never totally formalized his definition of a proper selection rule for sub-sequences, but in 1940
63:
avoids a definition of a random sequence. Traditional probability theory does not state if a specific sequence is random, but generally proceeds to discuss the properties of random variables and stochastic sequences assuming some definition of randomness. The
143:
independently proposed a more permissive selection rule. In their view Church's recursive function definition was too restrictive in that it read the elements in order. Instead they proposed a rule based on a partially computable process which having read
191:
approach. This approach started with the work of
Richard von Mises and Alonzo Church. In the 1960s Per Martin-Löf noticed that the sets coding such frequency-based stochastic properties are a special kind of
54:
stated in 1951: "A random sequence is a vague notion... in which each term is unpredictable to the uninitiated and whose digits pass a certain number of tests traditional with statisticians".
135:
During the 20th century various technical approaches to defining random sequences were developed and now three distinct paradigms can be identified. In the mid 1960s,
410:
Laurant
Bienvenu "Kolmogorov Loveland Stochasticity" in STACS 2007: 24th Annual Symposium on Theoretical Aspects of Computer Science by Wolfgang Thomas
156:
237:, it is not so random. The dual concept of randomness is compressibility ‒ the more random a sequence is, the less compressible, and vice versa.
103:
i.e. the frequency of zeros goes to 1/2 and every sub-sequence we can select from it by a "proper" method of selection is also not biased.
151:
elements of the sequence, decides if it wants to select another element which has not been read yet. This definition is often called
159:
who showed that there is a
Kolmogorov–Loveland stochastic sequence which does not conform to the general notion of randomness.
96:
174:. Kolmogorov's definition of a random string was that it is random if it has no description shorter than itself via a
615:
510:
415:
385:
365:
345:
196:
sets, and that a more general and smooth definition can be obtained by considering all effectively measure zero sets.
119: + 1. Church was a pioneer in the field of computable functions, and the definition he made relied on the
311:
675:
255:
170:. His original definition involved measure theory, but it was later shown that it can be expressed in terms of
670:
642:
610:
in
Automata, languages and programming: 29th international colloquium, ICALP 2002, by Peter Widmayer et al.
637:
115:
which having read the first N elements of the sequence decides if it wants to select element number
293:
99:, von Mises defined an infinite sequence of zeros and ones as random if it is not biased by having the
632:
175:
584:
288:
655:
579:
298:
167:
88:
283:
222:
171:
269:
In most cases, theorems relating the three paradigms (often equivalence) have been proven.
120:
69:
166:
introduced a new notion which is now generally considered the most satisfactory notion of
112:
8:
209:
approach. This paradigm was championed by A. N. Kolmogorov along with contributions from
505:
in
Mathematical foundations of computer science 2004: by Jiřà Fiala, Václav Koubek 2004
263:
showed that recursive randomness concept is different from
Schnorr's randomness concept.
540:
57:
21:
593:
611:
506:
411:
381:
361:
341:
84:
558:
523:
Schnorr, C. P. (1971). "A unified approach to the definition of a random sequence".
449:
432:
163:
83:
was one of the first mathematicians to formally address randomness in 1909. In 1919
589:
544:
532:
444:
251:
217:. For finite sequences, Kolmogorov defines randomness of a binary string of length
136:
65:
214:
33:
140:
649:
80:
664:
428:
108:
91:, which was inspired by the law of large numbers, although he used the term
210:
193:
51:
380:
by
Vladimir Andreevich UspenskiÄ, AlekseÄ, LĘąvovich Semenov 1993 Springer
181:
Three basic paradigms for dealing with random sequences have now emerged:
260:
229:. In other words, if the Kolmogorov complexity of the string is close to
536:
278:
25:
29:
570:
Wang, Yongge (1999). "A separation of two randomness concepts".
399:
Les probabilites denombrables et leurs applications arithmetique
68:
considered the statement "let us consider a random sequence" an
465:
Three approaches to the quantitative definition of information
490:
An introduction to
Kolmogorov complexity and its applications
478:
A new interpretation of von Mises' concept of random sequence
259:
sequence, then one gets the concept of recursive randomness.
36:
and many statistical discussions begin with the words "let
557:
Yongge Wang: Randomness and
Complexity. PhD Thesis, 1996.
492:
by Ming Li, P. M. B. Vitányi 1997 0387948686 pages 149–151
652:
on frequency stability. Why humans can't "guess" randomly
467:
Problems of
Information and Transmission, 1(1):1–7, 1965.
254:
and uses a slightly different definition of constructive
95:
rather than random sequence. Using the concept of the
233:, it is very random; if the complexity is far below
123:for computability. This definition is often called
28:. The concept generally relies on the notion of a
559:http://webpages.uncc.edu/yonwang/papers/IPL97.pdf
662:
480:Z. Math. Logik Grundlagen Math 12 (1966) 279–294
503:Some Recent Progress in Algorithmic Randomness
358:Inevitable Randomness in Discrete Mathematics
155:. But this method was considered too weak by
50:be independent random variables...". Yet as
401:Rend. Circ. Mat. Palermo 27 (1909) 247–271
583:
448:
522:
378:Algorithms: main ideas and applications
663:
427:
336:"What is meant by the word Random" in
569:
130:
433:"On the Concept of Random Sequence"
13:
250:approach. This paradigm is due to
97:impossibility of a gambling system
14:
687:
625:
608:Kolmogorov Loveland Stochasticity
317:The American Mathematical Monthly
153:Kolmogorov–Loveland stochasticity
656:Randomness tests by Terry Ritter
319:, Vol. 109, 2002, pp. 46–63
75:
600:
563:
551:
516:
495:
450:10.1090/S0002-9904-1940-07154-X
572:Information Processing Letters
483:
470:
457:
421:
404:
391:
371:
351:
330:
1:
594:10.1016/S0020-0190(98)00202-6
304:
189:frequency / measure-theoretic
87:gave the first definition of
338:Mathematics and common sense
207:complexity / compressibility
101:frequency stability property
58:Axiomatic probability theory
7:
638:Encyclopedia of Mathematics
525:Mathematical Systems Theory
272:
225:) normalized by the length
10:
692:
313:What Is a Random Sequence?
294:Seven states of randomness
340:by Philip J. Davis 2006
323:
176:universal Turing machine
289:Random number generator
125:Mises–Church randomness
676:Statistical randomness
299:Statistical randomness
168:algorithmic randomness
89:algorithmic randomness
437:Bull. Amer. Math. Soc
284:History of randomness
223:Kolmogorov complexity
172:Kolmogorov complexity
671:Sequences and series
360:by JĂłzsef Beck 2009
121:Church Turing Thesis
221:as the entropy (or
537:10.1007/bf01694181
463:A. N. Kolmogorov,
310:Sergio B. Volchan
113:recursive function
111:defined it as any
22:probability theory
633:"Random sequence"
606:Wolfgang Merkle,
131:Modern approaches
85:Richard von Mises
70:abuse of language
16:The concept of a
683:
646:
619:
604:
598:
597:
587:
567:
561:
555:
549:
548:
520:
514:
499:
493:
487:
481:
474:
468:
461:
455:
454:
452:
425:
419:
408:
402:
395:
389:
375:
369:
355:
349:
334:
252:Claus P. Schnorr
137:A. N. Kolmogorov
34:random variables
20:is essential in
691:
690:
686:
685:
684:
682:
681:
680:
661:
660:
631:
628:
623:
622:
605:
601:
568:
564:
556:
552:
521:
517:
500:
496:
488:
484:
476:D.W. Loveland,
475:
471:
462:
458:
426:
422:
409:
405:
396:
392:
376:
372:
356:
352:
335:
331:
326:
307:
275:
215:Gregory Chaitin
133:
78:
66:Bourbaki school
48:
42:
18:random sequence
12:
11:
5:
689:
679:
678:
673:
659:
658:
653:
647:
627:
626:External links
624:
621:
620:
599:
578:(3): 115–118.
562:
550:
531:(3): 246–258.
515:
494:
482:
469:
456:
443:(2): 130–136.
429:Church, Alonzo
420:
403:
390:
370:
350:
328:
327:
325:
322:
321:
320:
306:
303:
302:
301:
296:
291:
286:
281:
274:
271:
267:
266:
265:
264:
248:predictability
241:
240:
239:
238:
200:
199:
198:
197:
164:Per Martin-Löf
157:Alexander Shen
141:D. W. Loveland
132:
129:
77:
74:
46:
40:
9:
6:
4:
3:
2:
688:
677:
674:
672:
669:
668:
666:
657:
654:
651:
648:
644:
640:
639:
634:
630:
629:
617:
616:3-540-43864-5
613:
609:
603:
595:
591:
586:
585:10.1.1.46.199
581:
577:
573:
566:
560:
554:
546:
542:
538:
534:
530:
526:
519:
512:
511:3-540-22823-3
508:
504:
498:
491:
486:
479:
473:
466:
460:
451:
446:
442:
438:
434:
430:
424:
417:
416:3-540-70917-7
413:
407:
400:
394:
387:
386:0-7923-2210-X
383:
379:
374:
367:
366:0-8218-4756-2
363:
359:
354:
348:pages 180-182
347:
346:1-56881-270-1
343:
339:
333:
329:
318:
315:
314:
309:
308:
300:
297:
295:
292:
290:
287:
285:
282:
280:
277:
276:
270:
262:
257:
253:
249:
245:
244:
243:
242:
236:
232:
228:
224:
220:
216:
212:
208:
204:
203:
202:
201:
195:
190:
186:
185:
184:
183:
182:
179:
177:
173:
169:
165:
160:
158:
154:
150:
147:
142:
138:
128:
126:
122:
118:
114:
110:
109:Alonzo Church
104:
102:
98:
94:
90:
86:
82:
76:Early history
73:
71:
67:
62:
59:
55:
53:
49:
39:
35:
31:
27:
23:
19:
636:
607:
602:
575:
571:
565:
553:
528:
524:
518:
502:
497:
489:
485:
477:
472:
464:
459:
440:
436:
423:
406:
398:
393:
377:
373:
357:
353:
337:
332:
316:
312:
268:
247:
234:
230:
226:
218:
211:Leonid Levin
206:
194:measure zero
188:
180:
161:
152:
148:
145:
134:
124:
116:
105:
100:
92:
79:
61:deliberately
60:
56:
52:D. H. Lehmer
44:
37:
17:
15:
501:R. Downey,
261:Yongge Wang
256:martingales
81:Émile Borel
665:Categories
397:E. Borel,
305:References
279:Randomness
93:collective
26:statistics
643:EMS Press
580:CiteSeerX
618:page 391
431:(1940).
418:page 260
388:page 166
273:See also
162:In 1966
30:sequence
645:, 2001
545:8931514
513:page 44
368:page 44
614:
582:
543:
509:
414:
384:
364:
344:
650:Video
541:S2CID
324:Notes
43:,...,
612:ISBN
507:ISBN
412:ISBN
382:ISBN
362:ISBN
342:ISBN
246:The
213:and
205:The
187:The
139:and
24:and
590:doi
533:doi
445:doi
146:any
72:.
32:of
667::
641:,
635:,
588:.
576:69
574:.
539:.
527:.
441:46
439:.
435:.
178:.
127:.
596:.
592::
547:.
535::
529:5
453:.
447::
235:n
231:n
227:n
219:n
149:N
117:N
47:n
45:X
41:1
38:X
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.