Back to title page


3. Proofs of Lemmas 2, 3

 

LEMMA 5. Let L be an empty or finite set of natural numbers, set K(L) = the set of all tuples (i1, ..., is) such that (i1<i2<...<is) & (Ak<=s) ik in L (the empty tuple included). Then for an arbitrary sequence of reals {xn} we have

Sumi{ (xi1-1)...(xis-1) | i in K(L) }= Prodj{ xj | j in L },

where Sumi 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:

----> b0...----> b1...----> b2..----> b3.......................----> bm.....................................
|...............|...............|..............|...................................|..................................................
|...............|...............|..............|...................................|..................................................
-----------------------------------------------------------------------------> a .........(f)
S0............S1............S2............S3................................Sm................................................

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 taun declining from f. With each vertice of the tree we associate the probability that a function taun chosen according to the distribution pi meets this vertice. Let bm be the probability that taun meets the vertice Sm and immediately after that declines from f. Let

Bm = bm + bm+1 +...

Then the probability assigned to Sm will be a+Bm, where a is the probability assigned to the infinite path f (i.e. a = Sumn{pin |taun=f}).

By bij (i>=0, j>=i) we denote the probability that in the case of changing its mind at the vertice Si the istrategy BFtau,pi directs its new hypothesis through Sj aside from f. Clearly,

bij = bj/(a+Bi). ----------------(*)

iThe total probability of changing the mind at Sm, m>0, can be expressed by the numbers bij:

P{Am} = Sum{ b0,i1*bi1+1,i2*...*bik+1,m },

where Sum ranges over all tuples (i1, ..., ik) such that k>=0, 0<=i1< i2 < ... < ik < m.

The probability of simultaneous mindchanges at Sm1, ..., Smt (where m1 < m2 < ... < mt ) can be expressed similarly:

P{Am1 ^ .. .^ Amt} = Sum{ b0,i1*bi1+1,i2*...*bik+1,mt },

where Sum ranges over all tuples (i1, ..., ik) such that k>=0, 0<=i1< i2 < ... < ik < mt and {m1, ..., mt-1}is a subset of {i1, ..., ik}.

By (*), the probability P{Am1 ^ .. .^ Amt} depends only on a, b0, ..., bm and Bm+1, where m=mt =max mi. Let us introduce new variables gi, 0<=i<=m+1:

a+Bm+1 = agm+1,

a+Bm = agmgm+1, bm = a(gm-1)gm+1,

a+Bm-1 = agm-1gmgm+1, bm-1 = a(gm-1-1)gmgm+1,

a+Bj = agjgj+1 ... gm+1, bj = a(gj-1)gj+1 ... gm+1 (j=0,1,...,m).

Then we will have

bij = bj/(a+Bi) = (gj-1)/(gi ... gj),

b0,i1*bi1+1,i2*...*bik+1,m = (gi1-1)...(gik-1)(gm-1) / (g0 ... gm),

P{Am1 ^ .. .^ Amt} = (gm1-1)...(gmt-1) Sum{ (gi1-1)...(gik-1) }/ (g0 ... gm),

where L = {0, 1, ..., m}-{m1, ..., mt}, and Sum ranges over all tuples (i1, ..., ik) in K(L), where K(L) is defined in Lemma 5. By Lemma 5, the latter Sum is equal to Prod{ gi | i in L }, hence,

P{Am1 ^ .. .^ Amt} = (gm1-1)...(gmt-1) Prod{ gi | i in L } / (g0 ... gm) = (gm1-1)/gm1 * ... *(gmt-1)/gmt.

For t=1 we would have:

P{Am} = Pm(BFtau,pi, f) = (gm-1)/gm = bm/(a+Bm).

Hence,

P{Am1 ^ .. .^ Amt} = P{Am1}* ... *P{Amt}, i.e. the events Ai are independent. This proves Lemma 3.

PROOF OF LEMMA 2. As we already know,

Pm(BFtau,pi, f) = bm/(a+Bm) = 1 - (a+Bm+1)/(a+Bm).

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

Summ{ bm/(a+Bm) }<= ln Prodm{ a+Bm+1)/(a+Bm) }.

Since

Prodm<=s{ a+Bm+1)/(a+Bm) } = (a+B0)/(a+Bs+1) -> (a+B0)/a, as s->oo,

we obtain that

Pm(BFtau,pi, f) <= ln((a+B0)/a).

If f=taun, then a>=pin. Clearly, a+B0<=1, hence,

ln((a+B0)/a) <= ln (1/pin).

Q.E.D.

