There appears to be a semantic problem with this (I am not a physicist, so please bear with me).
If "the arrow of time" is re-defined to just mean "superficial appearance of decreases in entropy to some observer", then I agree with Shalizi and I also believe the result of his paper is not a 'paradox' and doesn't cast any doubt on validity of Bayesian methods. In local situations, a system might be sufficiently "closed" such that to the observer it looks like the system is spontaneously becoming more complex... that is, the degree of ignorance in the observer's mind might decrease quickly.
But, consistent with the physical laws, somewhere within the observer-system metasystem, that entropy is being accounted for. In order to zoom out and re-apply Shalizi's idea to the meta-system, you have to start talking about some new meta-observer whose states of ignorance are only relevant to the first observer-system metasystem.
So to me, it seems like if your approach accurately describes Shalizi's argument, then all he is doing is redefining "arrow of time" such that he gets the result he wants... but no one has to care about that version of "arrow of time" nor believe that it corresponds to the same "arrow of time" that is discussed in almost all discourse on thermodynamics. And even less should anyone think this is genuine reason to be skeptical of fully Bayesian updating.
There is no re-definition of "arrow of time" going on here. Shalizi is using the phrase in its standard thermodynamic sense, describing the fact that a number of macroscopic processes are thermodynamically irreversible.
Consider a specific example: two boxes of gas initially at different temperatures are brought into contact through a diathermal barrier. I check the temperature of these gases using a thermometer periodically. I observe that over time temperature difference vanishes. The gases spontaneously equilibriate.
What would you say about wha...
Link to the Question
I haven't gotten an answer on this yet and I set up a bounty; I figured I'd link it here too in case any stats/physics people care to take a crack at it.