数理解析研究所講究録932 巻 1995 年 118-124

118

On the notions of randomness
Mariko Yasugi
Faculty of Science, Kyoto Sangyo University
Kita-ku, Kyoto 603, Japan-mail: yasugi@cc.kyoto-su.ac.jp.
$\mathrm{e}$Abstract
A speculation on von Mises’ type notion of randomness will be presented.
Ideas proposed by Doob, Church and Loveland on this theme will first beoutlined, and then a principle of selecting subsequences will be proposed.
Introduction
The notion of randomness with coin-tossing as a typical model has attracted many mathematicians, including mathematical logicians. As is known,
von Mises attempted to give a mathematical formulation to it in terms ofthe concept Kollektiv and developed the theory of Kollektiv. We will not go
into the theory of Kollektiv, but will explain briefly some of the succeeding
works by Doob, Church and Loveland.
In order to make the story simple, we will consider an infinite sequenceof two symbols, and , meaning head and tail. That is, the universe of, where is the set $\{h, t\}$ and is the set of positive integers.
discourse is
The question is, how to characterise random ones among the sequences in.
What the predecessors above agree on the notion of randomness is thefollowing.
said to be random if it satisfies.
a sequence fromLet
if is , and if it is .
the conditions (1) and (2) below. Let
converges to a real number as tends to , where(1)$h$$\Omega^{\mathrm{N}}$$t$$\mathrm{N}$$\Omega$$\Omega^{\mathrm{N}}$$\Omega^{\mathrm{N}}$$\{a_{i}\}\mathrm{b}\mathrm{e}$$\{a_{i}\}\mathrm{i}\mathrm{s}$$\sigma(a_{i})\mathrm{d}\mathrm{e}\mathrm{n}\mathrm{o}\mathrm{t}\mathrm{e}1$$\Sigma_{i=1}^{n}\sigma(ai)/n$$0<p<1$ .

$p$$a_{i}$

$n$

$h$

$0$

$\infty$

$t$

119

. Thenbe any admissible subsequence ofas tends to .
Everybody would agree on (1).
A subsequence is admissible if it is chosen according to some principleof selechon. It is this principle that has to be speculated on and, hopefully,settled. It would probably be agreed thatmay depend only on information with reselection of an elementgards to some finitely many elements of the sequence excepting .
as the requirement for a selection function of admissible
Let us setsubsequences.
We expect that there be a principle, which I temporarily call , such that,, it is determined by whether to select or not.
given a sequence. It is obvious
is thus expected to contain some (local) information on
besubsequences
ought to regulate the selection so that not all thethatselected.
Doob in [1] sets a scheme called a system, representing a principle .
A system is a sequence of functions(2) Letconverges to$\Sigma_{k=1}^{j}\sigma(an_{k})/j$$\{a_{i}\}$$\{a_{n_{\mathrm{j}}}\}$

$j$

$p$

$\infty$$(^{*})$$a_{i}$$a_{i}$$(^{*})$$\mathrm{P}$$\mathrm{P}$$\mathrm{P}$$\{a_{i}\}$$a_{i}$$\{a_{i}\}$$\mathrm{P}$$P$$\tau_{1},$$\tau_{2(}a_{1}),$ $\tau 3(a_{1}, a_{2}),$$\cdots,$$\tau i(a1, \cdots, ai-1),$ $\cdots$

where the values of the functions are yes or $no$ .
is a constant, meaning that be chosen or not by default.
$a_{i-1}>$ .
decides whether to select or not according to information on $<a_{1},$Betting in gambling is a typical model of this system.
In [1], it is demonstrated that ”a successful system is impossible” ; thatis, ”betting in accordance with it leaves the player the same position as if
he had bet on the result of each trial.”
This version of the selection rule has the property that
, whether be selected or not depends only on informa(A) given a$a_{i-1}>$ .
tion with regards to $<a_{1},$It is not clear, however, what kind of a function be allowed for a system
Church in [2] proposed recursive functions as candidates of such. Let me
explain his idea with my phrases.
be a sequence of positive
Let be any recursive function, and let
integers defined as follows.

