t**, this determines the following bounds of the number of models of** S:

$$\begin{array}{c}{{{\mathcal{M}}_{t}(l)\leq|M O D(S\cup\{l\})|\leq2^{n-1}-{\mathcal{N}}_{t}(l);}}\\ {{{\mathcal{M}}_{t}(\neg l)\leq|M O D(S\cup\{\neg l\})|\leq2^{n-1}-{\mathcal{N}}_{t}(\neg l).}}\end{array}$$

If for an atom a **at time** τ (a) ≤ τf Mτ(a)(a) ≥ 2 n−1 − Nτ(a)(¬a) or Mτ(a)(¬a) > 2 n−1 − Nτ(a)(a**) (26)**
then |MOD(S ∪ {a})| ≥ |MOD(S ∪ {¬a})|, E(S, a) ≥ 0.**5, and hence the**
typical atom ˆa = a or, respectively, |MOD(S ∪ {¬a})| > |MOD(S ∪ {a})|, E(S, a) < 0.5, and ˆa = ¬a. So the typical value ˆa **can be determined already**
at time τ (a**). At this time the bounds give the following approximation of** evidence:
Mτ(a)(a)
Mτ(a)(a)+2n−1−Nτ(a)(¬a)
Mτ(a)(¬a)
Mτ(a)(¬a)+2n−1−Nτ(a)(a)
. **(27)**

$$\overline{{{0}}}\leq E(S,a)\leq1-\overline{{{M}}}$$

Let τ0(a**) denote the earliest time at which one of the inequalities (26) holds.**
It can be shown that for all a ∈ Base(S) if |E(S, a) − 0.5| > 0 then τ0(a) < τf and the larger the value of |E(S, a) − 0.5| **the larger the run time gain**
(τf − τs)/(τ0(a) − τs) > **1. So an estimation of evidence and determination of**
the corresponding typical atom can be achieved by means of comparing bounds faster than by a full run of Algorithm 6.1.

## Appendix B. Relaxing Limitations

So far we have assumed that all possible worlds represented by the models of S are equiprobable and the sets W and |MOD(S)| **are finite. This appendix**
shows an example of how these limitations can be relaxed.

## B1. Probability Of Possible Worlds

In most practical cases there is no comprehensive statistical information about the world sufficient for calculating the probability p(m**) for every model** m ∈ MOD(S**). However, there often is some restricted statistics regarding** a subset of objects and events of the world. For instance, suppose the prior probabilities of certain possible worlds are known (as all the possible worlds are mutually exclusive, their mutual conditional probabilities are 0). Let M~
be the set of models of S **representing possible worlds with known probability,**
and denote p(M~ ) = Pm∈M~ p(m**). Then assuming that all possible worlds with**
unknown probabilities are equiprobable, we get

$$E(S,F)=(1-p(\bar{M}))\frac{|MOD(S\cup\{F\})-\bar{M}|}{|MOD(S)-\bar{M}|}+\sum_{m\in(MOD(S\cup\{F\})\cap\bar{M})}p(m).\tag{28}$$

If no prior probabilities of possible worlds are known such that M~ = ∅,
then expression (28) becomes identical to that of Definition **2.2. In another** special case, if prior probabilities are given for all possible worlds such that M~ = MOD(S) and p(M~ ) = 1, then the evidence E(S, F**) amounts to the**
probability p(F).