Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userStochastic processes with random contexts: a characterization, and adaptive estimators for the transition probabilities
148
0
0.0
(
0
)
Added by
Roberto Imbuzeiro Oliveira
Publication date
2013
fields
Informatics Engineering
and research's language is
English
Authors
Roberto Imbuzeiro Oliveira
Ask ChatGPT about the research
No Arabic abstract
This paper introduces the concept of random context representations for the transition probabilities of a finite-alphabet stochastic process. Processes with these representations generalize context tree processes (a.k.a. variable length Markov chains), and are proven to coincide with processes whose transition probabilities are almost surely continuous functions of the (infinite) past. This is similar to a classical result by Kalikow about continuous transition probabilities. Existence and uniqueness of a minimal random context representation are proven, and an estimator of the transition probabilities based on this representation is shown to have very good pastwise adaptativity properties. In particular, it achieves minimax performance, up to logarithmic factors, for binary renewal processes with bounded $2+gamma$ moments.
rate research
Read More
The paper deals with a certain class of random evolutions. We develop a construction that yields an invariant measure for a continuous-time Markov process with random transitions. The approach is based on a particular way of constructing the combined process, where the generator is defined as a sum of two terms: one responsible for the evolution of the environment and the second representing generators of processes with a given state of environment. (The two operators are not assumed to commute.) The presentation includes fragments of a general theory and pays a particular attention to several types of examples: (1) a queueing system with a random change of parameters (including a Jackson network and, as a special case: a single-server queue with a diffusive behavior of arrival and service rates), (2) a simple-exclusion model in presence of a special `heavy` particle, (3) a diffusion with drift-switching, and (4) a diffusion with a randomly diffusion-type varying diffusion coefficient (including a modification of the Heston random volatility model).
Finitarily Markovian processes are those processes ${X_n}_{n=-infty}^{infty}$ for which there is a finite $K$ ($K = K({X_n}_{n=-infty}^0$) such that the conditional distribution of $X_1$ given the entire past is equal to the conditional distribution of $X_1$ given only ${X_n}_{n=1-K}^0$. The least such value of $K$ is called the memory length. We give a rather complete analysis of the problems of universally estimating the least such value of $K$, both in the backward sense that we have just described and in the forward sense, where one observes successive values of ${X_n}$ for $n geq 0$ and asks for the least value $K$ such that the conditional distribution of $X_{n+1}$ given ${X_i}_{i=n-K+1}^n$ is the same as the conditional distribution of $X_{n+1}$ given ${X_i}_{i=-infty}^n$. We allow for finite or countably infinite alphabet size.
Consider a spiked random tensor obtained as a mixture of two components: noise in the form of a symmetric Gaussian $p$-tensor for $pgeq 3$ and signal in the form of a symmetric low-rank random tensor. The latter is defined as a linear combination of $k$ independent symmetric rank-one random tensors, referred to as spikes, with weights referred to as signal-to-noise ratios (SNRs). The entries of the vectors that determine the spikes are i.i.d. sampled from general probability distributions supported on bounded subsets of $mathbb{R}$. This work focuses on the problem of detecting the presence of these spikes, and establishes the phase transition of this detection problem for any fixed $k geq 1$. In particular, it shows that for a set of relatively low SNRs it is impossible to distinguish between the spiked and non-spiked Gaussian tensors. Furthermore, in the interior of the complement of this set, where at least one of the $k$ SNRs is relatively high, these two tensors are distinguishable by the likelihood ratio test. In addition, when the total number of low-rank components, $k$, of the $p$-tensor of size $N$ grows in the order $o(N^{(p-2)/4})$ as $N$ tends to infinity, the problem exhibits an analogous phase transition. This theory for spike detection is also shown to imply that recovery of the spikes by the minimum mean square error exhibits the same phase transition. The main methods used in this work arise from the study of mean field spin glass models, where the phase transition thresholds are identified as the critical inverse temperatures distinguishing the high and low-temperature regimes of the free energies. In particular, our result formulates the first full characterization of the high temperature regime for vector-valued spin glass models with independent coordinates.
Finite sample properties of random covariance-type matrices have been the subject of much research. In this paper we focus on the lower tail of such a matrix, and prove that it is subgaussian under a simple fourth moment assumption on the one-dimensional marginals of the random vectors. A similar result holds for more general sums of random positive semidefinite matrices, and the (relatively simple) proof uses a variant of the so-called PAC-Bayesian method for bounding empirical processes. We give two applications of the main result. In the first one we obtain a new finite-sample bound for ordinary least squares estimator in linear regression with random design. Our result is model-free, requires fairly weak moment assumptions and is almost optimal. Our second application is to bounding restricted eigenvalue constants of certain random ensembles with heavy tails. These constants are important in the analysis of problems in Compressed Sensing and High Dimensional Statistics, where one recovers a sparse vector from a small umber of linear measurements. Our result implies that heavy tails still allow for the fast recovery rates found in efficient methods such as the LASSO and the Dantzig selector. Along the way we strengthen, with a fairly short argument, a recent result of Rudelson and Zhou on the restricted eigenvalue property.
We prove several results concerning classifications, based on successive observations $(X_1,..., X_n)$ of an unknown stationary and ergodic process, for membership in a given class of processes, such as the class of all finite order Markov chains.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
