Valid predicates for Probability[]?

The reasons the supposedly false behavior of EvenQ have been explained nicely in (139281). Basically there are three solutions:

1) Avoid predicates which will work on symbolic inputs

Next to using Mod[ x, 2] == 0 there is a more compact form available:

Probability[ x ~ Divisible ~ 2, x \[Distributed] Range @ 10 ]

1/2

2) Modify the predicates so they will not work on symbolic inputs

This is the solution given in the thread that I have linked. For completeness:

nEvenQ[ x_?NumericQ ] := EvenQ @ x

Probability[ nEvenQ @ x, x \[Distributed] Range @ 10 ]

1/2

3) Prevent the predicates from evaluating prematurely

While in the OP Defer has been used already, a nicer solution (imo) exists using Inactivate and Activate:

Probability[ Inactivate @ EvenQ[x], x \[Distributed] Range @ 10 ]

(* 1/10 (Boole[Inactive[EvenQ][1]] + Boole[Inactive[EvenQ][2]] + 
Boole[Inactive[EvenQ][3]] + Boole[Inactive[EvenQ][4]] + 
Boole[Inactive[EvenQ][5]] + Boole[Inactive[EvenQ][6]] + 
Boole[Inactive[EvenQ][7]] + Boole[Inactive[EvenQ][8]] + 
Boole[Inactive[EvenQ][9]] + Boole[Inactive[EvenQ][10]]) *)

Activate @ %

1/2

Here's a different perspective to complement gwr's answer:

Mathematica has functions for traditional programming, and functions which represent Mathematical concepts and are suitable for symbolic computation. The line between the two is somewhat blurred. This is good for keeping things simple, but it can also be confusing. A stricter CAS would make this distinction explicit at the cost of some convenience, and would provide separate tools for these two types of uses.

"Programming functions" will evaluate immediately, just as they do in other languages. EvenQ is such a function. Generally, functions ending in Q will evaluate immediately to either True or False. Example:

EvenQ /@ {0, 1, x}
(* {True, False, False} *)

Thus it is better to think of EvenQ[x] as "x is of Integer datatype and is even". It will return False for anything that is not of the Integer datatype, which is not the same thing as an integer in the mathematical sense. E.g., EvenQ[2.0] is False because 2.0 is Real. $k\in\mathbb{Z}$ is a mathematical concept, datatypes are a programming concept.

"Mathematical functions" do not evaluate with symbolic values and can be used to represent mathematical statements. Positive is such a function. Note that even though it returns True or False, it does not have Q in the name. Example:

Positive /@ {0, 1, x}
(* {False, True, Positive[x]} *)

It can be used to represent a Mathematica statement, on which we can perform operations:

FullSimplify[Positive[x^2], Element[x, Reals] && x != 0]
(* True *)

An example of a function that blurs the line between math and programming is If. If its first argument is neither True nor False, then it does not evaluate, and can be used as a sort of substitute for Piecewise. Note though that it has a fourth argument: when specified, If will evaluate immediately.

In general, you can think of programming function as "code" that is meant to run. You can think of mathematical functions as data that can be operated on. Probability is meant to be used with mathematical functions—anything else will evaluate before Probability even has a chance to see it. That excludes anything that has a Q in the name.

---

A note about Defer: this is a function that is meant purely for displaying/formatting things in notebooks. It is not meant for evaluation control.