数理解析研究所講究録
第 818 巻 1993 年 20-34

20

On Malign Input Distributions for Algorithms

東工大・理小林孝次郎 (Kojiro Kobayashi)

1 Introduction
One important problem in the theory of complexity of computation is how the average-casecomputation time of algorithms is related to the probability distribution of inputs.

Concerning this problem, Li and Vit\’anyi [2] found an interesting result that if inputs

to algorithms are selected with the probability that is proportional to a semicomputablemeasure that is known as an a priori measure [3], then the worst-case computation time
and the average-case computation time are roughly the same for any algorithm. A more
precise statement of this result is as follows.
By a measure we mean a function

$\mu$

from

real numbers such that $\mu(x)\geq 0$ for any
and a measure , let$\mu$$\{0,1\}^{n}$$t_{A}^{wo}(n)$$x$$\{0,1\}^{*}$(the set of all binary sequences) toand $\mu(\{0,1\}^{*})<\infty$ . For an algorithm

denote the worst-case computation time of(the set of all binary sequences of length n) and let

computation time of$A$

for inputs from$\{0,1\}^{n}$$t_{A}^{av,\mu}(n)$where a sequence

$x$

$A$

$A$

for inputs fromdenote the average-casein$\{0,1\}^{n}$with the probability $\mu(x)/\mu(\{0,1\}^{n})$ . Li and Vit\’anyi’s result says that if

measure then for any algorithm$A$

there exists a constant $c(>0)$ such that$\mu$

is given to$A$

is an a priori$t_{A}^{wo}(n)\leq ct_{A}^{av,\mu}(n)$for any . Miltersen [4] called measures having this property “malign measures.” Then Li$n$and Vit\’anyi’s result says that a priori measures are malign.
A priori measures are very complicated mathematical objects and it is difficult to imag-

ine a real situation where inputs are generated with the probability that is proportional toan a priori measure. Hence, if “a priori”-ness and malignness are equivalent, we may regard

Li and Vit\’anyi’s result as one interesting but pathological phenomenon. In the present pa-

21per, we consider the problem of whether the two notions “a priori”-ness and malignness aredifferent or not.
For this problem, we first introduce the notion of strongly malign measures and point out

that what Li and Vit\’anyi proved is that a priori measures are strongly malign. Although theintuitive notion of malignness allows several natural variations of definition of malignness
other than the one introduced by Miltersen, strong malignness seems to imply all of thesevariations. Hence we may regard strong malignness as the strongest of these variations.
Then we show that there exists a semicomputable strongly malign measure that is not apriori. This means that the two notions “a priori”-ness and malignness are different in onestrong sense.
We also show two results concerning a priori measures and Kolmogorov complexity. Fora rational number

such that $0<p<1$ , let$p$prefix-free algorithm$A_{U}$$A_{U}$$P_{p}(x)$denote the probability that a universal

outputs a binary sequenceis randomly selected with

$p$

$x$

when the input binary sequence toas the probability that the symbol 1 is selected. It is known

that $P(x)=P_{1/2}(x)$ is an a priori measure. We show that $P_{p}(x)$ is an a priori measure foreach . Let $H_{p}(x)$ denote the smallest of
$p$

$x$

of

when
$O’ s$$u$is given to

in u)

$+$

$A_{U}$$|u|_{p}$as an input, wherefor binary sequences$|u|_{p}$$u$such that$A_{U}$

outputs

