Exponential bounds for convergence of entropy rate approximations in hidden Markov models satisfying a path-mergeability condition

A hidden Markov model (HMM) is said to have path-mergeable states   if for any two states i,j$i,j$ there exist a word w$w$ and state k$k$ such that it is possible to transition from both i$i$ and j$j$ to k$k$ while emitting w$w$. We show that for a finite HMM with path-mergeable states the block estimates of the entropy rate converge exponentially fast. We also show that the path-mergeability property is asymptotically typical in the space of HMM topologies and easily testable.     

[1, 2]-sets in graphs

A subset S⊆V$S\subseteq V$ in a graph G=(V,E)$G=(V,E)$ is a [j,k]$[j,k]$-set if, for every vertex v∈V?S$v\in V?S$, j≤|N(v)∩S|≤k$j\le |N\left(v\right)\cap S|\le k$ for non-negative integers j$j$ and k$k$, that is, every vertex v∈V?S$v\in V?S$ is adjacent to at least j$j$ but not more than k$k$ vertices in S$S$. In this paper, we focus on small j$j$ and k$k$, and relate the concept of [j,k]$[j,k]$-sets to a host of other concepts in domination theory, including perfect domination, efficient domination, nearly perfect sets, 2-packings, and k$k$-dependent sets. We also determine bounds on the cardinality of minimum [1, 2]-sets, and investigate extremal graphs achieving these bounds. This study has implications for restrained domination as well. Using a result for [1, 3]-sets, we show that, for any grid graph G$G$, the restrained domination number is equal to the domination number of G$G$.     

Revenue in contests with many participants

We show that in a contest with a single prize, the expected effort made by the k$k$th highest valuation participant bounds the sum of the expected efforts made by all of the participants with valuations less than the k$k$th highest valuations. We also show that in the limit case of a contest with m$m$ prizes, the expected effort made by the k$k$th highest valuation participant when the bidders are risk-neutral is greater than the expected effort in the risk-averse case.     

Strongly quasi-Hamiltonian-connected semicomplete multipartite digraphs

A semicomplete multipartite or semicomplete c$c$-partite digraph D$D$ is a biorientation of a c$c$-partite graph. A semicomplete multipartite digraph D$D$ is called strongly quasi-Hamiltonian-connected, if for any two distinct vertices x$x$ and y$y$ of D$D$, there is a path P$P$ from x$x$ to y$y$ such that P$P$ contains at least one vertex from each partite set of D$D$.     

On probabilistic results for the discrepancy of a hybrid-Monte Carlo sequence

In many applications it has been observed that hybrid-Monte Carlo sequences perform better than Monte Carlo and quasi-Monte Carlo sequences, especially in difficult problems. For a mixed s$s$-dimensional sequence m$m$, whose elements are vectors obtained by concatenating d$d$-dimensional vectors from a low-discrepancy sequence q$q$ with (s−d)$(s-d)$-dimensional random vectors, probabilistic upper bounds for its star discrepancy have been provided. In a paper of G. Ökten, B. Tuffin and V. Burago [G. Ökten, B. Tuffin, V. Burago, J. Complexity 22 (2006), 435–458] it was shown that for arbitrary ε>0$\epsilon >0$ the difference of the star discrepancies of the first N$N$ points of m$m$ and q$q$ is bounded by ε$\epsilon$ with probability at least 1−2exp(−ε²N/2)$1-2exp(-{\epsilon }^{2}N/2)$ for N$N$ sufficiently large. The authors did not study how large N$N$ actually has to be and if and how this actually depends on the parameters s$s$ and ε$\epsilon$. In this note we derive a lower bound for N$N$, which significantly depends on s$s$ and ε$\epsilon$. Furthermore, we provide a probabilistic bound for the difference of the star discrepancies of the first N$N$ points of m$m$ and q$q$, which holds without any restrictions on N$N$. In this sense it improves on the bound of Ökten, Tuffin and Burago and is more helpful in practice, especially for small sample sizes N$N$. We compare this bound to other known bounds.     

Smale’s point estimate theory for Newton’s method on Lie groups

We introduce the notion of the (one-parameter subgroup) γ$\gamma$-condition for a map f$f$ from a Lie group to its Lie algebra and establish α$\alpha$-theory and γ$\gamma$-theory for Newton’s method for a map f$f$ satisfying this condition. Applications to analytic maps are provided, and Smale’s α$\alpha$-theory and γ$\gamma$-theory are extended and developed. Examples arising from initial value problems on Lie group are presented to illustrate applications of our results.     

Quandle cocycles from invariant theory

Let G$G$ be a group. Any G$G$-module M$M$ has an algebraic structure called a G$G$-family of Alexander quandles. Given a 2-cocycle of a cohomology associated with this G$G$-family, topological invariants of (handlebody) knots in the 3-sphere are defined. We develop a simple algorithm to algebraically construct n$n$-cocycles of this G$G$-family from G$G$-invariant group n$n$-cocycles of the abelian group M$M$. We present many examples of 2-cocycles of these G$G$-families using facts from (modular) invariant theory.     

On topological entropy of commuting tree maps

Let T$T$ be a tree with s$s$ ends and f,g$f,g$ be continuous maps from T$T$ to T$T$ with f°g=g°f$f°g=g°f$. In this note we show that if there exists a positive integer m≥2$m\ge 2$ such that gcd(m,l)=1$gcd(m,l)=1$ for any 2≤l≤s$2\le l\le s$ and f,g$f,g$ share a periodic point which is a km$km$-periodic point of f$f$ for some positive integer k$k$, then the topological entropy of f°g$f°g$ is positive.     

