Is the increase of entropy a theorem? Let us consider an isolated system of $N$ particles whose motion is determined by Newtonian mechanic, over time that stretches from $-\infty$ to $+\infty$. The system is isolated, therefore the only driving forces are pair-wise interaction particles, which are assumed to be non-dissipative. Therefore, energy, momentum, and angular momentum are conserved. The number $N$ of particles is very very large.
Let us consider the Boltzmann entropy $S(t) = k \log \Omega(t)$, of the microstate in which the system is at time $t$. Here, $\Omega(t)$ is the number of microstates that map to the macrostate where the system is at time $t$. Please, note that the dynamics of the system is deteministic. Therefore, given some initial conditions, the function $S(t)$ is completely deterministic.
Then, I expect that there is some theorem which states, that, for the exceedingly majority of initial conditions, the following inequality holds:
$$
\frac{dS}{dt} > 0, \forall t \in (-\infty, \infty)
$$
in particular, I would expect that the fraction of initial conditions for which such an inequality holds would tend to 1 as $N \rightarrow \infty$. Such a theorem would imply that irreversible processes do emerge from reversible microscopic dynamics.
However, after searching in every possible textbook I could possibly put my hands on, I have not found such a theorem.
Rather, I have found the following:

*

*For a sufficiently large number of particles, the exceedingly high majority of microstates maps onto the so-called equilibrium state. It is proved that such a macrostate corresponds to the highest possible value of the entropy S. Therefore, when I combine this with the ergodic hypothesis, I conclude that the system will spend an exceedingly high fraction of its time in as state with maximal entropy (up to insignificant fluctuations). However, this does not prove that the inequality $dS/dt > 0, \forall t \in (-\infty, \infty)$. holds for an exceedingly high fraction of the initial conditions.


*I have found some simple system in which it is shown that if I start from a low entropy state, the system will evolve onto a state with higher entropy with exceedingly high probability (in the order $1-10^{10^{20}}$). The most classical example is a box containing $N$ balls which at a certain time $t$ all balls are in the same half of the box (low entropy). It is easy to prove that after a certain time all balls will occupy the entire volume of the box (high entropy), and so they will stay for an exceedingly long time (in the order of $10^{10^{20}}$
However, if I take that very same set of low entropy initial conditions, and I let the system evolve back in time, I find that with exceedingly high probability the system was in a high entropy state in the past. In other words, I see no macroscopic irreversibility that emerges from microscopic reversivility.
One could consider a situation in which a barrier forces the balls to stay in the left half of the box and at $t = 0$ the barrier is magically made to disappear. It is true that if the barrier re-appears on a random subsequent instant, the probability that all balls are again in the same half of the box is extremely small. However, such a system is not isolated, it requires an external operator to remove or add the barrier. Even if no work is made when the the barrier disappears/appears, the disappearence/appearence of the barrier is not triggered by the motion of the balls.
Then, my question is: How could the law of increase of entropy be derived from first principles?
 A: I believe you are stating a version of Loschmidt's Parodox especially with your second example. Roughly how do we get the arrow of time/observed assymetry given symmetrical laws?
"...the second law of thermodynamics is thought to originate in the initial conditions in the universe"
Well, what was special about the intial conditions on the universe?
The low entropy big bang was "... a fixed initial state of a macroscopic system [which] corresponds to relatively low entropy because the coordinates of the molecules of the body are constrained. As the system evolves in the presence of dissipation, the molecular coordinates can move into larger volumes of phase space, becoming more uncertain, and thus leading to increase in entropy."
That's it. The observed assymetry of the second law requires a so-called "past hypothesis" if the underlying laws are symmetrical, which the standard model is by CPT symmetry. You could imagine the same physical laws yet with a maximally high entropy big bang. Same laws, no second law. You need a past hypothesis (together with the known laws of physics of course) for the second law and your question.
For your second example, there is no way to let the system evolve back in time, even if the laws allow for it. There was no high entropy history to the big bang by definition; there was nothing.
You cannot explain the second law without appealing to the past hypothesis. Even for probablistic allowances via the fluctuation theorem, which gives the probabiliies for an entropy reversal trajectory. The odds for witnessing such a reversal are based on how far the system is currently from equilibrium. The empirical odds are so low because the big bang was so low entropy (far from equilibrium).
There are other theories with dual arrows of time and such, but the second law alone requires a notion of initial conditons (current consensus).
