Back to title page

**LEMMA 5**. Let L be an empty or finite set of
natural numbers, set K(L) = the set of all tuples (i_{1},
..., i_{s}) such that (i_{1}<i_{2}<...<i_{s})
& (Ak<=s) i_{k} in L (the empty tuple included).
Then for an arbitrary sequence of reals {x_{n}} we have

Sum_{i}{ (x_{i1}-1)...(x_{is}-1)
| i in K(L) }= Prod_{j}{ x_{j }| j in L },

where Sum_{i} ranges over all tuples i in K(L).

PROOF. Immediately, by induction.

PROOF OF LEMMA 3. Let us consider the tree of functions of the numbering tau which coincide up to some moment with the function f:

----> b_{0}...----> b_{1}...---->
b_{2}..----> b_{3}.......................---->
b_{m}.....................................

|...............|...............|..............|...................................|..................................................

|...............|...............|..............|...................................|..................................................

----------------------------------------------------------------------------->
a .........(f)

S_{0}............S_{1}............S_{2}............S_{3}................................S_{m}................................................

The infinite path drawn here corresponds to the function f
(which may have more than one tau-index, by the way). The
outgoing arrows correspond to functions tau_{n} declining
from f. With each vertice of the tree we associate the
probability that a function tau_{n} chosen according to
the distribution pi meets this vertice. Let b_{m} be the
probability that tau_{n} meets the vertice S_{m}
and immediately after that declines from f. Let

B_{m} = b_{m} + b_{m+1}
+...

Then the probability assigned to S_{m} will be a+B_{m},
where a is the probability assigned to the infinite path f (i.e.
a = Sum_{n}{pi_{n} |tau_{n}=f}).

By b_{ij} (i>=0, j>=i) we denote the probability
that in the case of changing its mind at the vertice S_{i}
the istrategy BF_{tau,pi} directs its new hypothesis
through S_{j} aside from f. Clearly,

b_{ij} = b_{j}/(a+B_{i}).
----------------(*)

iThe total probability of changing the mind at S_{m},
m>0, can be expressed by the numbers b_{ij}:

P{A_{m}} = Sum{ b_{0,i1}*b_{i1+1,i2}*...*b_{ik+1,m}
},

where Sum ranges over all tuples (i_{1}, ..., i_{k})
such that k>=0, 0<=i_{1}< i_{2} < ...
< i_{k} < m.

The probability of simultaneous mindchanges at S_{m1},
..., S_{mt} (where m_{1} < m_{2} <
... < m_{t} ) can be expressed similarly:

P{A_{m1} ^ .. .^ A_{mt}} = Sum{
b_{0,i1}*b_{i1+1,i2}*...*b_{ik+1,mt} },

where Sum ranges over all tuples (i_{1}, ..., i_{k})
such that k>=0, 0<=i_{1}< i_{2} < ...
< i_{k} < m_{t} and {m_{1}, ..., m_{t-1}}is
a subset of {i_{1}, ..., i_{k}}.

By (*), the probability P{A_{m1} ^ .. .^ A_{mt}}
depends only on a, b_{0}, ..., b_{m} and B_{m+1},
where m=m_{t} =max m_{i}. Let us introduce new
variables g_{i}, 0<=i<=m+1:

a+B_{m+1} = ag_{m+1},

a+B_{m} = ag_{m}g_{m+1}, b_{m}
= a(g_{m}-1)g_{m+1,}

a+B_{m-1} = ag_{m-1}g_{m}g_{m+1},
b_{m-1} = a(g_{m-1}-1)g_{m}g_{m+1},

a+B_{j} = ag_{j}g_{j+1} ... g_{m+1,
}b_{j} = a(g_{j}-1)g_{j+1} ... g_{m+1}
(j=0,1,...,m).

Then we will have

b_{ij} = b_{j}/(a+B_{i})
= (g_{j}-1)/(g_{i} ... g_{j}),

b_{0,i1}*b_{i1+1,i2}*...*b_{ik+1,m}
= (g_{i1}-1)...(g_{ik}-1)(g_{m}-1) / (g_{0}
... g_{m}),