$\tau_{i}(a_{1,i-1}\ldots, a)$$a_{1}$$\tau_{1}$$\cdots,$$a_{i}$$\mathrm{i}\mathrm{n}$$\mathrm{P}$$\{a_{i}\}$$a_{i}$$\cdots,$$\phi$$\{b_{n}\}$$b_{1}:=1;bn+1:=2b_{n}+\sigma(a_{n})$120

is com, $\sigma(a_{m-1})>$ .
It is an enumeration of finite sequences
puted primitive recursively in terms of the basic function $2x+y$ by substifor . We can thus express the sequence
for andtuting
with a function as follows.
$<\sigma(a_{1}),$$b_{n-1}$$\sigma(a_{n})$$x$$b_{n}$$\cdots$$\{b_{n}\}$$y$$\beta$$b_{1}=\beta(1, <>):=1$$b_{n+1}=\beta(n+1, <a_{1}, \cdots , a_{n}>)$ $:=2\beta(n, <a_{1}, \cdots , a_{n-1}>)+\sigma(a_{n})$$a_{n-1}>$ .
thus depends only on $<a_{1},$$c_{n}:=\phi(b_{n})$and $C:=\{n|c_{n}=1\}$ . Under the assumption
Next, define.
that $C$ be an infinite set, arrange its elements in the increasing order:This scheme can be a candidate for a selection rule as required in (2) whichis computed with information given
satisfies (A). For, it is obvious thatas $c_{n}=\psi(n, <a_{1}, \cdots, a_{n-1}>)$ .
, $a_{n-1}>$ . We can thus writeby $<a_{1},$.
is then determined as follows.
is recursive in$b_{n}$$\cdots,$$\{n_{j}\}_{j}$$c_{n}$$\cdots$$c_{n}$$\{a_{i}\}$$\psi$$\{n_{j}\}_{j}$$n_{1}:= \min(m;\psi(m, <a_{1}, \cdots, a_{m-1}>)=1)$$n_{j+1}:= \min(m;m\geq n_{j}+1\wedge\psi(m, <a_{1}, \cdots , a_{m-1}>)=1)$, as the infinity of the set is assumed.
as a function of is recursive inNow, asked if be chosen, one computes $\psi(i, <a_{1}, \cdots, a_{i-1}>)$ and see. That, can be adopted as the system
if the value be or 1. So,is, this selection scheme is in accord with Doob’s system. Let us say-random if it is random in this sense.
A recursive funtion produces values in a regular manner and hence one
can expect that it does not destroy randomness as it selects a subsequence.
Church then proves that there are many (in fact with power c) C-randomsequences.
Much later than these predecessors, Loveland in [3] came up with anotherview on the selection principle. He explains an example of a situation inwhich a selction rule not satisfying the property (A) can be realistic. That is,,selection of may depend on information with regards to somewhere the subscripts may be greater than .
He gives a method how to construct a selection rule which does not violate$j$$n_{j}$$C$$\{a_{i}\}$$a_{i}$$0$$\psi(i$$\{\tau_{i}\}$$)$-$\{a_{i}\}\mathrm{i}\mathrm{s}$$C$$a_{k_{1}},$$a_{i}$$\cdots,$$a_{k_{j}}$$i$

but does not obey (A).
the condition
In the next section, I will give a mathematical formulation to this idea.
$(^{*})$

121

1Church-LoVeland-randOmnesS, which is random in the sense of Church. Let be
Given a sequencea recursive -enumeration of positive integers. Its inverse, say is also. (It can easily be
will be a -enumeration ofrecursive.
. )seen that the condition (1) does not necessarily hold with
We will define a function to determine a system, which realizes a selection
principle, in a manner similar to above.
be a sequence of positive integers defined as follows.
Let
$\nu$