To complete the proof of Theorem 1 we show now, for a computable numbering tau and computable probability distribution pi (pi1+pi2+pi3+...=1), how the recursive counterpart BF'tau,pi of the strategy BFtau,pi can be constructed. We will use also a omputable sequence of rationals {em} such that Prodm(1+em) < oo (for example, em=2-m).

Let us modify the definition of the hypothesis BFtau,pi(f[m]) (see Section 2) as follows. If the numbering tau is computable, the set Em is recursive, hence, we can compute a binary-rational probability distribution (lambdan1, lambdan2, ..., lambdank) which em-approximates the distribution {pin/s | n in Em}, s = Sumn{pin | n in Em}, i.e. lambdan1+ lambdan2+...+ lambdank = 1, and for all i:

ni in Em & lambdani <= (1+em) pini / s

Now define BF'tau,pi(f[m]) = ni with probability lambdani 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, taun, >=k} <= P{BFtau,pi, taun, >=k}* Prodm(1+em).

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

b'ij <= (1+ei) bij. -------------(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 (i1, ..., ik) such that k>=0, 0<= i1 < i2 < ... < ik. Hence, by (1),

P{BF'tau,pi, f, >=k} <= Prodm(1+em) * Sum{ b'0,i1*b'i1+1,i2* ... *b'ik-1+1,ik }
<= P{BFtau,pi, f, >=k}* Prodm(1+em).

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

 

4. Proof of Lemma 4

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=g0g1...ga - a binary string. We will construct n functions s1, s2, ..., sn starting with the values from gamma, such that if M identifies with probability 1 s-indices of all functions si, then by one of these functions M will change its mind >=k times with probability

>= (1-e) P{ Z2+...+Zn >=k},

where Zi 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 PM. We initiate parallel computing of probabilities of the following events:

M(b0)=t0 & M(b0b1)=t1 & ... & M(b0...bm)=tm -----------------(1)

for all binary strings beta=b0b1...bm and all finite sequences t=t0t1..tm 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 PM.

Simultaneously with PM, we add new values to functions s1, s2, s3, s4:

si(0)=g0, si(1)=g1, ..., si(a)=ga, si(a+1)=0, si(a+2)=0,...

(where gamma=g0g1...ga). Only at some particular moments we will interfere this process, and add a finite number of 1's as values of si.

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

| 1.......2.......3........4 | ....................(2)
|q1.......q2.......q3........q4 |..........................

where q1+q2+q3+q4 =1 and for all i:

qi <= P{M(gamma + 0j1) = 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+0j) 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 + 0oo 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 s1, s2, s3, s4, and hence, they will be all equal to gamma + 0oo. 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 s1, instead of the current value s1(x1)=0, obtains the value s1(x1)=1, and for all x>x1 s1 is set equal to 0. The remaining three functions s2, s3, s4 obtain for x=x1 the value 0 (i.e. other than s1(x1)), and then (after our "interference" is concluded) they continue to obtain zero values. I.e., after this moment, s1 differs from s2, s3, s4, 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 q1>0.

The definition process of s2, s3, s4 will be interfered for the second time, when the probabilities of (1) will be computed precisely enough to obtain for some j2 > j1 the numbers q1i:

| 2........3........4 | .....................(3)
|q12.....q13.....q14 |..........................

such that q12+q13+q14=1 and for all i:

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

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

P{ M(gamma + 0j) not in {2,3,4} | M(gamma + 0j1) = 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 s2, s3, s4 will be set equal to gamma + 0oo. 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 si (for example, let it be s2). We set s2(x2)=1, s3(x2)=s4(x2)=0, and for all x>x2: s2(x)=0 (here, of course, x2>x1, where x1 is the location of our first interference).

The third interference (and the last one - when n=4) in the definition process of functions s3, s4 will take place, when the probabilities of (1) will be computed precisely enough to obtain a number j3 > j2 and numbers q12i, q22i:

| 3.......... 4 |.....| 3...........4 |......................(4)
| q123...q124 |.....| q223...q224 |..........................

such that q123+q124=1, q223+q224=1, and for i=3, 4:

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

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

In the case, when the numbers j3, q12i, q22i cannot be obtained, Lemma 4 holds obviously.

If the numbers (4) have been obtained, the algorithm of Section 5 "removes" another function si (for example, let it be s3). We set s3(x3)=1 (where, of course, x3>x2), s4(x3)=0, and for all x>x3: s4(x)=0. Since n=4, now only one function s4 remains, let s4(x)=0 for all x>x3.

Hereby we conclude the definition of functions s1, ..., sn, 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 si the strategy M will change its mind >=k times with a sufficiently large probability.


Back to title page