P{A_{m1} ^ .. .^ A_{mt}} = (g_{m1}-1)...(g_{mt}-1)
Sum{ (g_{i1}-1)...(g_{ik}-1) }/ (g_{0}
... g_{m}),

where L = {0, 1, ..., m}-{m_{1}, ..., m_{t}},
and Sum ranges over all tuples (i_{1}, ..., i_{k})
in K(L), where K(L) is defined in Lemma 5. By Lemma 5, the latter
Sum is equal to Prod{ g_{i} | i in L }, hence,

P{A_{m1} ^ .. .^ A_{mt}} = (g_{m1}-1)...(g_{mt}-1)
Prod{ g_{i} | i in L } / (g_{0} ... g_{m})
= (g_{m1}-1)/g_{m1} * ... *(g_{mt}-1)/g_{mt}.

For t=1 we would have:

P{A_{m}} = P_{m}(BF_{tau,pi},
f) = (g_{m}-1)/g_{m} = b_{m}/(a+B_{m}).

Hence,

P{A_{m1} ^ .. .^ A_{mt}} = P{A_{m1}}*
... *P{A_{mt}}, i.e. the events A_{i} are
independent. This proves Lemma 3.

PROOF OF LEMMA 2. As we already know,

P_{m}(BF_{tau,pi}, f) = b_{m}/(a+B_{m})
= 1 - (a+B_{m+1})/(a+B_{m}).

Summing up for all m, and using the inequality 1-x <= ln(1/x) we obtain that

Sum_{m}{ b_{m}/(a+B_{m})
}<= ln Prod_{m}{ a+B_{m+1})/(a+B_{m})
}.

Since

Prod_{m<=s}{ a+B_{m+1})/(a+B_{m})
} = (a+B_{0})/(a+B_{s+1}) -> (a+B_{0})/a,
as s->oo,

we obtain that

P_{m}(BF_{tau,pi}, f) <=
ln((a+B_{0})/a).

If f=tau_{n}, then a>=pi_{n}. Clearly, a+B_{0}<=1,
hence,

ln((a+B_{0})/a) <= ln (1/pi_{n}).

Q.E.D.

To complete the proof of Theorem 1 we show now, for a
computable numbering tau and computable probability distribution
pi (pi_{1}+pi_{2}+pi_{3}+...=1), how the
recursive counterpart BF'_{tau,pi} of the strategy BF_{tau,pi}
can be constructed. We will use also a omputable sequence of
rationals {e_{m}} such that Prod_{m}(1+e_{m})
< oo (for example, e_{m}=2^{-m}).

Let us modify the definition of the hypothesis BF_{tau,pi}(f^{[m]})
(see Section 2) as follows. If the
numbering tau is computable, the set E_{m} is recursive,
hence, we can compute a binary-rational probability distribution
(lambda_{n1}, lambda_{n2}, ..., lambda_{nk})
which e_{m}-approximates the distribution {pi_{n}/s
| n in E_{m}}, s = Sum_{n}{pi_{n} | n in
E_{m}}, i.e. lambda_{n1}+ lambda_{n2}+...+
lambda_{nk }= 1, and for all i:

n_{i} in E_{m} & lambda_{ni}
<= (1+e_{m}) pi_{ni }/ s

Now define BF'_{tau,pi}(f^{[m]}) = n_{i}
with probability lambda_{ni} for all i = 1, ..., k.

**LEMMA 6**. Let BF'_{tau,pi} be the
modified computable probabilistic strategy. Then for all n and k,

P{BF'_{tau,pi}, tau_{n},
>=k} <= P{BF_{tau,pi}, tau_{n}, >=k}*
Prod_{m}(1+e_{m}).

PROOF. Let us return to the proof of Lemma 3. For the
probabilities b'_{ij }of BF'_{tau,pi}
(corresponding to b_{ij} of BF_{tau,pi} in Section 2) we have:

b'_{ij} <= (1+e_{i}) b_{ij}.
-------------(1)

