Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userLower bounds for moments of global scores of pairwise Markov chains
65
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Let $X_1,X_2,ldots$ and $Y_1,Y_2,ldots$ be two random sequences so that every random variable takes values in a finite set $mathbb{A}$. We consider a global similarity score $L_n:=L(X_1,ldots,X_n;Y_1,ldots,Y_n)$ that measures the homology (relatedness) of words $(X_1,ldots,X_n)$ and $(Y_1,ldots,Y_n)$. A typical example of such score is the length of the longest common subsequence. We study the order of central absolute moment $E|L_n-EL_n|^r$ in the case where two-dimensional process $(X_1,Y_1),(X_2,Y_2),ldots$ is a Markov chain on $mathbb{A}times mathbb{A}$. This is a very general model involving independent Markov chains, hidden Markov models, Markov switching models and many more. Our main result establishes a general condition that guarantees that $E|L_n-EL_n|^rasymp n^{rover 2}$. We also perform simulations indicating the validity of the condition.
rate research
Read More
Convergence rates of Markov chains have been widely studied in recent years. In particular, quantitative bounds on convergence rates have been studied in various forms by Meyn and Tweedie [Ann. Appl. Probab. 4 (1994) 981-1101], Rosenthal [J. Amer. Statist. Assoc. 90 (1995) 558-566], Roberts and Tweedie [Stochastic Process. Appl. 80 (1999) 211-229], Jones and Hobert [Statist. Sci. 16 (2001) 312-334] and Fort [Ph.D. thesis (2001) Univ. Paris VI]. In this paper, we extend a result of Rosenthal [J. Amer. Statist. Assoc. 90 (1995) 558-566] that concerns quantitative convergence rates for time-homogeneous Markov chains. Our extension allows us to consider f-total variation distance (instead of total variation) and time-inhomogeneous Markov chains. We apply our results to simulated annealing.
We consider the problem of performing inference with imprecise continuous-time hidden Markov chains, that is, imprecise continuous-time Markov chains that are augmented with random output variables whose distribution depends on the hidden state of the chain. The prefix `imprecise refers to the fact that we do not consider a classical continuous-time Markov chain, but replace it with a robust extension that allows us to represent various types of model uncertainty, using the theory of imprecise probabilities. The inference problem amounts to computing lower expectations of functions on the state-space of the chain, given observations of the output variables. We develop and investigate this problem with very few assumptions on the output variables; in particular, they can be chosen to be either discrete or continuous random variables. Our main result is a polynomial runtime algorithm to compute the lower expectation of functions on the state-space at any given time-point, given a collection of observations of the output variables.
We study the $2k$-th discrete moment of the derivative of the Riemann zeta-function at nontrivial zeros to establish sharp lower bounds for all real $k geq 0$ under the Riemann hypothesis (RH).
We prove that for every $epsilon>0$ and predicate $P:{0,1}^krightarrow {0,1}$ that supports a pairwise independent distribution, there exists an instance $mathcal{I}$ of the $mathsf{Max}P$ constraint satisfaction problem on $n$ variables such that no assignment can satisfy more than a $tfrac{|P^{-1}(1)|}{2^k}+epsilon$ fraction of $mathcal{I}$s constraints but the degree $Omega(n)$ Sum of Squares semidefinite programming hierarchy cannot certify that $mathcal{I}$ is unsatisfiable. Similar results were previously only known for weaker hierarchies.
We describe estimators $chi_n(X_0,X_1,...,X_n)$, which when applied to an unknown stationary process taking values from a countable alphabet ${cal X}$, converge almost surely to $k$ in case the process is a $k$-th order Markov chain and to infinity otherwise.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