$\{a_{i}\}$

$\mu$

$re$

$\{a_{\nu()}\iota\}(=\{d_{l}\})$$\{a_{i}\}$$\mathrm{r}\mathrm{e}$$\{d_{l}\}$$\psi$$\{b_{n}’\}$$b_{1}’=\beta’(1, <>):=1$$b_{n+1}’=\beta’(n+1, <a_{\nu(1)},\cdots,a(n-1)>)\nu$$:=2\beta’(n, <a\nu(1),$ $\cdots,$ $a\nu(n-1\rangle>)+\sigma(a_{\nu}(n))$$C’$$:=$
be any recursive function. Then, define $c_{n}’:=\phi(b_{n}’)$ and$C’$ be an infinite set, arrange$\{n|c’n=1\}$ . Under the assumption thatcan be computed with in.
its elements in the increasing order:
as. We can thus write)
formation with regards toon, depending only
$c_{n}’=\psi’(n, <a_{\nu(1)}, \cdots , a_{\nu(l)}>)$ .
is recursive in$a\nu(l)>$ .
$<a_{y(1)},$. We would like to decide whether$q=q_{i}=\mu(i)$. That is,Putor not according to the scheme given by . That is, will be
to selectbe said to bechosen if and only if $c_{q}=1$ . The original sequence
L-C-random if it satisfies (1) and (2) with the selection rule as above.
The idea is simple and natural. As a very special case of , we can takethe identity function, and hence $C-L$ -random sequences are C-random.
Loveland presents a construction method such that it produces a sequenceis -random but not C-L-random. This guarantees the significanceof Loveland’s generalization of the notion of randomness. The construction
is an elaborate one relying on a diagonal method.
He also proves the existence of C-L-random sequences by the classicalmethods emplyoed by Doob and Church.

