Back to title page
We consider the case n=4, k=2. The generalization is straightforward.
If the strategy M identifies with probability 1 s-indices of all functions s1, s2, s3, s4, then during the construction process of these functions all the three possible interferences must have been performed. For example, in the following sequence 123(4):
| j1 | 1 | 2 | 3 | 4 |
| j2 | 2 | 3 | 4 | 2 | 3 | 4 |
| j3 | 3 | 4 | 3 | 4 | 3 | 4 | 3 | 4 |
| j4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 |
Segments split the first row according to the probability distribution (q1, q2, q3, q4) of Section 4. The first 3 segments of the second row split q1 according to the distribution (q12, q13, q14). The segments of the third row split q12 to (q123, q1124 ), and q22 - to (q223, q224). In the last row we have (with probability 1) the hypothesis 4 - the only "right" s-index of s4.
Let us introduce a more convenient notation:
|1|=q1, |2|=|22|=q12,
|12|=q12, |133|=q13,
|123|=q123, |224|=q224,...
Let us assume (for a moment) that these numbers coincide exactly with the probabilistic characteristics of the strategy M (see Section 4), for example:
|123| = P{M(gamma + 0j1)=1 & M(gamma + 0j2)=2 & M(gamma + 0j3)=3},
|223| = P{M(gamma + 0j1)=2 & M(gamma + 0j3)=3}.
Then, the probability that by the function s4 the strategy M will change its mind at least two times (k=2), is
>= |123|+|124|+|133|+|223| = |12|+|13|+|223|. -----------------(a)
When during the last interference the function s4 would have been excluded (instead of s3), then instead of (a) we would have had the sum
|12|+|14|+|224|. --------------(aa)
Hence, when the functions s1, s2 have been already excluded, it would be sensible to exclude next s3 or s4 depending on the maximum - (a) or (aa). And this can be really decided - all the items of (a) and (aa) are known at the level j3.
Now let us consider the level j2. The function s1 is already excluded. We know the probabilities |1|, |2|, |3|, |4|, |12|, |13|, |14|. What of the functions should be excluded next - s2, s3 or s4? The decision "exclude s2" can be estimated by means of the sum (a)+(aa), i.e.,
|12|+|13|+|223|+|12|+|14|+|224| = |1|+|22|+|12| = |1|+|2|+|12|. -----------(b)
Hence, this sum depends only on the probabilities known at the level j2. The corresponding sums for s3 and s4 are
|1|+|3|+|13|, ------------(bb)
|1|+|4|+|14|. ------------(bbb)
Hence, the maximum of (b), (bb) and (bbb) should decide, which of the functions s2, s3, s4 should be excluded next, after s1. And this can be really decided at the level j2.
Finally, let us consider the level j1. The decision "exclude s1" can be estimated by means of the sum (b)+(bb)+(bbb):
3*|1|+|2|+|3|+|4|+|12|+|13|+|14| = 1+3*|1|.
The analogous estimates for s2, s3, s4 are
1+3*|2|, 1+3*|3|, 1+3*|4|.
All these estimates can be computed at the level j. Hence, at this level we should exclude the function si having the maximum 1+3*|i|.
Hereby, for n=4, k=2 the definition of our exclusion algorithm is concluded. The generalization is straightforward.
In Section 6 we will prove generally, that all the summing-up operations used in the algorithm are leading to the level, at which the required decision should be performed.
Now let us obtain some estimate of the probability that the strategy M will change its mind >=2 times by the function s4.
At the level j1 we had 4 estimates:
1+3*|1|, 1+3*|2|, 1+3*|3|, 1+3*|4|.
The sum of them is 4+3*1=7, i.e. it depends only on n and k. If, according to our algorithm, we exclude s1, then:
1+3*|1| >= 7 / 4.
If, after this, s2 is excluded, then:
|1|+|2|+|12| >= 7 / (4*3).
Finally, the exclusion of s3 means that
|12|+|23|+|223| >= 7 / (4*3*2), --------------(1)
i.e. the probability of M changing its mind >=2 times is >= 7 / (4*3*2).
However, this conclusion would be absolutely valid only if the characteristic probabilities of M would be exactly |1|, |12|, |223| etc. This is not the case, but one can select the number delta of Section 4 so that instead of the estimate >= 7 / (4*3*2) we obtain >= (1-e)* 7 / (4*3*2), where e is the third parameter of Lemma 4. Really,
P{M, s4, >=2}>= P{M(gamma + 0j1)=1 & M(gamma + 0j2)=2} +
+ P{M(gamma + 0j1)=1 & M(gamma + 0j2)=3}+
+ P{M(gamma + 0j1)=2 & M(gamma + 0j3)=3}>=
>= (1-delta)2q12 + (1-delta)2q13 + (1-delta)3q223 >=
>= (1-delta)3 (|12|+|13|+|223|) >= (1-delta)3 * 7 / (4*3*2).
When delta is selected so that (1-delta)3 >= 1-e, then
P{M, s4, >=2} >= (1-e)*7/(4*3*2).
To conclude the proof of Lemma 4 (for n=4 and k=2), it remains to verify that
7/(4*3*2) = P{ Z2+Z3+Z4 >= 2 }, ----------------(2)
where Zi are independent random variables such that
P{Zi=1} = 1/i, P{Zi=0}=1-1/i.
Of course, one could verify (2) directly:
(1/2)*(1/3)*(1-1/4) + (1/2)*(1-1/3)*(1/4) + (1-1/2)*(1/3)*(1/4) + (1/2)*(1/3)*(1/4) = 7/(4*3*2).
To obtain a general method (for arbitrary n,k, k<n), we can use constructions from the proof of Lemma 3 (see Section 4).
First let us note that the lower bound 7/(4*3*2) of (1) is reached if and only if the table at the beginning of this section is "symmetric": the first row is splitted in ratio 1:4, the second one - in 1:3, the third one - in 1:2. Such a table is simulating the work of the strategy BFtau,pi by the function s4 = 0oo, where
tau = (s1, s2, s3, s4),
s1 = 010oo, s2 = 0010oo, s3 = 00010oo, s4 = 0oo,
pi = {1/4, 1/4, 1/4, 1/4}.
Indeed, the hypothesis BFtau,pi(<0>) = 1, 2, 3 or 4 with equal probabilities 1/4. Further, if BFtau,pi(<0>) = 1, then BFtau,pi(<0,0>) = 2, 3 or 4 with probabilities 1/3. If BFtau,pi(<0>)=1 & BFtau,pi(<0,0>)=2, then BFtau,pi(<0,0,0>) = 3 or 4 with probabilities 1/2. If BFtau,pi(<0>) = 2, then BFtau,pi(<0,0>) = 2 with probability 1, and BFtau,pi(<0,0,0>) = 3 or 4 with probabilities 1/2. Finally, the hypothesis BFtau,pi(<0,0,0,0>)=4 with probability 1.
By using the function tree from the proof of Lemma 3:
----> 010oo......----> 0010oo....---->
00010oo................................................................
|..b0..................|..b1...................|..b2................................................................................
|........................|........................|......................................................................................
---------------------------------------------------------------------------->
a .........(0oo)
S0.....................S1.....................S2.....................................................................................
where b0 = b1 = b2 = a = 1/4, we obtain:
P{BFtau,pi(<0>)<>BFtau,pi(<0,0>)} = b0 / (b0+b1+b2+a) = 1/4.
P{BFtau,pi(<0,0>)<>BFtau,pi(<0,0,0>)} = b1 / (b1+b2+a) = 1/3.
P{BFtau,pi(<0,0,0>)<>BFtau,pi(<0,0,0,0>) = b2 / (b2+a) = 1/2.
By Lemma 3, the following Xi (i=0, 1, 2) are independent random variables:
Xi = 1, if BFtau,pi(<0i>) <> BFtau,pi(<0i+1>),
Xi = 0, otherwise.
Hence, the triple (X0, X1, X2) coincides with the triple (Z4, Z3, Z2). Since the sum X0+X1+X2 = Z4+Z3+Z2 represents the number of mindchanges of M by the function 0oo, we obtain that
7/(4*3*2) = P{ Z2+Z3+Z4 >= 2 }.
Obviously, this way (2) can be proved for arbitrary n,k (k<n).
The general setting is as follows. Let n be a natural number. Some probability distribution over the set {1,2,...,n} is labeled by the empty tuple o:
|1|o, |2|lo, ..., |n|o.
When now some number i in {1,2,...,n} is "excluded", the probability |i|o is splitted in the following way:
|i|o = Sumy{ |iy|i | y<>i |,
where the new distribution is labeled by the tuple (i). The probabilities |x|o for x<>i are retained:
|x|o = |xx|i.
Let us call the 2-tuples, obtained in these two ways (i.e. (iy) for y<>i, and (xx) for x<>i) (i)-admissible.
In the next step another number j in {1,2,...,n}-{i} is "excluded", and the probabilities |ij|i, |jj|i are splitted in the following way (x=i or x=j):
|xj|i = Sumy{|xjy|ij | y<>i, j }
All the other probabilities are retained:
|xy|i = |xyy|ij.
Let us call the obtained 3-tuples (ij)-admissible.
In the general case, after the numbers p1, ..., pa of the a-tuple p = (p1 ... pa) have been "excluded", and the notion of p-admissible (a+1)-tuples has been defined (and to every p-admissible x corresponds the probability |xj|p), the next number q in {1,2,...,n}- p is "excluded". The p -probabilities |zq|p are splitted:
|zq|p = Sumy{|zqy|pq | y not in p and y<>j}|. ---------------(a)
The other probabilities are retained:
|zy|p = |zyy|pq,
where y<>q (and, of course, y not in p, since zy is p-admissible). The left hand side tuples of (a) and (b) are called pq-admissible.
Obviously, the tuple (x1...xa+1) is p-admissible (where p=(p1...pa)), if and only if for all i<=a:
(1) xi+1 not in {p1, ..., pi},
(2) xi not in {p1, ..., pi) implies xi+1 = xi.
At the very end of the exclusion process we will have some permutation (p1...pn) of the set {1, 2, ..., n}. Let us denote p = (p1...pn-1). To every p-admissible n-tuple x a probability |x|p- is assigned. According to our problem, special attention is paid to n-tuples x = (x1...xn) having the property: xi <> xi+1 for at least k values of i (k is a natural number, k<n). Let us denote by Sk the set of all such x's. We will use only the symmetricity of Sk, i.e. if pi is any permutation of the numbers {1, 2, ..., n}, then
(x1...xn) in Sk <--> (pi(x1)...pi(xn)) in Sk.
The "quality" of every permutation (p1...pn) of the set {1, 2, ..., n} is defined by the probability
T(p) = Sumx{ |x|p },
where x ranges over all p-admissible n-tuples of Sk (recall that p = (p1...pn-1)).
We extend this "quality" definition to any tuple q = (q1...qa) containing no repetitions (a<=n-1).
If a<=n-2 and q contains all the numbers of the set {1, 2, ..., n} except qa+1, ..., qn, then we define by recursion:
T(q) = T(qqa+1)+T(qqa+2)+...+T(qqn).
In particular, for the empty tuple o:
T(o) = T(1) + T(2) + ... + T(n).
We will prove that for all q and all q not in q the value of T(qq) can be computed having the probabilities |x|q for all q-admissible (a+1)-tuples x. This will be proved by showing that T(qq) can be represented as
T(qq) = Sumx{ c(x)|x|q },
where x ranges over all q-admissible tuples, and c(x)'s are natural numbers that can be computed having x, q and q.
First we consider the case q = (q1, ..., qn-2). Let us denote by q, t the only two numbers (1<=q<t<=n), which do not belong to the tuple q. Then, for any qq-admissible tuple x = (x1, ..., xn) we have xn = t, and |x|qq = |x1...xn-1|q, hence,
T(qq) = Sumy{ c(y)|y|q },
where y ranges over all q-admissible (n-1)-tuples, and
c(y) = 1, if yt in Sk,
c(y) = 0, otherwise.
Now let us consider the next case q = (q1, ..., qn-3). By q, s, t we denote the 3 numbers which do not belong to q. Then, by definition:
T(qq) = T(qqs) + T(qqt).
As we already know,
T(qqs) = Sumx{ |x|qq },----------------- (1)
where x ranges over qq-admissible (n-1)-tuples such that xt in Sk. The set Sk is symmetric, therefore, replacing s by t in (1), we will obtain T(qqt).
The sum expression T(qqs)+T(qqt) can be simplified considering the following cases, where x is an arbitrary tuple of the expression (1):
1) x = ys, where y does not contain s, t. Then, replacing s by t, we obtain yt, and
|ys|qq + |yt|qq = |y|q.
2) x = yt, similarly.
3) x = yss...s, where y does not contain s, t. Then, replacing s by t, we obtain ytt...t, and
|yss...s|qq = |yss...|q,
|ytt...t|qq = |ytt...|q.
4) x=ytt...t, similarly.
Hence, we obtain the following representation of T(qq):
T(qq)= Sumx{ c(x)|x|q },-------------------- (2)
where x ranges oven all q-admissible (n-2)-tuples, and the numbers c(x) can be computed from x, q, q. The representation (2) is symmetric to s, t: if x contains s (then x does not contain t), then replacing (in x) s by t, we obtain y such that c(y)=c(x).
Now we can perform the induction step for the general case. Let q = (q1...qa) be a tuple without repetitions, and the numbers q, r2, ..., rn-a do not belong to q. Let us suppose that
T(qqr2) = Sumx{ c(x)|x|qq }, --------------(3)
where x ranges over all qq-admissible tuples, and the following symmetricity condition holds: if x is qq-admissible, and s = (s3, ..., sn-a) is any permutation of the numbers (r3, ..., rn-a ), then the action of s on x yields a tuple y such that c(y)=c(x).
By definition:
T(qq) = T(qqr2)+T(qqr3)+...+T(qqrn-a).---------------- (4)
To obtain from (3) a representation of T(qqri) (where i>=3), one can apply to all qq-admissible (a+2)-tuples x the permutation of the set {1, 2, ..., n} transposing r2 and ri. Thus, the expression (4) can be simplified by considering the following cases:
1) x = yr2, where y does not contain r2. Applying the permutations mentioned above we obtain the tuples yr3, ..., yrn-a, and
|yr2|qq + |yr3|qq + ... + |yrn-a|qq = |y|q.
2) x = yri, where i>=3 and y does not contain ri. Then, (3) contains all the tuples of this kind: yr3, ..., yrn-a, and with the same coefficient c(x). Applying the permutations of the set {1, 2, ..., n} mentioned above we obtain from yri: a) the tuple yr2, b) n-a-3 copies of yri itself. All this will be included into (4):
(n-a-2)(|yr2|qq + ... + |yrn-a|qq) = (n-a-2)|y|q.
3) x = yr2...r2, where y does not contain r2. The permutations mentioned above yield all the tuples yri...ri (i>=3), where
|yri...ri|qq = |yri...|q.-------------(5)
and after this "tail reduction" the expression (4) contains all the ri (i>=2) symmetrically.
4) x = yri...ri, where i>=3 and y does not contain ri. iThen, (4) contains all the similar tuples
yr3...r3, ..., yrn-a...rn-a
with the same coefficient c(x). Applying the permutations mentioned above we obtain n-a-2 copies of each tuple yri...ri (i>=2). Here (5) holds as well, and after the "tail reduction" the expression (4) contains all the ri (i>=2) symmetrically.
Hence, we have obtained the following representation of T(qq) (where q is any number not contained in q):
T(qq) = Sumx{ c'(x)|x|q },
where x ranges over all q-admissible tuples, and the coefficients c'(x) can be computed from x, q and q. This representation contains all the numbers r not in qq symmetrically.
Hereby our induction step is concluded.
Thus, we have proved that the estimate T(qq) of any tuple qq (without repetitions) can be computed from the probabilities |x|q of all q-admissible tuples x. This proves the correctness of the exclusion algorithm described in Section 5.
Concluding remark. For the empty tuple o our result means that the estimate T(o) depends only on the number n and a symmetric set Sk of n-tuples from the set {1, 2, ..., n}. These are the only parameters of Section 5 algorithm. In particular, when
Sk = { (x1...xn) | xi <> xi+1 for >=k values of i },
then, as we have shown in Section 5:
T(o) / n! = P{ Z2+Z3+...+Zn>=k ),
where the random variables Zi are defined in Section 3.
[Ba 74-1] J.Barzdin. Limiting synthesis of tau-indices. "Theory of Algorithms and Programs", vol. 1, Latvia State University, 1974, pp. 112-116 (in Russian)
[Ba 74-2] J.Barzdin. Prediction and limiting synthesis of finite automata. "Theory of Algorithms and Programs", vol. 1, Latvia State University, 1974, pp. 129-144 (in Russian)
[BF 72] J.Barzdin, R.Freivald. On the prediction of general recursive functions. "Soviet Math. Dokl.", 13, 1972, pp. 1224-1228
[BF 74] J.Barzdin, R.Freivald. Prediction and limiting synthesis of effectively enumerable classes of functions. "Theory of Algorithms and Programs", vol. 1, Latvia State University, 1974, pp. 101-111 (in Russian)
[FBP 91] R. Freivalds, J. Barzdins, and K. Podnieks. Inductive inference of recursive functions: complexity bounds.� Lecture Notes in Computer Science, 502, Springer-Verlag, 1991, pp. 111-155�
[LMS 56] K.de Leeuw, E.F.Moore et al. Computability by probabilistic machines. "Automata Studies (Ann. of Math. Studies, No.34)", Princeton Univ. Press, Princeton, N.J., 1956, pp. 183-212
[Po 75] K.Podnieks. Probabilistic synthesis of enumerated classes of functions. "Soviet Math. Dokl.", 16, 1975, pp. 1042-1045
[Po 77-1] K.Podnieks. Computational complexity of prediction strategies. "Theory of Algorithms and Programs", vol. 3, Latvia State University, 1977, pp. 89-102 (in Russian)
[Po 77-2] K.Podnieks. Probabilistic program synthesis. "Theory of Algorithms and Programs", vol. 3, Latvia State University, 1977, pp. 57-88 (in Russian)
Back to title page