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 s_{1}, s_{2}, s_{3}, s_{4},
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):

j_{1} |
1 | 2 | 3 | 4 |

j_{2} |
2 | 3 | 4 | 2 | 3 | 4 |

j_{3} |
3 | 4 | 3 | 4 | 3 | 4 | 3 | 4 |

j_{4} |
4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 |

Segments split the first row according to the probability
distribution (q_{1}, q_{2}, q_{3}, q_{4})
of Section 4. The first 3 segments of
the second row split q_{1} according to the distribution
(q_{12}, q_{13}, q_{14}). The segments of
the third row split q_{12} to (q_{123}, q_{1124}
), and q_{22} - to (q_{223}, q_{224}). In
the last row we have (with probability 1) the hypothesis 4 - the
only "right" s-index of s_{4}.

Let us introduce a more convenient notation:

|1|=q_{1}, |2|=|22|=q_{12},

|12|=q_{12}, |133|=q_{13},

|123|=q_{123}, |224|=q_{224},...

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 + 0^{j1})=1 &
M(gamma + 0^{j2})=2 & M(gamma + 0^{j3})=3},

|223| = P{M(gamma + 0^{j1})=2 &
M(gamma + 0^{j3})=3}.

Then, the probability that by the function s_{4} 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 s_{4}
would have been excluded (instead of s_{3}), then instead
of (a) we would have had the sum

|12|+|14|+|224|. --------------(aa)

Hence, when the functions s_{1}, s_{2} have
been already excluded, it would be sensible to exclude next s_{3}
or s_{4} 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 j_{3}.

Now let us consider the level j_{2}. The function s_{1}
is already excluded. We know the probabilities |1|, |2|, |3|,
|4|, |12|, |13|, |14|. What of the functions should be excluded
next - s_{2}, s_{3} or s_{4}? The
decision "exclude s_{2}" 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 j_{2}. The corresponding sums for s_{3} and
s_{4} are

|1|+|3|+|13|, ------------(bb)

|1|+|4|+|14|. ------------(bbb)

Hence, the maximum of (b), (bb) and (bbb) should decide, which
of the functions s_{2}, s_{3}, s_{4}
should be excluded next, after s_{1}. And this can be
really decided at the level j_{2}.

Finally, let us consider the level j_{1}. The decision
"exclude s_{1}" 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 s_{2}, s_{3}, s_{4}
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 s_{i} 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 s_{4}.

At the level j_{1} 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 s_{1}, then:

1+3*|1| >= 7 / 4.

If, after this, s_{2} is excluded, then:

|1|+|2|+|12| >= 7 / (4*3).

Finally, the exclusion of s_{3} 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, s_{4}, >=2}>= P{M(gamma + 0^{j1})=1
& M(gamma + 0^{j2})=2} +

+ P{M(gamma + 0^{j1})=1 & M(gamma +
0^{j2})=3}+

+ P{M(gamma + 0^{j1})=2 & M(gamma +
0^{j3})=3}>=

>= (1-delta)^{2}q_{12} +
(1-delta)^{2}q_{13} + (1-delta)^{3}q_{223}
>=