Let$\phi$$\{n_{j}\}$$a_{\nu}$$<a_{\nu(1),(\mathrm{t}}\ldots,$$c_{n}’$$c_{n}’$$c_{n}’$$>$$\{a_{l}\}$$\cdots,$$a_{i}=a_{\nu(q)}$$\psi’$$a_{i}$$a_{i}$$\{a_{i}\}\mathrm{w}\mathrm{i}\mathrm{l}1$$\psi’$$\nu$$\{a_{i}\}\mathrm{W}\mathrm{h}\mathrm{i}\mathrm{C}\mathrm{h}$$C$

Beyond Recursive Selection

2

As was mentioned above, recursive selection for the condition (2) (whether it
be -random or C-L-random) is a safe way of selection, due to its regularity.
$C$

122

I am not sure, however, if it is sufficient. It is a matter of how one views
betting decision.
Given information on $<a_{1},$ , $a_{i-1}>$ , how would one decides whetheror not to bet on ? In a way, this decision could be quite random (?!),
for one can make decision quite capriciously. One can even toss a coin! Inreality, one would like to win over a game, and hence would evaluate thepreceding results and decide on a pre-set rule of judgement. Such a rule isusually recursive, as one has to make decision in a finite time interval. If
one becomes desparate, however, one may toss a coin or rely on some omen.
The selection procedure as such still does not depend on the information ofitself
Since Doob does not specify the selection rule, all these are admissible.
Even then, mathematically, there are random sequences with power . It is
now at our liberty what kind of selection rules (called above) we admit.
can be expressed in terms of a scheme :$\cdots$$a_{i}$$a_{i}$$\mathrm{c}$$\mathrm{P}$$\delta$$\mathrm{P}$$c_{n}:=\delta(n, <\sigma(a1),$ $\sigma(a_{2}),$ $\cdots,$ $\sigma(a_{n-}1)>)$

A most regular would be recursive, and a most irregular one would becoin-tossing or something of the sort.
In reality, one would rely on some kind of decidable criteria. For example,
with 69 heads and 31 tails, one may feel that, since 69 is more than twice 31,
the next tossing result would be tail. Being betrayed at the next stage, theplayer may judge that, for awhile, the lady luck is on the side of head. So,
the player will bet on head.
Each of these judgements is decidable. The first one is to ask$(a)$ if $h_{n}>2t_{n}$ ,and the second one is to ask
if $h_{n}>2t_{n}$ and $\sigma(a_{n})=1$ .
stages.) There is, however, no pre(is the number of heads bydetermined rule what kind of judgement be adapted at each stage. The
be 1, and so the player bets on
player may suddenly getsa hunch that.
In order that , the selection principle, cover all these possibilities ofselection and yet be consistent in the sense that almost all sequences (frombe random with repsect to , a sensible condition be that be recursive
in a parameter. Such a parameter is usually called an orade. I thus propose
the following.
$\delta$$(b)$$n$$h_{n}$$a_{n+1}$$a_{n+1}$$\mathrm{P}$$\Omega^{\mathrm{N}})$$\mathrm{P}$$\mathrm{P}$123

Proposal The selction principle
are recursive in an oracle.
More explicitly, express$\mathrm{P}$$\mathrm{P}$be represented in terms offunctions which

as follows.

Definition 2.1 Let be a number-theoretic function with a function parameter . is said to be recursive in the oracle , if the follwoing it is definedby one of the following.
$f$$\alpha$$f$$\alpha$$f(x_{1}, \cdots , x_{n}):=c$($c$is a constant.

)$f(x_{1}, \cdots, x_{n}):=x_{i}(i=1, \cdots, n)$$f(x_{1}, \cdots, X_{n}):=\alpha(x1, \cdots, X_{n})$$f(x_{1}, \cdots, x_{n}):=h(g1(X_{1}, \cdots, xn), \cdots, g_{m}(X_{1}, \cdots, x_{n}))$$f(x):=x+1$$f(x, x_{1}, \cdots, x_{n}):=$else

if $x=0$

then
$g$

and

$h$

$h(x, x_{1}, \cdots , x_{n})$$g(f(x-1, X1, \cdots, Xn), X, X1, \cdots, x_{n})$$f(x_{1}, \cdots, x_{n}):=$

Herethen

$y$

else

if

$g(x_{1}, \cdots, x_{n}, y)=0$$f(x_{1}, \cdots , x_{n}, y+1)$

are supposed to be recursive in$\alpha$, and have already beendefined.
(See [4] for details.)
Obviously, a recursive function is obtained as a special case of the definitions above. For (a) above, one can set as follows.
$\alpha(n+1, <s_{1}, \ldots, s_{n}>)=1$

if and only if$h_{n}>2t_{n}$124;(1’s) amongis the number of, andisHere,thisisthatNoticesimilarly.
similarly with . For (b), can be determied
not determined uniformly in , but is for this particular $n+1$ . At anotherstage, say $m$ , one may prefer to tossing another coin for decision, and gets .
Then, $\alpha(m, <\cdots>)=0$ , a constant.
$s_{i}$$\sigma(a_{i})$$t_{n}$$h’ \mathrm{s}$$h_{n}$$a_{1},$$\cdot\cdot’,$$a_{n}$$\alpha$

$n$

$t$

The scheme as proposed above still fits in Doob’s concept of system.
Mathematical details are yet to be worked out.

References[1] J.L. Doob, Note on Probability, Annals of Mathematics, vol.37(1936),363-367[2] A. Church, On the concept of a random sequence, Bulletin of AMS,
vol.46(1940), 130-135[3] D. Loveland, A new interpretation of the von Mises’ conceptof random sequence, Zeitschrift f. math.Logik und Grundl. d.
Math., Bd. 12(1966).279-294[4] M. Davis, R. Sigal and E. Weyuker, Computability, Complexity, andLanguages, Academic Press, San Diego, 1994