Fixed point theorem for generalized Φ -pseudocontractive mappings

Let E$E$ be a real Banach space, C$C$ be a nonempty closed convex subset of E$E$ and T:C→C$T:C\to C$ be a continuous generalized Φ$\Phi$-pseudocontractive mapping. It is proved that T$T$ has a unique fixed point in C$C$.     

Hopf subalgebras and tensor powers of generalized permutation modules

By means of a certain module V$V$ and its tensor powers in a finite tensor category, we study a question of whether the depth of a Hopf subalgebra R$R$ of a finite-dimensional Hopf algebra H$H$ is finite. The module V$V$ is the counit representation induced from R$R$ to H$H$, which is then a generalized permutation module, as well as a module coalgebra. We show that if in the subalgebra pair either Hopf algebra has finite representation type, or V$V$ is either semisimple with R^∗$R^{\ast }$ pointed, projective, or its tensor powers satisfy a Burnside ring formula over a finite set of Hopf subalgebras including R$R$, then the depth of R$R$ in H$H$ is finite. One assigns a nonnegative integer depth to V$V$, or any other H$H$-module, by comparing the truncated tensor algebras of V$V$ in a finite tensor category and so obtains upper and lower bounds for depth of a Hopf subalgebra. For example, a relative Hopf restricted module has depth 1, and a permutation module of a corefree subgroup has depth less than the number of values of its character.     

Conditional residual lifetimes of coherent systems

In this paper, we derive mixture representations for the reliability function of the conditional residual lifetime of a coherent system with n$n$ independent and identically distributed (i.i.d.) components under the condition that at least j$j$ and at most k−1$k-1$ (j<k$j<k$) components have failed by time t$t$. Based on these mixture representations, we then discuss stochastic comparisons of the conditional residual lifetimes of two coherent systems with independent and identical components.     

Oscillation of harmonic functions for subordinate Brownian motion and its applications

In this paper, we establish an oscillation estimate of nonnegative harmonic functions for a pure-jump subordinate Brownian motion. The infinitesimal generator of such subordinate Brownian motion is an integro-differential operator. As an application, we give a probabilistic proof of the following form of relative Fatou theorem for such subordinate Brownian motion X$X$ in a bounded κ$\kappa$-fat open set; if u$u$ is a positive harmonic function with respect to X$X$ in a bounded κ$\kappa$-fat open set D$D$ and h$h$ is a positive harmonic function in D$D$ vanishing on D^c$D^c$, then the non-tangential limit of u/h$u/h$ exists almost everywhere with respect to the Martin-representing measure of h$h$.     

Weak convergence of censored and reflected stable processes

It is shown that if a sequence of open n$n$-sets _Dk$D_k$ increases to an open n$n$-set D$D$ then reflected stable processes in _Dk$D_k$ converge weakly to the reflected stable process in D$D$ for every starting point x$x$ in D$D$. The same result holds for censored α$\alpha$-stable processes for every x$x$ in D$D$ if D$D$ and _Dk$D_k$ satisfy the uniform Hardy inequality. Using the method in the proof of the above results, we also prove the weak convergence of reflected Brownian motions in unbounded domains.     

Tournaments associated with multigraphs and a theorem of Hakimi

A tournament of order n$n$ is usually considered as an orientation of the complete graph _Kn$K_n$. In this note, we consider a more general definition of a tournament that we call aC$C$-tournament, where C$C$ is the adjacency matrix of a multigraph G$G$, and a C$C$-tournament is an orientation of G$G$. The score vector of a C$C$-tournament is the vector of outdegrees of its vertices. In 1965 Hakimi obtained necessary and sufficient conditions for the existence of a C$C$-tournament with a prescribed score vector R$R$ and gave an algorithm to construct such a C$C$-tournament which required, however, some backtracking. We give a simpler and more transparent proof of Hakimi’s theorem, and then provide a direct construction of such a C$C$-tournament which works even for weighted graphs.     

Every point is critical

We show that, for any compact Alexandrov surface S$S$ (without boundary) and any point y$y$ in S$S$, there exists a point x$x$ in S$S$ for which y$y$ is a critical point. Moreover, we prove that uniqueness characterizes the surfaces homeomorphic to the sphere among smooth orientable surfaces.     

On prime ideals and radicals of polynomial rings and graded rings

We extend some known results on radicals and prime ideals from polynomial rings and Laurent polynomial rings to Z$\mathbb{Z}$-graded rings, i.e, rings graded by the additive group of integers. The main of them concerns the Brown–McCoy radical G$G$ and the radical S$S$, which for a given ring A$A$ is defined as the intersection of prime ideals I$I$ of A$A$ such that A/I$A/I$ is a ring with a large center. The studies are related to some open problems on the radicals G$G$ and S$S$ of polynomial rings and situated in the context of Koethe’s problem.     

A unified proof of Brooks’ theorem and Catlin’s theorem

Brooks’ theorem is a fundamental result in the theory of graph coloring. Catlin proved the following strengthening of Brooks’ theorem: Let d$d$ be an integer at least 3, and let G$G$ be a graph with maximum degree d$d$. If G$G$ does not contain _Kd+1$K_{d+1}$ as a subgraph, then G$G$ has a d$d$-coloring in which one color class has size α(G)$\alpha \left(G\right)$. Here α(G)$\alpha \left(G\right)$ denotes the independence number of G$G$. We give a unified proof of Brooks’ theorem and Catlin’s theorem.