denotes the value ( $-\log_{2}$ (1-p))(number( $-\log_{2}$ p)(number of l’s in ). The value $H(x)=H_{1/2}(x)$ is known as the$u$(prefix-free algorithm based) Kolmogorov complexity of . We show that for each$x$exists a constant

$c$

$p$

there

such that $|H(x)-H_{p}(x)|\leq c$ for any .
$x$

2 Preliminaries
Let$\Sigma$denote the set $\{0,1\}$ of two symbols $0,1,$of length , and$\Sigma^{*}denote$each word , let

$|x|$

$n$

$x$

$\Sigma^{0}\cup\Sigma^{1}\cup\Sigma^{2}\ldots$

denote its length. Letof length . We use $N,$ $Q,$$0$

the set$R$$\Sigma^{n}$$\lambda$

denote the set of all sequences of $0,1$. We call an element of$\Sigma^{*}$

a word. For

denote the empty word, that is, the sequence

to denote the sets of ail natural numbers, all rational numbers,

22
and all real numbers respectively. We as sume that some standard one-to-one mapping from
$N$

onto

$\Sigma^{*}$

is fixed and we identify a number with its corresponding word. Throughout inthis paper, $\log x$ means$\log_{2}x$.

By a measure we mean a function$\mu(\Sigma^{*})<\infty$(for$L\subseteq\Sigma^{*},$$\mu(L)$denotes

$\mu$

from

$\Sigma^{*}$$\Sigma_{x\in L}\mu(x)$

to

$R$

). A measure

if there exists a computable function $fbom\Sigma^{*}\cross N$ to$n\leq n’$

such that $\mu(x)\geq 0$ for any$Q$and $hm_{narrow\infty}f(x, n)=\mu(x)$ . For two functions $f,$$\mu$such that $f(x, n)\leq f(x, n’)$ for

$g$

from

$N$

to

$R$

, we write$n$$g_{\sim}<f$andis said to be semicomputable

there exists a constant $c(>0)$ such that $f(n)\leq cg(n)$ for any . We write$f_{\sim}<g,$$x$$f\approx g$$f_{\sim}<g$

if

if both ofhold true.

By an algorithm we mean a deterministic Turing machine. We assume that algorithms
accept words as inputs and generate words as outputs if they halt. Let
put of an algorithm$A$$\phi_{A}(x)$for an input . When the algorithm does not halt,$x$denote the out-$\phi_{A}(x)$is undefined.

We assume that some standard one-to-one mapping from the set of all (representations of)algorithms onto$\Sigma^{*}$

is fixed and we identify an algorithm with its corresponding word.

By a step counting function, we mean any partial function $time_{A}(x)$ that assigns anatural number to an algorithm(the “Blum’s axioms” [1]): (1)($time_{A}(x)\leq t$’

on $A,$

$x,$

$t$

$A$

and an input$\phi_{A}(x)$$x$that satisfies the following two conditions

is $defined\Leftrightarrow time_{A}(x)$ is defined; (2) the predicate

is decidable. We understand that the predicate “time $A(x)\leq t’$)

is false when $time_{A}(x)$ is undefined.

Suppose that one step counting function is fixed. We define the worst case computation

time$tW^{o}(n)$of an algorithm$A$

for inputs of length$n$by $t_{A}^{wo}(n)= \max_{x\in\Sigma\hslash}time_{A}(x)$ . For

each measure , we define the average case computation time$\mu$

inputs of length

$n$

by

$t_{A}^{av,\mu}(n)=\Sigma_{x\in\Sigma n}(\mu(x)/\mu(\Sigma^{n}))$Definition 1 ([4]) A measure$\mu$$t_{A}^{av,\mu}(n)$of an algorithm A fortime $A(x)$ .

is malign if it satisfies the following two conditions forany step counting function: (i) $\mu(\Sigma^{n})>0$ for any ; (ii) for any algorithm$n$all inputs there exists a constant $c(>0)$ such that$t_{A}^{wo}(n)\leq ct_{A}^{av,\mu}(n)$$A$that halts forfor any .
$n$23
3 A Priori Measures
There are several equivalent ways to define a priori measures. The first is to define themas semicomputable measures that are largest among$a\mathbb{I}$semicomputable measures.

Definition 2 An a priori measure is a semicomputable measurecomputable measure$\mu’$$\mu$such that for any semi-

there exists a constant $c(>0)$ such that $\mu’(x)\leq c\mu(x)$ for any .
$x$Existence of such measures is well-known ([3]).

Other ways to define a priori measures use prefix-free algorithms. For two words$y$is a prefx of$x$

if there exists a word

if it contain no two different words$\Sigma_{x\in L}2^{-|x|}$such that $yz=x$ . A set of words

$z$

$x,$

such that

$y$

$y$

$A$

$y$

,

is prefix-free

is a prefix of . Note that the value$x$is always defined and is at most 1 for any prefix-free set

An algorithm

$L$

$x,$

$L$

.

is prefix-free if the domain $dom(\phi_{A})$ of the partial function$\phi_{A}$is prefix-

free. It is well-known that there exist one prefix-free $algorithmA_{U}\sim$ and one prefix-free setof words$L_{U}$

that satisfy the condition: for any prefix-free algorithm

such that $\phi_{A_{U}}(hx)=\phi_{A}(x)$ for any
and the word

$h$

$x$

. We call sucha code of the algorithm

$A$

for

$A_{U}$$A_{U}$. We use$A$

there exists $h\in L_{U}$a universal prefix-free algorithm$A_{U}$

and$L_{U}$

to denote some fixed

universal prefix-free algorithm and set of codes.
For each word$x$

we define a real number $P(x)$ and a natural number $H(x)$ by $P(x)=$$\Sigma_{y}\{2^{-|y|}|\phi_{A_{U}}(y)=x\}$$\Sigma_{x}\{f(x)|S(x)\}$and $H(x)= \min\{|y||y\in\Sigma^{*}, \phi_{A_{U}}(y)=x\}$ . (We use the notation

to denote the sum of $f(x)$ for all words$x$that satisfy the condition $S(x).)$The value $P(x)$ is the probability that a randomly selected infinite sequence of $0,1$ starts
with a word$y$such that$\phi_{A_{U}}(y)=x$. The value $H(x)$ is the value that is known as the(prefix-free algorithm based) Kolmogo $rov$ complexity ofa priori measures$\mu$

is by the condition

third is by the condition

$\mu$

(
$\mu$

$x$

([3]). The second way to define

is semicomputable and $\mu(x)\approx P(x)$ and theis semicomputable and $\mu(x)\approx 2^{-H(x)}$ . These three definitionsof a priori measures are equivalent. From now on we fix one a priori measure and denote itby .
$\tilde{\mu}$24Theorem 1 ([2]) If$\mu$

is an a priori measure then it is malign.

The proof in [2] is quite simple. However, here we devide it into two parts to make

Proof.

its logical structure clearer. The proof of the condition $\mu(\Sigma^{n})>0$ is easy and we omit it.
Let

$\mu$

be an a priori measure and let$A$

be an algorithm that halts for all inputs. Supposethat a step counting function is fixed. Let $w(n)$ denote one of the worst inputs of length .
$n$(1) The proof that there exists a constant $c(>0)$ such that $\mu(w(n))\geq c\mu(\Sigma^{n})$ for anyLet$A_{0}$$n$.

be an algorithm such that$\phi_{A_{0}}(y)=\{\begin{array}{l}w(|\phi_{A_{U}}(y)|)undefi ned’\end{array}$This algorithm$A_{0}$

is prefix-free. Let$h$$oth^{U}erwise\phi_{A}(y)is$defined,be one of its codes. Then there exist constants$c_{1},$$c_{2}$$(>0)$ such that we have, for any $n,$ $\mu(w(n))\geq c_{1}P(w(n))\geq c_{1}2^{-|h|}\Sigma_{y}\{2^{-|y|}|\phi_{A_{0}}(y)=w(n)\}$$\geq c_{1}2^{-|h|}P(\Sigma^{n})\geq c_{1}2^{-|h|}c_{2}\mu(\Sigma^{n})$$\mu(w(n))\geq c\mu(\Sigma^{n})$. Denoting the constant $c_{1}2^{-|h|}c_{2}(>0)$ by , we have$c$for any .
$n$(2) The proof that $t_{A}^{wo}(n)\leq(1/c)t_{A}^{av,\mu}(n)$ for any$n$. For any , we have$n$time $A(x)\mu(x)/\mu(\Sigma^{n})\geq time_{A}(w(n))\mu(w(n))/\mu(\Sigma^{n})\geq ct_{A}^{wo}(n)$.

$t_{A}^{av,\mu}(n)=\Sigma_{x\in\Sigma^{n}}$$\square$

4 Strongly Malign Measures
We defined malignness by Definition 1. However, there are several other ways to define theintuitive notion of malignness. The variations come from two factors.
First factor is what kind of step counting functions are allowed. In [2], this factor was notclearly stated. One extreme way is to fix one step counting function such as the number ofsteps performed by Turing machines. This is the approach adopted in [4]. Another extreme
way is to allow all step counting functions that satisfy the Blum’s axioms. Our definition
adopts this approach. There are many other ways that are in between these two extreme

approaches. At present, we do not know whether the notions of malignness defined by these

two extreme approaches are different or not.

25
The second factor is how to define the sizes of inputs. In Definition 1, the size of an
input

$x$

meant its length$|x|$more loosely. For example, if. However, in practice we use the term “size of an input”$A$

is an algorithm for computing the product of two Boolean

matrices, we will use (an input of size
representation of two$n\cross n$$n$’

to denote a bit sequence of lengththat is the$2n^{2}$bit matrices. Generally, the definition of the size of an input

depends on the algorithm that uses them as inputs.
There are several ways to formally define malignness. However, it is interesting to notethat Li and Vit\’anyi’s result that a priori measures are malign seems to hold true for all ofthese variations of the definition of malignness. Therefore, a priori measures might have

one essential feature from which follows the malignness of a priori measure for all thesevariations.
Analyzing the proof of Li and Vit\’anyi’s result (Theorem 1), we see that what theyessentially proved is the following property of a priori measures .
$\mu$(A1) There exists a constant $c(>0)$ such that $\mu(w(n))\geq c\mu(\Sigma^{n})$ for any

The malignness of

$\mu$

$n$

.

immediately follows $hom$ (A1). However, Li and Vit\’anyi’s proof canbe readily modified to prove the following stronger property.
(A2) For any two partial recursive functions
$N$

$f$

from

$N$

to

$\Sigma^{*}$

and

$g$

from

, there exists a constant $c(>0)$ such that $\mu(f(n))\geq c\mu(g^{-1}(n))$ for any$\Sigma^{*}$

$n$

to

such

that $f(n)$ is defined.
We think that the porperty (A2) is a feature of a priori measures that deserves investigationin itself and call measures that have this property (A2) “strongly malign.”

Definition 3 A measure$\mu$

is strongly malign if it satisfies the following two conditions:(1) $\mu(\Sigma^{*})>0$ ;(2) for any algorithms $A,$if$\phi_{A}(n)$is defined then$B$

, there exists a constant $c(>0)$ such that, for any $n\in N$ ,$\mu(\phi_{A}(n))\geq c\mu(\phi_{B}^{-1}(n))$.

26
As is expected, a priori measures are strongly malign and strongly malign measures aremalign.
Theorem 2 A priori measures are strongly malign.
Proof.

Let$\mu$be an a priori measure. Suppose that $A,$ $B$ are algorithms. Let

algorithm such that$\phi_{A_{0}}(y)=\phi_{A}(\phi_{B}(\phi_{A_{U}}(y)))$becomes a proof of the strong malignness of$\phi_{B}(\phi_{A_{U}}(n))$

and$\Sigma^{n}$with$\phi_{B}^{-1}(n)$$A_{0}$

be an. Then the step (1) of the proof of Theorem 1$\mu$

if we replace $w(n)$ with$\phi_{A}(n),$$|\phi_{A_{U}}(n)|$

with

.

$\square$

The proof of the following theorem is easy and we omit it.
Theorem 3 Strongly malign measures are malign.
Let AP, SSMAL, SMAL, MAL denote the following classes of measures: $AP=the$ classof all a priori measures, SSMAL $=the$ class of all semicomputable strongly malign measures,
SMAL $=the$ class of all strongly malign measures, MAL $=the$ class of all malign measures.

The above theorems imply $AP\subseteq SSMAL\subseteq SMAL\subseteq MAL$ . We will show that these fourclasses are all different. To show $SSMAL\neq SMAL$ and $SMAL\neq MAL$ is straightforward.
Theorem 4 There exists a strongly malign measure that is not semicomputable.
Proof (an outline).
let $X$ be the set

For each$\{x_{0}, x_{1}, \ldots\}$

$n$

let

$x_{n}$

be a word of length$n$such that $H(x_{n})\geq n/2$ and. We can relativize the notions of “a priori”, “strongly malign”

and $H(x)$ with respect to $X$ . Let$\mu$be a measure that is a priori relative to $X$ . Thenstrongly malign relative to $X$ and is hence strongly malign. Let
Then we can prove that there exist constants$\geq c_{2}2^{-H^{X}(x_{n})}\geq c_{2}2^{-2\log n}=c_{2}/n^{2}$shows that$\mu$

for any$n$$c_{1},$$c_{2}$

such that$\tilde{\mu}$

$\mu$

is

be an a priori measure.

$\tilde{\mu}(x_{n})\leq c_{1}2^{-n/2}$and$\mu(x_{n})$( $H^{X}(x)$ denotes the relativized $H(x)$ ). This

is not semicomputable.

Theorem 5 There exists a malign measure that is not strongly malign.

$\square$27
Proof (an outline).
$\mu$

Let

$\tilde{\mu}$be an a priori measure. We can easily show that the measuredefined by $\mu(x)=\tilde{\mu}(x)/|x|$ is malign and is not a priori.

$\square$5 Characterizations of a Priori and Strongly Malign Measures
Before proceeding to the proof of AP $\neq SSMAL$ we give some characterizations of the twoclasses AP and SMAL. These characterizations show an essential difference, if any, of thetwo classes AP and SSMAL.

Theorem 6 For a measure , the following two conditions are equivalent.
$\mu$

(1)

$\mu$

(2)

$\mu$

is a strongly malign measure.

satisfies the conditions:(i) $\mu(\Sigma^{*})>0$ ;(ii) for any algorithm$A$

there exists a constant $c(>0)$ such that $\mu(x)\geq c\mu(\phi_{A}^{-1}(x))$

for any .
$x$(I) Proof of (1)$\Rightarrow(2)$. Suppose that$\mu$

is strongly malign. Let$A$

be an algorithm. Let $B,$$C$

be algorithms such that $\phi_{B}(n)=n,$ $\phi_{C}(y)=\phi_{A}(y)$ . Then there exists a constant $c(>0)$
such that$\mu(\phi_{B}(n))\geq c\mu(\phi_{\overline{C}}^{1}(n))$$=c\mu(\phi_{A}^{-1}(x))$

for any(II) Proof of (2)

Let

$C$

$\Rightarrow(1)$$x\in\Sigma^{*}$

for any $n\in N$ , and hence $\mu(x)=\mu(\phi_{B}(x))\geq c\mu(\phi_{C}^{1}(x))$.

. Suppose that a measure$\mu$satisfies $(i)-(ii)$ . Let $A,$

be an algorithm such that $\phi_{C}(y)=\phi_{A}(\phi_{B}(y))$ for any

constant $c(>0)$ such that$\mu(x)\geq c\mu(\phi_{\overline{C}}^{1}(x))$$c\mu(\phi_{\overline{C}}^{1}(\phi_{A}(n)))\geq c\mu(\phi_{B}^{-1}(n))$

Recall that by$\tilde{\mu}$for any

for any $n\in N$ such that$x\in\Sigma^{*}$$\phi_{A}(n)$$y\in\Sigma^{*}$$B$. There exists a. Then we haveis defined.

we denote some fixed a priori measure.

Theorem 7 For a measure , the following two conditions are equivale $nt$ .
$\mu$

(1)
(2)

$\mu$

$\mu$

is an a priori measure.

satisfies the conditions:be algorithms.

$\mu(\phi_{A}(n))\geq$$\square$

28
(i)

$\mu$

is semicomputable;(ii) $\mu(\Sigma^{*})>0$ ;(iii) there exists a constant $c(>0)$ such that
$A$

$B$

$x$

$\Rightarrow(2)$

. Let

$\mu$

be an a priori measure. It is obvious that (i), (ii) hold true.

be a prefix-free algorithm such that $\phi_{B}(uv)=\phi_{w}(\phi_{A_{U}}(v))$ , with $w=\phi_{A_{U}}(u)$ , and let$h$be one of its codes. If is a description of$v$

is a description of a word in$u$there exist constants$\mu(x)$$\geq$

each word$x_{0}$$c_{1},$$c_{2}(>0)$$c_{1}P(x)$$=$$\phi_{A}^{-1}(x)$$A$(that is, a wordsuch that $\phi_{A_{U}}(u)=A$ ) and, then we have $\phi_{A_{U}}(huv)=\phi_{B}(uv)=x$ . Therefore

such that$c_{1}\Sigma_{y}\{2^{-|y|}|\phi_{A_{U}}(y)=x\}$$c_{1}2^{-|h|}(\Sigma_{u}\{2^{-|u|}|\phi_{A_{U}}(u)=A\})(\Sigma_{v}\{2^{-|v|}|\phi_{A_{U}}(v)\in\phi_{A}^{-1}(x)\})$$=$$c_{1}2^{-|h|}P(A)P(\phi_{A}^{-1}(x))$$\Rightarrow(1)$let$A_{x_{0}}$is determined by$\geq$$c_{1}2^{-|h|}c_{2}\tilde{\mu}(A)\mu(\phi_{A}^{-1}(x))$(An outline). Suppose that a measure.

satisfies (i) –(iii). For$\mu$be an alrogithm such that $\phi_{A_{0}}.(x)=x_{0}$ for any$x_{0}$and hence there is a constantHence there is a constant $c_{2}(>0)$ such that$c\tilde{\mu}(A_{x_{0}})\mu(\phi_{A_{x_{0}}}^{-1}(x_{0}))\geq cc_{2}\tilde{\mu}(x_{0})\mu(\Sigma^{*})$$\mu(x_{0})\geq c_{3}\tilde{\mu}(x_{0})$$u$$\geq$(II) Proof of (2)$A_{x_{0}}$for any algorithm

and any .

(I) Proof of (1)Let$\mu(x)\geq c\tilde{\mu}(A)\mu(\phi_{A}^{-1}(x))$

for any$x_{0}$$c_{1}$$x$. The algorithm

such that $H(A_{x_{0}})\leq H(x_{0})+c_{1}$ .

$\tilde{\mu}(A_{x_{0}})\geq c_{2}\tilde{\mu}(x_{0})$, and we have

. Denoting the constant $cc_{2}\mu(\Sigma^{*})(>0)$ by. Moreover$\mu$

is semicomputable. Hence$\mu$$c_{3}$$\mu(x_{0})\geq$, we haveis a priori.

$\square$Comparing these two theorems, we see that the essential difference between SSMAL andAP lies in the difference of the behavior of$\mu(x)/\mu(\phi_{A}^{-1}(x))$

as a function of . For a measure$x$in SSMAL, this value is bounded from below by a constant $c_{A}(>0)$ that may depend on
the algorithm$A$. For a measure in AP, the same is true and moreover the constant

be represented as$c\tilde{\mu}(A)$with a constant $c(>0)$ that does not depend on

the problem of whether AP

$=$

$A$

$c_{A}$

can. Therefore,

SSMAL or not is the problem of whether the nonuniform

existence of constants for measures in SSMAL can be always changed to uniform existence

29
or not.

Semicomputable Strongly Malign Measures that are not a

6

PrioriWe show one method for constructing a family of semicomputable strongly malign measures.

This family contains some of a priori measures, and also measures that are not a priori.
Let
$1$

$f$

be a computable function from, and $f(uv, a)\geq f(v, a)$ for any

from$\Sigma^{*}$

to

$Q$

$P_{f}$$u_{1},$$v\in\Sigma^{*}$

to

and

$Q$

such that $f(u, a)>0,$ $f(u, O)+f(u, 1)\leq$$a\in\Sigma$. For this , let$f$$\pi_{f}$be the function

defined by $\pi_{f}(\lambda)=1$ and $\pi_{f}(a_{1}a_{2}\ldots a_{m})=f(\lambda,a_{1})f(a_{1},a_{2})f(a_{1}a_{2},a_{3})\ldots$$f(a_{1}a_{2}\ldots a_{m-1}, a_{m})$any words$u,$$\Sigma^{*}\cross\Sigma$$\ldots,$

for $m\geq 1$ . It is easy to show that$u_{m}$and that$\pi_{f}(u_{1}\ldots u_{m})\geq\pi_{f}(u_{1})\ldots\pi_{f}(u_{m})$for any prefix-free set$\Sigma_{\iota}\{\pi_{f}(s)|s\in L\}\leq 1$

$L$

for

. Finally, let

be the measure defined by $P_{f}(x)=\Sigma.\{\pi_{f}(s)|\phi_{A_{U}}(s)=x\}$ .
For two rational numbers

denote$\pi_{f}(u)$$q$such that $0<p,$ $0<q,$ $p+q\leq 1$ , let

and $P_{f}(x)$ respectively for the function

For a rational number$P_{1-p,p}(x)$

$p,$

$p$

such that $0<p<1$ , let$\pi_{p}(u)$

$x$

and

$|0|_{p}$and $-\log p$ respectively, for each word $u=a_{1}\ldots a_{m}$ let, and for each word

and $P_{q,p}(x)$defined by $f(u, 0)=q,$ $f(u, 1)=p$ .

$f$respectively. Moreover, for each $a\in\Sigma$ let$(=-\log\pi_{p}(u))$$\pi_{q,p}(u)$$P_{p}(x)$and$|u|_{p}$$|1|_{p}$denote $\pi_{1-p,p}(u)$ anddenote $-\log(1-p)$

denote $|a_{1}|_{p}+\ldots+|a_{m}|_{p}$let $H_{p}(x)$ denote $\min\{|u|_{p}|u\in\Sigma^{*}, \phi_{A_{U}}(u)=x\}$ .

In these notations, the measure $P(x)$ and the Kolmogorov complexity $H(x)$ introduced in

Section 3 are $P_{1/2}(x)$ and $H_{1/2}(x)$ respectively.
In this section we show four results: (1) $P_{f}(x)$ is semicomputable and strongly malign;(2) if $p+q<1$ then $P_{q,p}(x)$ is not a priori; (3)$P_{p}(x)$is a priori; (4) there is a constant$c$such that $|H(x)-H_{p}(x)|\leq c$ for any . The results (1), (2) imply AP $\neq SSMAL$ .
$x$

Theorem 8 The measure $P_{f}(x)$ is semicomputable and strongly malign.

Proof.
$P_{f}(x)$It is obvious that $P_{f}(x)$ is semicomputable. We use Theorem 6 to prove thatis strongly malign. It is obvious that $P_{f}(\Sigma^{*})>0$ . Let$A$

be an algorithm. Let$A_{0}$

30
be a prefix-hee algorithm such that
Then, for any$\phi_{A_{0}}(s)=\phi_{A}(\phi_{A_{U}}(s))$

and let$h$be one of its codes.

we have $P_{f}(x)=\Sigma_{r}\{\pi_{f}(r)|\phi_{A_{U}}(r)=x\}\geq\Sigma_{*}\{\pi_{f}(hs)|\phi_{A_{U}}(hs)=x\}\geq$$x$$\pi_{f}(h)\Sigma_{\ell}\{\pi_{f}(s)|\phi_{A_{U}}(s)\in\phi_{A}^{-1}(x)\}=\pi_{f}(h)P_{f}(\phi_{A}^{-1}(x))$. Denoting the constant $\pi_{f}(h)(>0)$

by , we have $P_{f}(x)\geq cP_{f}(\phi_{A}^{-1}(x))$ .

$\square$$c$

For a word $w=a_{1}a_{2}\ldots a_{n}$ of length
head$a_{1}a_{2}\ldots a$: ofTheorem 9 If

$f$

$w$

$n$

and

$i$

such that $0\leq i\leq n$ , let $w|i$ denote theof length .
$i$satisfies the condition$\lim_{narrow\infty}\max_{w\in\Sigma^{n}:}\prod_{=0}^{n-1}(f(w|i, 0)+f(w|i, 1))=0$

then the measure,

is not a priori.

$P_{J}(x)$Proof.

Let$f(u, 1))$ .

Suppose that $P_{f}(x)$ is a priori. Then there exists a constant $c(>0)$ such that$g$

$P_{g}(x)<cP_{f}(x)$Let$n_{0}$

any word

for any$x$

because$\Sigma^{*}\cross\Sigma$$P_{g}(x)$tois semicomputable.

of length$n$. For any word $s=a_{1}a_{2}\ldots a_{n}$ of length$=$$\prod_{:=1}^{n}f(a..a, a_{i})$$n\geq n_{0}$we have$\pi_{f}(s)\leq$$\pi_{9}(s)\prod_{:=1}^{n}(f(a_{1}\ldots a_{i-1},0)+f(a_{1\cdots:-1}a,1))$$=$$= \pi_{g}(s)\prod_{j=0}^{n-1}(f(s|j, 0)+f(s|j, 1))$$x$

defined by $g(u, a)=f(u, a)/(f(u, 0)+$because$\pi_{f}(s)$

Let

$Q$

be a value such that $\Pi_{i=0}^{n-1}(f(w|i, 0)+f(w|i, 1))\leq 1/c$ for any $n\geq n_{0}$ and$w$$(1/c)\pi_{g}(s)$be the function from$\leq$$(1/c)\pi_{g}(s)$be a word such that there is no oflength less than$s$.

$n_{0}$

such that $\phi_{A_{U}}(s)=x$ . Then

we have $P_{f}(x)=\Sigma_{s}\{\pi_{f}(s)|\phi_{A_{U}}(s)=x\}\leq\Sigma_{s}\{(1/c)\pi_{g}(s)|\phi_{A_{U}}(s)=x\}=(1/c)P_{g}(x)$ .
This contradicts $P_{g}(x)<cP_{f}(x)$ .
Corolary 1 If

$p,$

$q$

$\square$are rational numbers such that $0<p,$ $0<q,$ $p+q<1_{f}$ then $P_{q,p}(x)$ is

a semicomputable strongly malign measure that is not a priori.

31
Proof.

We have $\lim_{narrow\infty}\max_{w\in\Sigma\hslash}\Pi_{:^{-1}}^{n_{=0}}(f(w|i, 0)+f(w|i, 1))=\lim_{narrow\infty}(p+q)^{n}=0$ .

$\square$Now we show the results (3), (4). In the remainder of this section we fix one rational

numbersuch that $0<p<1$ and denote $1-p$ by . Moreover, we simply write $\pi(u)$

$p$

$q$

instead of $\pi_{p}(u)(=\pi_{1-p,p}(u))$ .
We define “the interval represented by a word
sents the unit interval $(0,1)$ . If a word

$u$

$u$

’

as follows. The empty word

represents an interval $(s,t)$ , then$uO$$\lambda$

repre-

represents theinterval $(s, s+q(t-s))$ and $u1$ represents the interval $(s+q(t-s), t)$ . It is obvious thatthe size $t-s$ of the interval $(s, t)$ represented by a wordfrom$\Sigma^{*}$

to

$Q$

such that the interval represented byis defined inductively by$\tau(\lambda)=0,$

that if $|u|=|u’|$ andis greater than$\tau(u’)$

$u’$

$u$

$u$

is $\pi(u)$ . Let

be the functionis $(\tau(u), \tau(u)+\pi(u))$ . This function$\tau(uO)=\tau(u),$ $\tau(u1)=\tau(u)+\pi(u)q$$u$$\tau$$\tau$. It is easy to showby one as a binary number then $\tau(u)+\pi(u)=$. We call a number in the unit interval $(0,1)$ p-rational if there exists a word such
$u$

$r$

that $r=\tau(u)$ , and p-irrational otherwise. We call a subinterval $(s, t)$ of $(0,1)$ a p-interval
if it is the interval represented by some word . It is well-known that any subinterval $(s, t)$$u$of size $d(=t-s)$ of the unit interval $(0,1)$ contains a 1/2-interval (a (binary interval”) ofsize at least $d/4$ . This fact is used to prove $2^{-H(x)}\sim>P(x)$ . We show a similar result for
p-intervals.

Lemma 1 Any subinterval $of$ size$\min\{q,p\}$of $(0,1)$ contains a p-interval of size at least $(d/2)$ .

.

Proof (an outline).
$0<s$ and $s,$$(s, t)$$d$$t$

Let $(s, t)$ be a subinterval of sizeare p-irrationals. Let. There is a word

$u’$

$u$

$\tau(u)$is in the intervalsuch that $u=u’1$ . At least one of $t-\tau(u),$ $\tau(u)-s$ is at$h$be the value such that $\tau(u)+\pi(u0^{h})\geq t$ and. Then the p-interval $(\tau(u0^{h+1}), \tau(u0^{h+1})+\pi(u0^{h+1}))$ satisfies thecondition. If $\tau(u)-s\geq d/2$ then let$s$of $(0,1)$ . We may assume thatbe the shortest word such thatleast $d/2$ . If $t-\tau(u)\geq d/2$ then let$\tau(u)+\pi(u0^{h+1})<t$

$d$

$h$

be the value such that $\tau(u’01^{h})\leq s,$ $\tau(u’01^{h+1})>$. Then the p-interval $(\tau(u’01^{h+1}), \tau(u’01^{h+1})+\pi(u’01^{h+1}))$ satisfies the condition.

$\square$32
Theorem 10 If

is a rational number such that $0<p<1$ then there is a $\omega nstantc$ such$p$that $H_{p}(x)\leq-\log P(x)+c$ for any .
$x$

It is obvious that $P_{p}(x)$ is semicomputable. We show that there exists

Proof (an outline).

a constant $c(>0)$ such that $P(x)\leq cP_{p}(x)$ for any .
$x$

Let $X$ be the recursively enumerable set $\{(x, m) | x\in\Sigma^{*}, m\in N, 2^{-m}<P(x)/2\}$and let$(x_{0}, m_{0}),$$(x_{1}, m_{1}),$algorithm. We have$(x_{2}, m_{2}),$$\Sigma_{i=0}^{\infty}2^{-m:}\leq 1$. $..+2^{-m;}$ ) is a subinterval of size$\ldots$

be the enumeration of all elements of $X$ by someand hence the interval $(2^{-m_{0}}+\ldots+2^{-m_{i-1}},2^{-m_{0}}+$of the unit interval $(0,1)$ for each $i\geq 0$ . Let$z$;be (the leftmost of) the largest p-interval contained in this interval. Let this p-interval$z$;be represented by a word$(2^{-m_{i}}/2) \min\{q,p\}$. Letthen $\phi_{A}(u)=x:$ , and$\{u_{0}, u_{1}, \ldots\}$

Let

$x$

$u_{i}$$A$$\phi_{A}(u)$and hence$A$$2^{-m:}$. By Lemma 1, the size$\pi_{p}(u_{*}\cdot)$of the p-interval . is at least$z_{*}$

be the algorithm such that if there exists

is undefined otherwise. The domain ofis prefix-free. Let

$h$

$i$

such that $u=u_{i}$is the prefix-free set$\phi_{A}$be one of its codes.

be a word. We have $2^{-\lceil-\log P(x)\rceil-2}<P(x)/2$ . Hence $(x, \lceil-\log P(x)\rceil+2)$ is in $X$ .

Let $(x;, m_{i})$ be this element. Then we have $\phi_{A_{U}}(hu:)=\phi_{A}(u;)=x_{i}=x$ , and hence $H_{p}(x)$$\leq|hu;|_{p}=-\log\pi(hu_{i})=-\log\pi(h)-\log\pi(u_{i})\leq-\log\pi(h)+m_{i}+1$$\leq-\log\pi(h)+4$ –log(min{q, $p\}$ ) $-\log P(x)$log(min{q,$p\}$–log(min{q,

$p\}$

)

. Denoting the constant $-\log\pi(h)+4-$) by , we have $H_{p}(x)\leq-\log P(x)+c$ .

$\square$$c$

The proofs of the following two corollaries are easy if we note that$2^{-H_{p}(x)}$is semicom-

putable and that $P_{p}(x)\geq 2^{-H_{p}(x)}$ .
Corollary 2 If$p$

is a rational number such that $0<p<1_{f}$ then$P_{p}(x)$is an a priori

measure.
Corollary 3 If$p$is a rational number such that $0<p<1$ , then there exists a constantsuch that $|H(x)-H_{p}(x)|\leq c$ for any .
$x$

$c$

33
7 One Condition for Semicomputable Strongly Malign Measures
to be a Priori
In this section we show one condition for measures to be a priori under the assumption thatthey are semicomutable and strongly malign. We expect such a condition to be weaker

than the conditions for the case where no assumption on the measures is made.
We call a function
word

$s,$

from

$F$

$\Sigma^{*}$

tofeasible if it is semicomputable, $F(s)\geq 0$ for any$R$for any prefix-free set$F(L)\leq 1$$L$, and there exists a prefix-freethat the measure $\mu(x)$ defined by $\mu(x)=\Sigma.$ { $F(s)$ I$\pi_{p}$$\phi_{A}(s)=x$$al$gorithm$A$such} is a priori. The function

is an example of feasible functions by Corollary 2. Especially the function $F(s)=2^{-|s|}$is feasible. For a measure , let$\mu$

Theorem 11 Let$F$$\rho_{\mu}(s)$denote inf,

be a feasible function and$\in\Sigma^{*}\mu(sy)/\mu(y)$

$\mu$

.

be a semicomputable strongly malignmeasure. Then the following two conditions are equivalent.
(1)

is an a priori measure.

$\mu$(2) For any recursively enumerable prefix-free set

that $F(s)\leq c\rho_{\mu}(s)$ for any
Proof of (1)an enumeration$L,$ $m\in(an outline)$\Rightarrow(2)$$(s_{0}, m_{0}),$

in

Let

$(s_{1}, m_{1}),$$2^{-m}<F(s)/2$

N,$

$s$

$\ldots$

$L$

$L$

$L$

there exists a constant $c(>0)$ such.
be a recursively enumerable prefix-free set. Usingof the recursively enumerable set $X=\{(s, m)|s\in$}, we can show that there is a prefix-free algorithm

for any $s\in L$ there exists$u$$A_{0}$

such thatsuch that $\phi_{A_{0}}(u)=s$ and $|u|\leq-\log F(s)+5$ . Its proof issimilar to that of Theorem 10, but we use Lemma 1 with $p=1/2$ .
Let$A_{1}$

be a prefix-free algorithm such thatits codes. Then, for any $s\in L$ and any$y$$\phi_{A_{1}}(uv)=\phi_{A_{0}}(u)\phi_{A_{U}}(v)$and let$h$be one ofwe have $H(sy)\leq|h|-\log F(s)+5+H(y)$ , andhence $\mu(sy)\geq c_{1}2^{-H(\ell y)}\geq c_{1}2^{-|h|-6}F(s)2^{-H(y)}\geq c_{1}c_{2}2^{-|h|-5}F(s)\mu(y)$ for some constants$c_{1},$$c_{2}(>0)$.

Proof of (2)$\Rightarrow(1)$.

Let$A_{0}$

be a prefix-free algorithm such that the measure $\mu’(x)$ definedby $\mu’(x)=\Sigma_{s}\{F(s)|\phi_{A_{0}}(s)=x\}$ is a priori. The domain$dom(\phi_{A_{0}})$of$\phi_{A_{0}}$is a recursively

34
enumerable prefix-free set. Let $c_{1}(>0)$ be a constant such that $F(s)\leq c_{1}\rho_{\mu}(s)$ for any$s\in dom(\phi_{A_{0}})$. Let$A_{1}$

be the algorithm such that $\phi_{A_{1}}(sy)=\phi_{w}(y)$ , with $w=\phi_{A_{0}}(s)$ . By

Theorem 6 there exists a constant $c_{2}(>0)$ such that
For any algorithm

$A$

$\mu$

for any .
$x$and any word , we have$\mu(\phi_{A}^{-1}(x))\mu’(A)$This shows that$\mu(x)\geq c_{2}\mu(\phi_{A_{1}}^{-1}(x))$

$x$

$=$

$\mu(\{y|y\in\Sigma^{*}, \phi_{A}(y)=x\})\Sigma.\{F(s)|\phi_{A_{0}}(s)=A\}$$\leq$$\Sigma_{*,y}\{\mu(y)F(s)|s\in dom(\phi_{A_{0}}), \phi_{A_{1}}(sy)=x\}$$\leq$$\Sigma_{*)y}\{c_{1}\mu(sy)|s\in dom(\phi_{A_{0}}), \phi_{A_{1}}(sy)=x\}$$\leq$$c_{1}\mu(\phi_{A_{1}}^{-1}(x))$$\leq$$c_{1}(1/c_{2})\mu(x)$is a priori by Theorem 7.

.
口

Refere nces
1. M. Blum: A machine-independent theory of the complexity of recursive functions. J.

ACM 14, 322-336 (1967)

2. M. Li, P.M.B. Vit\’anyi: A theory of learning simple concepts under simple distributions
and average case complexity for the universal distribution. In: Proc. of the 30th FOCS,

1989, pp.34-39

3. M. Li, P.M.B. Vit\’anyi: Kolmogorov complexity and its applications. In: J. van Leeuwen(ed.): Handbook of Theoretical Computer Science, Vol.

$A$

, Chap. IV. Elsevier and MIT

Press 1990, pp.187-254

4. P.B. Miltersen: The complexity of malign ensembles. In: Proc. of the 6th SICT, 1991,
pp.

$16\not\subset 171$