Is the second law of Thermodynamics an immense tautology? Let's imagine for a second a system that is changing constantly from one microstate to another one. It could be a given volume of a gas with its atoms moving and bouncing around, or a deck of cards being constantly shuffled by a monkey. If the starting microstate belongs to a macrostate with very few microstates, chances are that in the next step the system will be in a macrostate with more microstates in it. There is nothing mysterious about this, it is simply a matter of probabilities and how we define them. 
Now we have the second law of thermodynamics, that says that entropy always increases. It could have been reformulated like: a system that is permanently visiting different states, will spend more time in those which have a higher probability of being visited. Things more probable occur more times. And, since we define probabilities in terms of frequency:
Are not we simply saying that things more likely to occur, occur more times? Isn't it true then, that the second law is simply an immense tautology?
 A: 
Are not we simply saying that things more likely to occur, occur more times? Isn't it then, that the second law is simply an inmense tautology?

No, this argument doesn't suffice to prove the second law. This argument only proves that thermal fluctuations away from equilibrum should be rare and short-lived. That's a statement that doesn't have anything to do with an arrow of time, whereas the second law incorporates an arrow of time. This question deals with how you get an arrow of time.
A: 
Now we have the second law of thermodynamics, that says that entropy always increases.

Second law does not say exactly that. It has more formulations, some of which use the concept of entropy. One such formulation is

*

*When thermally insulated system changes its state from one equilibrium state to another, its entropy cannot decrease.

This statement is very different from the sloppy version "entropy always increases" one often encounters.

It could have been reformulated like: a system that is permanently visiting different states, will spend more time in those which have a higher probability of being visited.

That is not necessarily true. System can visit state $o$ million times in a second and state $r$ only once in that same second, but how long does it stay in those states is another thing.

Things more probable occur more times.
And, since we define probabilities in terms of frequency:

There are other ways to understand the concept of probability, for example the Bayesian way.

Isn't it true then, that the second law is simply an immense tautology?

Tautology is a name for a statement that is true for all variable inputs and its truth value does not depend on the reality, only on the form of the statement itself.
In physics we do not encounter tautologies, because it is not about language or form of statements, but about Nature. It works with empirical statements. Second law is an empirical law. It may be derived in probabilistic sense from mechanics (with certain assumptions), but it is not a tautology.
