I think your "correct" bozo sort example from earlier shows that there is a finite number of states (all of the permutations of the input array), just an unbounded number of state transitions.

I think for something like this, you could do asymptotic analysis of the expected run-time. Assuming all elements are distinct, there are n! permutations, so each would have a 1/n! chance of being selected each iteration. (But it's rather late, and this is a poor medium for discussing math, and someone has probably already done this, so I'm not going to go any further.)