Perhaps I have made the same mistake as you, and was thinking about the practical but non-generalized way the second law of thermodynamics is usually taught, which includes concepts like "the system will be in this state". The only part of your statement that is still probabilistic is "entropy will not decrease". That's not really true; it probably won't decrease.
>neither of which gives a prediction
"entropy will not decrease" is a prediction. It is possible (albeit overwhelmingly unlikely over large time scales) that this prediction is sometimes false.
The markov/IT version of the 2nd law is a statement about macrostate entropy (taking the entire microstate ensemble for each macrostate), and in that sense it is not probabilistic. See the Cover&Thomas reference I gave earlier for the exact definition. It is indeed different than how it is usually taught in physics, in which the microstates are differentiated.
I guess we both need to be more careful about mathematical definitions in the future ...
I did not remember the exact statement when I posted earlier, but here it is: the statement of the (markov) 2nd law of thermodynamics is also a statement about the sample space: It says that in expectation (over the ensemble) the relative entropy decreases towards that of stationary distribution (which in most systems is the highest entropy distribution possible in that system, thus absolute entropy is non decreasing). That is, unless the system starts at a state with a higher entropy than that of the stationary distribution, entropy will not decrease.
Both are mathematical statements, consequences of pure mathematics, neither of which gives a prediction - they both give ensemble averages, and both are both internally perfectly correct and consistent. See Cover & Thomas, 2nd Edition, Jul 2006, pg 81, section 4.4 - entropy rate of markov processes. Unless, of course, you are referring to a different version of the uncertainty principle which I am not familiar with.