  We describe a family of conservative statistical tests for independence of
two autocorrelated time series. The series may take values in any sets, and one
of them must be stationary. A user-specified function quantifying the
association of a segment of the two series is compared to an ensemble obtained
by time-shifting the stationary series -N to N steps. If the series are
independent, the unshifted value is in the top m shifted values with
probability at most m/(N+1). For large N, the probability approaches m/(2N+1).
A conservative test rejects independence at significance {\alpha} if the
unshifted value is in the top {\alpha}(N+1), and has half the power of an
approximate test valid in the large N limit. We illustrate this framework with
a test for correlation of autocorrelated categorical time series.
