However, you wouldn't output the whole thing (or you instantly leak the state), and I think in that case you don't get an automatic useful guarantee about the period anymore: For some seeds you could have the whole 0..2^64-1 counter span just output a few repeating values (or even a constant).
In that case the 'state' has a long period, true, but the output doesn't. If instead you use a construction where the output is guaranteed to have a known (large) period, you can follow that up with whatever permutation you want, but to preserve the period all of the permutation must be output.
I'm assuming the state-mixing function is a permutation (i.e. the counter affects the whole state in a reversible way), but it is not required that the whole state is outputted.
> However, you wouldn't output the whole thing (or you instantly leak the state), and I think in that case you don't get an automatic useful guarantee about the period anymore: For some seeds you could have the whole 0..2^64-1 counter span just output a few repeating values (or even a constant).
The counter will always have the full period of 2^N (assuming N-bit counter), regardless of how it is initialized (i.e. regardless of seeding), as long as it is a simple "i = (i + 1) mod 2^N" counter.
What this does is to effectively change the (presumably fixed) state permutation function: instead of using a fixed one, you're applying a repeating sequence of 2^N slightly different state permutation functions, which ensures that the period of the state should be at least as large as that (and probably much larger).
Assuming the chosen state permutation function is reasonable (and does indeed mix the counter effectively), truncating the state to provide output should not lead to short cycles: if it does, then your permutation is probably not reasonable as primitive for a PRNG (i.e. you have worse problems in your generator than "small period").
For more information on the use of counters to ensure lower bounds on the periods of stream ciphers and PRNG, take a look at Rabbit [1] (or, in general, at the concept of "counter-assisted stream ciphers" [2]).
The nice property that LFSR+non-linear-permutation-on-output schemes have is that by construction they give a guaranteed known gigantic period.
The counter and truncated permutation will do so if the permutation is reasonable. If lots of cpu time is allowed then I think it's likely that people will manage to select reasonable permutations. ... but when trying to shave off ever last cycle (as is the case for the RNGs discussed in this thread) it would be good to have a more concrete definition of reasonable.
I'm using "reasonable" here, because if the state-update function is an extremely weak and far-from-random permutation, like the identity, then the least-significant bits of the state will obviously display short cycles and, then, if your output function is also weak (e.g. simple truncation of most-significant bits), you may have short cycles in your output.
But, again, in such a case, you have a much bigger problem than "lack of lower bound on cycle length": your state-update function is not mixing your state, so you are 100% reliant on your output function to mix the state+counter. Also, if you go ahead and remove the counter, then you get a PRNG that always outputs the same thing (regardless of the chosen output function): clearly, you haven't picked a "reasonable" state-update function.
In a nutshell: if you don't actually have a PRNG (because both your state-update and output functions are trivially weak and non-mixing), then adding a counter won't magically turn it into a PRNG.
> The nice property that LFSR+non-linear-permutation-on-output schemes have is that by construction they give a guaranteed known gigantic period.
...and you get that guarantee from the fact that a LFSR is a counter. So you're just reinforcing what I said, and what is stated in the paper I linked to: adding a counter to a (stateful or stateless) nonlinear function is the best/easiest way to ensure a lower bound on the cycle length of a PRNG of arbitrary structure.
> If lots of cpu time is allowed then I think it's likely that people will manage to select reasonable permutations. ... but when trying to shave off ever last cycle (as is the case for the RNGs discussed in this thread) it would be good to have a more concrete definition of reasonable.
The chosen permutation does not have to have any special properties other than the ones that are already required for any usual PRNG (things like "changing a bit in the input should change each output bit with a probability of about 1/2").
The concrete definition of a "reasonable" PRNG is: either the state-update function or the output function of the PRNG must effectively mix the state (or both). Adding a counter will not turn an "unreasonable" PRNG into a "reasonable" PRNG: it will only take a "reasonable" PRNG and turn it into a "reasonable PRNG with lower bound on its cycle lengths".
If 'very small' is small enough (such as 2 or 5) then those seeds will cause some ordinary uses to fail badly in obvious ways. If bad seeds are common enough (say 1 in 2^64) then you could actually see rare failures in production.
(Cryptographic RNGs tend to avoid this risk just by having a pretty gigantic and well mixed state, so any bad seed-- if one exists-- would be extremely unlikely to be hit. They also usually have structures that are 'close' to permutations which makes it hard for them to have small periods.)
For insecure small state RNGs the risk of small periods makes it useful to build RNGs based on structures that make it easy to know the period. Unfortunately, those same structures also tend to do things like make the RNG efficiently invertible.
Invertibility itself shouldn't be a problem since these sorts of non-cryptographic RNGs should never be used where security is a factor, but the existence of invertibility has a bad smell even when you're just concerned that the pattern of the RNG may trigger pathological behavior in the underlying system (as the structure of LCGs often does).
If it's not obvious to you why invertibility (or predictability in general) is a bad smell, think of it this way: Using the inversion I can create a randomness test that the RNG will fail (by recovering the state and checking it) and I can create an application that will fail using it. The application would be contrived, for sure, but it would exist. If we don't know how to predict the RNG then we also probably don't know how to create an application that will fail with it, even a contrived one (assuming the RNG otherwise has good statistical properties).
Though this only goes so far, because with a small state every RNG is going to be invertible (up to seeds with equal output) by an exhaustive test.