The probability P{BF'_{tau,pi}, f, >=k} can be
expressed by b'_{ij}:

P{BF'_{tau,pi}, f, >=k} = Sum{ b'_{0,i1}*b'_{i1+1,i2}*
... *b'_{ik-1+1,ik} },

where Sum ranges over all tuples (i_{1}, ..., i_{k})
such that k>=0, 0<= i_{1} < i_{2} <
... < i_{k}. Hence, by (1),

P{BF'_{tau,pi}, f, >=k} <= Prod_{m}(1+e_{m})
* Sum{ b'_{0,i1}*b'_{i1+1,i2}* ... *b'_{ik-1+1,ik}
}

<= P{BF_{tau,pi}, f, >=k}* Prod_{m}(1+e_{m}).

By Lemma 6, since the inequality of Theorem 1 holds for the
strategy BF_{tau,pi}, it holds also for BF'_{tau.pi}.

Let us carry out the (more complicated) "computable
case" of the proof. Let M be a computable probabilistic
strategy, n, k - natural numbers, k<n, e>0 - a rational
number, gamma=g_{0}g_{1}...g_{a} - a
binary string. We will construct n functions s_{1}, s_{2},
..., s_{n} starting with the values from gamma, such that
if M identifies with probability 1 s-indices of all functions s_{i},
then by one of these functions M will change its mind >=k
times with probability

>= (1-e) P{ Z_{2}+...+Z_{n}
>=k},

where Z_{i} are random variables defined in Section2.

Let us consider the idea of the proof for the case n=4, k=2. The generalization is straightforward.

**Procedure P**_{M}. We
initiate parallel computing of probabilities of the following
events:

M(b_{0})=t_{0} & M(b_{0}b_{1})=t_{1}
& ... & M(b_{0}...b_{m})=t_{m}
-----------------(1)

for all binary strings beta=b_{0}b_{1}...b_{m}
and all finite sequences t=t_{0}t_{1}..t_{m}
of natural numbers. This can be done as follows. For all pairs
(alpha, beta) of binary strings alpaha, beta the following
parallel -computation process is carried out: alpha serves as a
finite realization of Bernoulli generator's output (i.e. a finite
sequence of 0's and 1's), and beta - as initial segment f(0),
..., f(m) of some function f taking values 0,1. Initially, we
associate with each pair (beta, t) an empty set of binary strings
alpha. When, during the computation process with alpha and beta
we see the sequence s printed on the output tape of M, then we
add alpha to the set associated with (beta, t). If it appears
that alpha is too short for some computation, we simply drop this
computation. And so on.

**End of procedure P**_{M}**.
**

Simultaneously with P_{M}, we add new values to
functions s_{1}, s_{2}, s_{3}, s_{4}:

s_{i}(0)=g_{0}, s_{i}(1)=g_{1},
..., s_{i}(a)=g_{a}, s_{i}(a+1)=0, s_{i}(a+2)=0,...

(where gamma=g_{0}g_{1}...g_{a}). Only
at some particular moments we will interfere this process, and
add a finite number of 1's as values of s_{i}.

The first of these moments will appear, when the probabilities
of (1) will be computed precisely enough to obtain for some
number j_{1} the following approximate probability
distribution of the hypothesis M(gamma + 0^{j1} ):

| 1.......2.......3........4 |
....................(2)

|q_{1.......}q_{2.......}q_{3........}q_{4}
|..........................

where q_{1}+q_{2}+q_{3}+q_{4}
=1 and for all i:

q_{i} <= P{M(gamma + 0^{j1})
= i}/(1-delta),

where delta>0 is a constant such that (1-delta)^{3}>=1-e
(here we have n-1=3, see Section 5).

If such a moment does not appear, it would mean, that for each
j in N the hypothesis M(gamma+0^{j}) is undefined or not
in {1, 2, 3, 4} with probability greater than delta. Then, with
probability >delta, this is the case for infinitely many j's
simultaneously, i.e. by the function gamma + 0^{oo} the
strategy M outputs infinitely many hypotheses other than 1, 2, 3,
4. But this is exactly the case, when we do not interfere the
definition process of the functions s_{1}, s_{2},
s_{3}, s_{4}, and hence, they will be all equal
to gamma + 0^{oo}. For this case, Lemma 4 holds
obviously.

Now let us consider the case, when the probability distribution (2) can be obtained. Using (2) and the algorithm described in Section 5, we exclude one of the numbers 1, 2, 3, 4 in the following sense (for example, let it be the number 1):

The function s_{1}, instead of the current value s_{1}(x_{1})=0,
obtains the value s_{1}(x_{1})=1, and for all
x>x_{1} s_{1} is set equal to 0. The remaining
three functions s_{2}, s_{3}, s_{4}
obtain for x=x_{1} the value 0 (i.e. other than s_{1}(x_{1})),
and then (after our "interference" is concluded) they
continue to obtain zero values. I.e., after this moment, s_{1}
differs from s_{2}, s_{3}, s_{4}, and by
these last 3 functions the hypothesis 1 will be wrong. Our
algorithm (see Section 5) guarantees
that 1 will be removed only if q_{1}>0.

The definition process of s_{2}, s_{3}, s_{4}
will be interfered for the second time, when the probabilities of
(1) will be computed precisely enough to obtain for some j_{2}
> j_{1} the numbers q_{1i}:

| 2........3........4 |
.....................(3)

|q_{12.....}q_{13.....}q_{14}
|..........................

such that q_{12}+q_{13}+q_{14}=1
and for all i:

q_{1i} <= P{ M(gamma + 0^{j1})=1
& M(gamma + 0^{j2}) =2 }/ (1-delta)^{2}.

If such a moment would not appear, it would mean, that for
some delta'>0 and all j > j_{1}:

P{ M(gamma + 0^{j}) not in {2,3,4} |
M(gamma + 0^{j1}) = 1 } > delta'.

Hence, with probability >delta' this is the case for
infinitely many j's simultaneously. Since our second interference
does not take place in this case, the functions s_{2}, s_{3},
s_{4} will be set equal to gamma + 0^{oo}. Lemma
4 holds in this case obviously.

Let us consider the case, when the distribution (3) can be
obtained. Then, by the algorithm of Section
5, we exclude another function s_{i} (for example,
let it be s_{2}). We set s_{2}(x_{2})=1,
s_{3}(x_{2})=s_{4}(x_{2})=0, and
for all x>x_{2}: s_{2}(x)=0 (here, of course,
x_{2}>x_{1}, where x_{1} is the
location of our first interference).

The third interference (and the last one - when n=4) in the
definition process of functions s_{3}, s_{4} will
take place, when the probabilities of (1) will be computed
precisely enough to obtain a number j_{3} > j_{2}
and numbers q_{12i}, q_{22i}:

| 3.......... 4 |.....| 3...........4
|......................(4)

| q_{123...}q_{124} |.....|_{ }q_{223...}q_{224}
|..........................

such that q_{123}+q_{124}=1, q_{223}+q_{224}=1,
and for i=3, 4:

q_{12i} <= P{ M(gamma + 0^{j1})=1
& M(gamma + 0^{j2}) =2 & M(gamma + 0^{j3})
=i }/ (1-delta)^{3}.

q_{22i} <= P{ M(gamma + 0^{j1})=2
& M(gamma + 0^{j2})=i }/ (1-delta)^{3}.

In the case, when the numbers j_{3}, q_{12i},
q_{22i} cannot be obtained, Lemma 4 holds obviously.

If the numbers (4) have been obtained, the algorithm of Section 5 "removes" another
function s_{i} (for example, let it be s_{3}). We
set s_{3}(x_{3})=1 (where, of course, x_{3}>x_{2}),
s_{4}(x_{3})=0, and for all x>x_{3}: s_{4}(x)=0.
Since n=4, now only one function s_{4} remains, let s_{4}(x)=0
for all x>x_{3}.

Hereby we conclude the definition of functions s_{1},
..., s_{n}, corresponding by Lemma 4 to the probabilistic
strategy M, natural numbers k, n (k<n) and rational number
e>0. The algorithm, described in Section
5, will guarantee that by one of the functions s_{i}
the strategy M will change its mind >=k times with a
sufficiently large probability.

Back to title page