Pruned discrete random samples

Let $X_i,i\in \mathbb{N}$, be independent and identically distributed random variables with values in ${\mathbb{N}}_0$. We transform (‘prune’) the sequence $\{X_1,\dots ,X_n\},n\in \mathbb{N}$, of discrete random samples into a sequence $\{0,1,2,\dots ,Y_n\},n\in \mathbb{N}$, of contiguous random sets by replacing $X_{n+1}$ with $Y_n+1$ if $X_{n+1}>Y_n$. We consider the asymptotic behaviour of $Y_n$ as $n\to \infty$. Applications include path growth in digital search trees and the number of tables in Pitmanʼs Chinese restaurant process if the latter is conditioned on its limit value.     

A remark on the orbit structure of the complexification of a semisimple symmetric space

We consider the action of a real semisimple Lie group G on the complexification $G_{\mathbf{C}}/H_{\mathbf{C}}$ of a semisimple symmetric space $G/H$ and we present a refinement of Matsuki?s results (Matsuki, 1997 [1]) in this case. We exhibit a finite set of points in $G_{\mathbf{C}}/H_{\mathbf{C}}$, sitting on closed G-orbits of locally minimal dimension, whose slice representation determines the G-orbit structure of $G_{\mathbf{C}}/H_{\mathbf{C}}$. Every such point $\overline{p}$ lies on a compact torus and occurs at specific values of the restricted roots of the symmetric pair $(\mathfrak{g},\mathfrak{h})$. The slice representation at $\overline{p}$ is equivalent to the isotropy representation of a real reductive symmetric space, namely $Z_G(p^4)/G_{\overline{p}}$. In principle, this gives the possibility to explicitly parametrize all G-orbits in $G_{\mathbf{C}}/H_{\mathbf{C}}$.     

Lower bounds for moments of global scores of pairwise Markov chains

Let $X_1,\dots$ and $Y_1,\dots$ be random sequences taking values in a finite set $\mathbb{A}$. We consider a similarity score $L_n?L(X_1,\dots ,X_n;Y_1,\dots ,Y_n)$ that measures the homology of words $(X_1,\dots ,X_n)$ and $(Y_1,\dots ,Y_n)$. A typical example is the length of the longest common subsequence. We study the order of moment $E{|L_n?E{L}_n|}^r$ in the case where the two-dimensional process $(X_1,Y_1),(X_2,Y_2),\dots$ is a Markov chain on $\mathbb{A}\times \mathbb{A}$. This general model involves independent Markov chains, hidden Markov models, Markov switching models and many more. Our main result establishes a condition that guarantees that $E{|L_n?E{L}_n|}^r?n^{\frac{r}{2}}$. We also perform simulations indicating the validity of the condition.     

On optimal polynomial meshes

Let $P_n^d$ be the space of real algebraic polynomials of $d$ variables and degree at most $n$, $K?{\mathbb{R}}^d$ a compact set, ${6p6}_K:={sup}_{x\in K}\left|p\left(x\right)\right|$ the usual supremum norm on $K$, and $card\left(Y\right)$ the cardinality of a finite set $Y$. A family of sets $Y=\{Y_n?K,n\in \mathbb{N}\}$ is called an admissible mesh in $K$ if there exists a constant $c_1>0$ depending only on $K$ such that ${6p6}_K\le c_1{6p6}_{Y_n}\text{,}p\in P_n^d,n\in \mathbb{N}\text{,}$ where the cardinality of $Y_n$ grows at most polynomially. If $card\left(Y_n\right)\le c_2{n}^d,n\in \mathbb{N}$ with some $c_2>0$ depending only on $K$ then we say that the admissible mesh is optimal. This notion of admissible meshes is related to norming sets which are widely used in the literature. In this paper we present some general families of sets possessing admissible meshes which are optimal or near optimal in the sense that the cardinality of sets $Y_n$ does not grow too fast. In particular, it will be shown that graph domains bounded by polynomial graphs, convex polytopes and star like sets with $C^2$ boundary possess optimal admissible meshes. In addition, graph domains with piecewise analytic boundary and any convex sets in ${\mathbb{R}}^2$ possess almost optimal admissible meshes in the sense that the cardinality of admissible meshes is larger than optimal only by a $logn$ factor.     

Domination and upper domination of direct product graphs

Let $X_{\mathbb{Z}∕n\mathbb{Z}}$ denote the unitary Cayley graph of $\mathbb{Z}∕n\mathbb{Z}$. We present results on the tightness of the known inequality $\gamma \left(X_{\mathbb{Z}∕n\mathbb{Z}}\right)\le {\gamma }_t\left(X_{\mathbb{Z}∕n\mathbb{Z}}\right)\le g\left(n\right)$, where $\gamma$ and${\gamma }_t$ denote the domination number and total domination number, respectively, and $g$ is the arithmetic function known as Jacobsthal’s function. In particular, we construct integers $n$ with arbitrarily many distinct prime factors such that $\gamma \left(X_{\mathbb{Z}∕n\mathbb{Z}}\right)\le {\gamma }_t\left(X_{\mathbb{Z}∕n\mathbb{Z}}\right)\le g\left(n\right)?1$. We give lower bounds for the domination numbers of direct products of complete graphs and present a conjecture for the exact values of the upper domination numbers of direct products of balanced, complete multipartite graphs.     

The Carroll and Chang conjecture of equal Indscal components when Candecomp/Parafac gives perfect fit

The Candecomp/Parafac algorithm approximates a set of matrices ${\mathbf{X}}_1\text{,}\dots \text{,}{\mathbf{X}}_I$ by products of the form ${\mathbf{AC}}_i{\mathbf{B}}^{\prime }$, with ${\mathbf{C}}_i$ diagonal, $i=1\text{,}\dots \text{,}I$. Carroll and Chang have conjectured that, when the matrices are symmetric, the resulting $\mathbf{A}$ and $\mathbf{B}$ will be column wise proportional. For cases of perfect fit, Ten Berge et al. have shown that the conjecture holds true in a variety of cases, but may fail when there is no unique solution. In such cases, obtaining proportionality by changing (part of) the solution seems possible. The present paper extends and further clarifies their results. In particular, where Ten Berge et al. solved all $I\times 2\times 2$ cases, now all $I\times 3\times 3$ cases, and also the $I\times 4\times 4$ cases for $I=2\text{,}8$, and 9 are clarified. In a number of cases, $\mathbf{A}$ and $\mathbf{B}$ necessarily have column wise proportionality when Candecomp/Parafac is run to convergence. In other cases, proportionality can be obtained by using specific methods. No cases were found that seem to resist proportionality.     

Approximation of maximum of Gaussian random fields

This contribution is concerned with Gumbel limiting results for supremum ${\mathbb{M}}_{\mathit{n}}={\sup }_{\mathit{t}\in [\mathbf{0},{\mathit{T}}_{\mathit{n}}]}?|X_{\mathit{n}}(\mathit{t})|$ with $X_{\mathit{n}},\mathit{n}\in {\mathbb{N}}^2$ centered Gaussian random fields with continuous trajectories. We show first the convergence of a related point process to a Poisson point process thereby extending previous results obtained in [8] for Gaussian processes. Furthermore, we derive Gumbel limit results for ${\mathbb{M}}_{\mathit{n}}$ as $\mathit{n}\to \infty$ and show a second-order approximation for $\mathbb{E}{\{{\mathbb{M}}_{\mathit{n}}^p\}}^{1/p}$ for any $p\ge 1$.