On Expected Truth Value of a Random Propositional Formula



Is it more probable that random propositional formula, as defined
in previous blogpost using true, nil and traditional connectives or,
and, not and -> is true or false? One would expect that it is equally
probable. Let us test this hypothesis.

(set 'random-formula
      (lambda(x)
        (if (= x 1)
            (amb true nil)
            (letn ((a (div (add (mul x 3) 4) (mul 2 (sub x 1))))
                  (r (random 0 (add 4 (mul 2 a)))))
                 
                 (cond
                    ((<= 0 r 1) (list 'not (random-formula x)))
                    ((<= 1 r 2) (list 'and (random-formula x) (random-formula x)))
                    ((<= 2 r 3) (list 'or (random-formula x) (random-formula x)))
                    ((<= 3 r 4) (list '-> (random-formula x) (random-formula x)))
                    ((<= 4 r (add 4 a)) true)           ; if a=2 then 
                    ((<= (add 4 a) r (add 4 a a)) nil))))))
                 
(set '-> (lambda(x y)(or (not x) y)))

(for (j 1 50)
  (set 'sum 0)
  (dotimes(i 100000)
    (if (eval (random-formula j)) ; power of eval
        (inc sum)))
  (println "Random formula of a length " j ". is true in " 
           (div (mul 100 sum) 100000) "% of cases"))
  
Results:  
  
Random formula of a length 1. is true in 49.855% of cases
Random formula of a length 2. is true in 52.099% of cases
Random formula of a length 3. is true in 52.636% of cases
Random formula of a length 4. is true in 53.104% of cases
Random formula of a length 5. is true in 53.224% of cases
Random formula of a length 6. is true in 53.577% of cases
Random formula of a length 7. is true in 53.339% of cases
Random formula of a length 8. is true in 53.484% of cases
Random formula of a length 9. is true in 53.513% of cases
Random formula of a length 10. is true in 53.87% of cases
Random formula of a length 11. is true in 53.889% of cases
Random formula of a length 12. is true in 53.571% of cases
Random formula of a length 13. is true in 53.917% of cases
Random formula of a length 14. is true in 53.837% of cases
Random formula of a length 15. is true in 54.14% of cases
Random formula of a length 16. is true in 53.973% of cases
Random formula of a length 17. is true in 53.811% of cases
Random formula of a length 18. is true in 54.059% of cases
Random formula of a length 19. is true in 53.929% of cases
Random formula of a length 20. is true in 53.98% of cases
Random formula of a length 21. is true in 53.818% of cases
Random formula of a length 22. is true in 54.109% of cases
Random formula of a length 23. is true in 53.999% of cases
Random formula of a length 24. is true in 54.001% of cases
Random formula of a length 25. is true in 54.095% of cases
Random formula of a length 26. is true in 54.03% of cases
Random formula of a length 27. is true in 54.215% of cases
Random formula of a length 28. is true in 54.048% of cases
Random formula of a length 29. is true in 54.12% of cases
Random formula of a length 30. is true in 53.972% of cases
Random formula of a length 31. is true in 53.752% of cases
Random formula of a length 32. is true in 54.154% of cases
Random formula of a length 33. is true in 54.229% of cases
Random formula of a length 34. is true in 54.159% of cases
Random formula of a length 35. is true in 53.972% of cases
Random formula of a length 36. is true in 54.063% of cases
Random formula of a length 37. is true in 53.926% of cases
Random formula of a length 38. is true in 53.899% of cases
Random formula of a length 39. is true in 54.078% of cases
Random formula of a length 40. is true in 54.247% of cases
Random formula of a length 41. is true in 54.14% of cases
Random formula of a length 42. is true in 54.036% of cases
Random formula of a length 43. is true in 54.05% of cases
Random formula of a length 44. is true in 54.16% of cases
Random formula of a length 45. is true in 53.964% of cases
Random formula of a length 46. is true in 53.988% of cases
Random formula of a length 47. is true in 54.075% of cases
Random formula of a length 48. is true in 54% of cases
Random formula of a length 49. is true in 53.975% of cases
Random formula of a length 50. is true in 53.954% of cases

Why probability that random formula is true is consistently greater
than 50%? Because of asymmetry of traditionally basic logical connectives
and, or and ->. These are the truth tables (0 = nil, 1 = true):

 x y (or x y)        x y (and x y)       x y (-> x y)
 ------------        -------------       ------------
 0 0   0             0 0   0             0 0  1
 0 1   1             0 1   0             0 1  1
 1 0   1             1 0   0             1 0  0
 1 1   1             1 1   1             1 1  1 

Look at the last column in each of these definitions - there are  
total seven 1's and five 0's.


If formula of a given length, say l has connective or, and or
-> on a top level, the probability that it is true should be greater
than probability that it is false.


On the other side, if formula of the same length l has connective not
on the top level, then it is more probable that formula is false -
because not is applied on a random formula of a length l-1 which
is, supposedly more probable to be true. However, there is less of
formulas of length l-1 than formulas of a length l, so formulas
starting with not cannot compensate for formulas starting with
and, or and ->.


We proved that random formula of the length l is probably true -
if formula of the length l-1 is probably true. To complete the proof,
we must prove that random formula is probably true for some base
case:


1: true, false => 1 true, 1 false
2: (not true), (not false) => 1 true, 1 false
3: (or false false), (or false true), (or true false), (or true true),
   (and false false), (and false true), (and true false), (and true true),
   (-> false false), (-> false true), (-> true false), (-> true true)
   (not (not true)), (not (not false)) => 8 true, 6 false.


If formula of a length 3 is probably true, then formula of the
length 4 is probably true and so on ...


Note that our random formulas have no fixed length - but they have
fixed average length, and it is enough that this asymmetry breaks
through.





---

No comments:

Post a Comment