Estimation in slow mixing, long memory channels
Preprint
Abstract
We consider estimation of binary channels with memory where the transition probabilities (\emph{channel parameters}) from the input to output are determined by prior outputs (\emph{state of the channel}). While the channel is unknown, we observe the joint input/output process of the channel---we have $n$ \iid input bits and their corresponding outputs. Motivated by applications related to the backplane channel, we want to estimate the channel parameters as well as the stationary probabilities for each state. Two distinct problems that complicate estimation in this setting are (i) long memory, and (ii) \emph{slow mixing} which could happen even with only one bit of memory. In this setting, any consistent estimator can only converge pointwise over the model class. Namely,given any estimator and any sample size $n$, the underlying model could be such that the estimator performs poorly on a sample of size $n$ with high probability. But can we look at a length-$n$ sample and identify \emph{if} an estimate is likely to be accurate? Since the memory is unknown a-priori, a natural approach, known to be consistent, is to use a potentially coarser model with memory $k_n=\alpha_n\log n$ with $\alpha_n$ being a function of $n$ that grows $\cO_n(1)$. While effective asymptotically, the situation is quite different when we want answers with a length-$n$ sample, rather than just consistency. Combining results on universal compression and Aldous' coupling arguments, we obtain sufficient conditions (even for slow mixing models) to identify when naive estimates of the (i) channel parameters and (ii) stationary probabilities of the channel states are accurate, and bound their deviations from true values.
Keywords
All Related Versions
This publication has 15 references indexed in Scilit:
- Optimization of Information Rate Upper and Lower Bounds for Channels With MemoryIEEE Transactions on Information Theory, 2009
- Markov Processes Asymptotically Achieve the Capacity of Finite-State Intersymbol Interference ChannelsIEEE Transactions on Information Theory, 2008
- Exponential inequalities for VLMC empirical treesESAIM: Probability and Statistics, 2008
- Consistency of the Unlimited BIC Context Tree EstimatorIEEE Transactions on Information Theory, 2006
- Simulation-Based Computation of Information Rates for Channels With MemoryIEEE Transactions on Information Theory, 2006
- Context tree estimation for not necessarily finite memory processes, via BIC and MDLIEEE Transactions on Information Theory, 2006
- Large-scale typicality of Markov sample paths and consistency of MDL order estimatorsIEEE Transactions on Information Theory, 2002
- The context-tree weighting method: basic propertiesIEEE Transactions on Information Theory, 1995
- A universal data compression systemIEEE Transactions on Information Theory, 1983
- Random walks on finite groups and rapidly mixing markov chains1983