>= (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, s_{4}, >=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{ Z_{2}+Z_{3}+Z_{4}
>= 2 }, ----------------(2)

where Z_{i} are independent random variables such that

P{Z_{i}=1} = 1/i, P{Z_{i}=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 BF_{tau,pi} by the
function s_{4} = 0^{oo}, where

tau = (s_{1}, s_{2}, s_{3},
s_{4}),

s_{1} = 010^{oo}, s_{2}
= 0010^{oo}, s_{3} = 00010^{oo}, s_{4}
= 0^{oo},

pi = {1/4, 1/4, 1/4, 1/4}.

Indeed, the hypothesis BF_{tau,pi}(<0>) = 1, 2,
3 or 4 with equal probabilities 1/4. Further, if BF_{tau,pi}(<0>)
= 1, then BF_{tau,pi}(<0,0>) = 2, 3 or 4 with
probabilities 1/3. If BF_{tau,pi}(<0>)=1 & BF_{tau,pi}(<0,0>)=2,
then BF_{tau,pi}(<0,0,0>) = 3 or 4 with
probabilities 1/2. If BF_{tau,pi}(<0>) = 2, then BF_{tau,pi}(<0,0>)
= 2 with probability 1, and BF_{tau,pi}(<0,0,0>) =
3 or 4 with probabilities 1/2. Finally, the hypothesis BF_{tau,pi}(<0,0,0,0>)=4
with probability 1.

By using the function tree from the proof of Lemma 3:

----> 010^{oo}......----> 0010^{oo}....---->
00010^{oo}................................................................

|..b_{0}..................|..b_{1}...................|..b_{2}................................................................................

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

---------------------------------------------------------------------------->
a .........(0^{oo})

S_{0}.....................S_{1}.....................S_{2}.....................................................................................

where b_{0} = b_{1} = b_{2} = a = 1/4,
we obtain:

P{BF_{tau,pi}(<0>)<>BF_{tau,pi}(<0,0>)}
= b_{0 }/ (b_{0}+b_{1}+b_{2}+a) =
1/4.

P{BF_{tau,pi}(<0,0>)<>BF_{tau,pi}(<0,0,0>)}
= b_{1 }/ (b_{1}+b_{2}+a) = 1/3.

P{BF_{tau,pi}(<0,0,0>)<>BF_{tau,pi}(<0,0,0,0>)
= b_{2 }/ (b_{2}+a) = 1/2.

By Lemma 3, the following X_{i} (i=0, 1, 2) are
independent random variables:

X_{i} = 1, if BF_{tau,pi}(<0^{i}>)
<> BF_{tau,pi}(<0^{i+1}>),

X_{i} = 0, otherwise.

Hence, the triple (X_{0}, X_{1}, X_{2})
coincides with the triple (Z_{4}, Z_{3}, Z_{2}).
Since the sum X_{0}+X_{1}+X_{2} = Z_{4}+Z_{3}+Z_{2
}represents the number of mindchanges of M by the function 0^{oo},
we obtain that

7/(4*3*2) = P{ Z_{2}+Z_{3}+Z_{4}
>= 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} = Sum_{y}{
|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} = Sum_{y}{|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 p_{1}, ..., p_{a}
of the a-tuple **p** = (p_{1 }... p_{a})
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 |**z**q|_{p}
are splitted:

|**z**q|_{p}
= Sum_{y}{|**z**qy|_{pq}
| y not in **p** and y<>j}|.
---------------(a)

The other probabilities are retained:

|**z**y|_{p}
= |**z**yy|_{pq},

where y<>q (and, of course, y not in **p**,
since **z**y is **p**-admissible). The
left hand side tuples of (a) and (b) are called **p**q-admissible.

Obviously, the tuple (x_{1}...x_{a+1}) is **p**-admissible
(where **p**=(p_{1}...p_{a})), if
and only if for all i<=a:

(1) x_{i+1} not in {p_{1}, ..., p_{i}},

(2) x_{i} not in {p_{1}, ..., p_{i})
implies x_{i+1} = x_{i}.

At the very end of the exclusion process we will have some
permutation (p_{1}...p_{n}) of the set {1, 2,
..., n}. Let us denote **p** = (p_{1}...p_{n-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** = (x_{1}...x_{n})
having the property: x_{i} <> x_{i+1} for
at least k values of i (k is a natural number, k<n). Let us
denote by S_{k} the set of all such **x**'s.
We will use only the symmetricity of S_{k}, i.e. if pi is
any permutation of the numbers {1, 2, ..., n}, then

(x_{1}...x_{n}) in S_{k}
<--> (pi(x_{1})...pi(x_{n})) in S_{k}.

The "quality" of every permutation (p_{1}...p_{n})
of the set {1, 2, ..., n} is defined by the probability

T(**p**) = Sum_{x}{
|**x**|_{p }},

where **x** ranges over all **p**-admissible
n-tuples of S_{k} (recall that **p** = (p_{1}...p_{n-1})).

We extend this "quality" definition to any tuple **q**
= (q_{1}...q_{a}) containing no repetitions
(a<=n-1).

If a<=n-2 and **q** contains all the numbers
of the set {1, 2, ..., n} except q_{a+1}, ..., q_{n},
then we define by recursion:

T(**q**) = T(**q**q_{a+1})+T(**q**q_{a+2})+...+T(**q**q_{n}).

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(**q**q) can be
computed having the probabilities |**x**|_{q}
for all **q**-admissible (a+1)-tuples **x**.
This will be proved by showing that T(**q**q) can be
represented as

T(**q**q) = Sum_{x}{
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** = (q_{1},
..., q_{n-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 **q**q-admissible tuple **x**
= (x_{1}, ..., x_{n}) we have x_{n} = t,
and |**x**|_{qq} = |x_{1}...x_{n-1}|_{q},
hence,

T(**q**q) = Sum_{y}{
c(**y**)|**y**|_{q}
},

where **y** ranges over all **q**-admissible
(n-1)-tuples, and

c(**y**) = 1, if **y**t
in S_{k},

c(**y**) = 0, otherwise.

Now let us consider the next case **q** = (q_{1},
..., q_{n-3}). By q, s, t we denote the 3 numbers which
do not belong to **q**. Then, by definition:

T(**q**q) = T(**q**qs)
+ T(**q**qt).

As we already know,

T(**q**qs) = Sum_{x}{
|x|_{qq }},----------------- (1)

where **x** ranges over **q**q-admissible
(n-1)-tuples such that **x**t in S_{k}. The
set S_{k} is symmetric, therefore, replacing s by t in
(1), we will obtain T(**q**qt).

The sum expression T(**q**qs)+T(**q**qt)
can be simplified considering the following cases, where **x**
is an arbitrary tuple of the expression (1):

1) **x** = **y**s, where **y**
does not contain s, t. Then, replacing s by t, we obtain **y**t,
and

|**y**s|_{qq}
+ |**y**t|_{qq} = |**y**|_{q}.

2) **x **= **y**t, similarly.

3) **x** = **y**ss...s, where **y**
does not contain s, t. Then, replacing s by t, we obtain **y**tt...t,
and

|**y**ss...s|_{qq}
= |**y**ss...|_{q},

|**y**tt...t|_{qq}
= |**y**tt...|_{q}.

4) **x**=**y**tt...t, similarly.

Hence, we obtain the following representation of T(**q**q):

T(**q**q)= Sum_{x}{
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** = (q_{1}...q_{a}) be a
tuple without repetitions, and the numbers q, r_{2}, ...,
r_{n-a} do not belong to **q**. Let us
suppose that

T(**q**qr_{2}) = Sum_{x}{
c(**x**)|**x**|_{qq}
}, --------------(3)

where **x** ranges over all **q**q-admissible
tuples, and the following symmetricity condition holds: if **x**
is **q**q-admissible, and **s** = (s_{3},
..., s_{n}-a) is any permutation of the numbers (r_{3},
..., r_{n-a} ), then the action of **s** on **x**
yields a tuple **y** such that c(**y**)=c(**x**).

By definition:

T(**q**q) = T(**q**qr_{2})+T(**q**qr_{3})+...+T(**q**qr_{n-a}).----------------
(4)

To obtain from (3) a representation of T(**q**qr_{i})
(where i>=3), one can apply to all **q**q-admissible
(a+2)-tuples **x** the permutation of the set {1, 2,
..., n} transposing r_{2} and r_{i}. Thus, the
expression (4) can be simplified by considering the following
cases:

1) **x **= **y**r_{2}, where
**y** does not contain r_{2}. Applying the
permutations mentioned above we obtain the tuples **y**r_{3},
..., **y**r_{n-a}, and

|**y**r_{2}|_{qq}
+ |**y**r_{3}|_{qq}
+ ... + |**y**r_{n-a}|_{qq}
= |**y**|_{q}.

2) **x** = **y**r_{i}, where
i>=3 and **y** does not contain r_{i}.
Then, (3) contains **all** the tuples of this kind: **y**r_{3},
..., **y**r_{n-a}, and with the same
coefficient c(**x**). Applying the permutations of
the set {1, 2, ..., n} mentioned above we obtain from **y**r_{i}:
a) the tuple **y**r_{2}, b) n-a-3 copies of **y**r_{i}
itself. All this will be included into (4):

(n-a-2)(|**y**r_{2}|_{qq}
+ ... + |**y**r_{n-a}|_{qq})
= (n-a-2)|**y**|_{q}.

3) **x** = **y**r_{2}...r_{2},
where **y** does not contain r_{2}. The
permutations mentioned above yield all the tuples **y**r_{i}...r_{i}
(i>=3), where

|**y**r_{i}...r_{i}|_{qq}
= |yr_{i}...|_{q}.-------------(5)

and after this "tail reduction" the expression (4)
contains all the r_{i} (i>=2) symmetrically.

4) **x** = **y**r_{i}...r_{i},
where i>=3 and **y** does not contain r_{i}.
iThen, (4) contains all the similar tuples

**y**r_{3}...r_{3},
..., **y**r_{n-a}...r_{n-a}

with the same coefficient c(**x**). Applying the
permutations mentioned above we obtain n-a-2 copies of each tuple
**y**r_{i}...r_{i} (i>=2). Here
(5) holds as well, and after the "tail reduction" the
expression (4) contains all the r_{i} (i>=2)
symmetrically.

Hence, we have obtained the following representation of T(**q**q)
(where q is any number not contained in **q**):

T(**q**q) = Sum_{x}{
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 **q**q
symmetrically.

Hereby our induction step is concluded.

Thus, we have proved that the estimate T(**q**q)
of any tuple **q**q (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 S_{k} of n-tuples from the
set {1, 2, ..., n}. These are the only parameters of Section 5 algorithm. In particular, when

S_{k} = { (x_{1}...x_{n})
| x_{i} <> x_{i+1} for >=k values of i
},

then, as we have shown in Section 5:

T(**o**) / n! = P{ Z_{2}+Z_{3}+...+Z_{n}>=k
),

where the random variables Z_{i} 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