Source author record

Yevgeniy Kovchegov

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.PR math-ph math.MP math.CA math.CO math.ST Statistics Theory Applications Discrete Mathematics nlin.AO physics.comp-ph physics.data-an physics.geo-ph q-fin.EC quant-ph

Catalog footprint

Research overview

16works

15topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

A new life of Pearson's skewness

In this work we show how coupling and stochastic dominance methods can be successfully applied to a classical problem of rigorizing Pearson's skewness. Here, we use Fréchet means to define generalized notions of positive and negative skewness that we call truly positive and truly negative. Then, we apply stochastic dominance approach in establishing criteria for determining whether a continuous random variable is truly positively skewed. Intuitively, this means that scaled right tail of the probability density function exhibits strict stochastic dominance over equivalently scaled left tail. Finally, we use the stochastic dominance criteria and establish some basic examples of true positive skewness, thus demonstrating how the approach works in general.

preprint2022arXiv

Invariant Galton-Watson trees: metric properties and attraction with respect to generalized dynamical pruning

Invariant Galton-Watson (IGW) tree measures is a one-parameter family of critical Galton-Watson measures invariant with respect to a large class of tree reduction operations. Such operations include the generalized dynamical pruning (also known as hereditary reduction in a real tree setting) that eliminates descendant subtrees according to the value of an arbitrary subtree function that is monotone nondecreasing with respect to an isometry-induced partial tree order. We show that, under a mild regularity condition, the IGW measures are the only attractors of critical Galton-Watson measures with respect to the generalized dynamical pruning. We also derive the distributions of height, length, and size of the IGW trees.

preprint2021arXiv

Critical Tokunaga model for river networks

The hierarchical organization and self-similarity in river basins have been topics of extensive research in hydrology and geomorphology starting with the pioneering work of Horton in 1945. Despite significant theoretical and applied advances however, the mathematical origin of and relation among Horton laws for different stream attributes remain unsettled. Here we capitalize on a recently developed theory of random self-similar trees to introduce a one-parametric family of self-similar critical Tokunaga trees that elucidates the origin of Horton laws, Hack's laws, basin fractal dimension, power-law distributions of link attributes, and power-law relations between distinct attributes. The proposed family includes the celebrated Shreve's random topology model and extends to trees that approximate the observed river networks with realistic exponents. The results offer tools to increase our understanding of landscape organization under different hydroclimatic forcings, and to extend scaling relationships useful for hydrologic prediction to resolutions higher that those observed.

preprint2015arXiv

Horton Law in Self-Similar Trees

Self-similarity of random trees is related to the operation of pruning. Pruning $R$ cuts the leaves and their parental edges and removes the resulting chains of degree-two nodes from a finite tree. A Horton-Strahler order of a vertex $v$ and its parental edge is defined as the minimal number of prunings necessary to eliminate the subtree rooted at $v$ . A branch is a group of neighboring vertices and edges of the same order. The Horton numbers $N_k[K]$ and $N_{ij}[K]$ are defined as the expected number of branches of order $k$ , and the expected number of order- $i$ branches that merged order- $j$ branches, $j>i$ , respectively, in a finite tree of order $K$ . The Tokunaga coefficients are defined as $T_{ij}[K]=N_{ij}[K]/N_j[K]$ . The pruning decreases the orders of tree vertices by unity. A rooted full binary tree is said to be mean-self-similar if its Tokunaga coefficients are invariant with respect to pruning: $T_k:=T_{i,i+k}[K]$ . We show that for self-similar trees, the condition $\limsup(T_k)^{1/k}<\infty$ is necessary and sufficient for the existence of the strong Horton law: $N_k[K]/N_1[K] \rightarrow R^{1-k}$ , as $K \rightarrow \infty$ for some $R>0$ and every $k\geq 1$ . This work is a step toward providing rigorous foundations for the Horton law that, being omnipresent in natural branching systems, has escaped so far a formal explanation.

preprint2015arXiv

Horton self-similarity of Kingman's coalescent tree

The paper establishes a weak version of Horton self-similarity for a tree representation of Kingman's coalescent process. The proof is based on a Smoluchowski-type system of ordinary differential equations for the number of branches of a given Horton-Strahler order in a tree that represents Kingman's N-coalescent process with a constant kernel, in a hydrodynamic limit. We also demonstrate a close connection between the combinatorial Kingman's tree and the combinatorial level set tree of a white noise, which implies Horton self-similarity for the latter.

preprint2015arXiv

Path Coupling and Aggregate Path Coupling

In this survey paper, we describe and characterize an extension to the classical path coupling method applied statistical mechanical models, referred to as aggregate path coupling. In conjunction with large deviations estimates, we use this aggregate path coupling method to prove rapid mixing of Glauber dynamics for a large class of statistical mechanical models, including models that exhibit discontinuous phase transitions which have traditionally been more difficult to analyze rigorously. The parameter region for rapid mixing for the generalized Curie-Weiss-Potts model is derived as a new application of the aggregate path coupling method.

preprint2015arXiv

Rapid Mixing of Glauber Dynamics of Gibbs Ensembles via Aggregate Path Coupling and Large Deviations Methods

In this paper, we present a novel extension to the classical path coupling method to statistical mechanical models which we refer to as aggregate path coupling. In conjunction with large deviations estimates, we use this aggregate path coupling method to prove rapid mixing of Glauber dynamics for a large class of statistical mechanical models, including models that exhibit discontinuous phase transitions which have traditionally been more difficult to analyze rigorously. The parameter region for rapid mixing for the generalized Curie-Weiss-Potts model is derived as a new application of the aggregate path coupling method.

preprint2014arXiv

Orthogonal Polynomials for Seminonparametric Instrumental Variables Model

We develop an approach that resolves a {\it polynomial basis problem} for a class of models with discrete endogenous covariate, and for a class of econometric models considered in the work of Newey and Powell (2003), where the endogenous covariate is continuous. Suppose $X$ is a $d$ -dimensional endogenous random variable, $Z_1$ and $Z_2$ are the instrumental variables (vectors), and $Z=\left(\begin{array}{c}Z_1 \\Z_2\end{array}\right)$ . Now, assume that the conditional distributions of $X$ given $Z$ satisfy the conditions sufficient for solving the identification problem as in Newey and Powell (2003) or as in Proposition 1.1 of the current paper. That is, for a function $π(z)$ in the image space there is a.s. a unique function $g(x,z_1)$ in the domain space such that $E[g(X,Z_1)~|~Z]=π(Z) \qquad Z-a.s.$ In this paper, for a class of conditional distributions $X|Z$ , we produce an orthogonal polynomial basis $Q_j(x,z_1)$ such that for a.e. $Z_1=z_1$ , and for all $j \in \mathbb{Z}_+^d$ , and a certain $μ(Z)$ , $P_j(μ(Z))=E[Q_j(X, Z_1)~|~Z ],$ where $P_j$ is a polynomial of degree $j$ . This is what we call solving the {\it polynomial basis problem}. Assuming the knowledge of $X|Z$ and an inference of $π(z)$ , our approach provides a natural way of estimating the structural function of interest $g(x,z_1)$ . Our polynomial basis approach is naturally extended to Pearson-like and Ord-like families of distributions.

preprint2012arXiv

A Class of Markov Chains with no Spectral Gap

In this paper we extend the results of the research started by the first author, in which Karlin-McGregor diagonalization of certain reversible Markov chains over countably infinite general state spaces by orthogonal polynomials was used to estimate the rate of convergence to a stationary distribution. We use a method of Koornwinder to generate a large and interesting family of random walks which exhibits a lack of spectral gap, and a polynomial rate of convergence to the stationary distribution. For the Chebyshev type subfamily of Markov chains, we use asymptotic techniques to obtain an upper bound of order $O({\log{t} \over \sqrt{t}})$ and a lower bound of order $O({1 \over \sqrt{t}})$ on the distance to the stationary distribution regardless of the initial state. Due to the lack of a spectral gap, these results lie outside the scope of geometric ergodicity theory.

preprint2012arXiv

Stable Adiabatic Times for Markov Chains

In this paper we continue our work on adiabatic time of time-inhomogeneous Markov chains first introduced in Kovchegov (2010) and Bradford and Kovchegov (2011). Our study is an analog to the well-known Quantum Adiabatic (QA) theorem which characterizes the quantum adiabatic time for the evolution of a quantum system as a result of applying of a series of Hamilton operators, each is a linear combination of two given initial and final Hamilton operators, i.e. $\mathbf{H}(s) = (1-s)\mathbf{H_0} + s\mathbf{H_1}$ . Informally, the quantum adiabatic time of a quantum system specifies the speed at which the Hamiltonian operators changes so that the ground state of the system at any time $s$ will always remain $ε$ -close to that induced by the Hamilton operator $\mathbf{H}(s)$ at time $s$ . Analogously, we derive a sufficient condition for the stable adiabatic time of a time-inhomogeneous Markov evolution specified by applying a series of transition probability matrices, each is a linear combination of two given irreducible and aperiodic transition probability matrices, i.e., $\mathbf{P_{t}} = (1-t)\mathbf{P_{0}} + t\mathbf{P_{1}}$ . In particular we show that the stable adiabatic time $t_{sad}(\mathbf{P_{0}}, \mathbf{P_{1}}, ε) = O (t_{mix}^{4}(ε\slash 2) \slash ε^{3}), $ where $t_{mix}$ denotes the maximum mixing time over all $\mathbf{P_{t}}$ for $0 \leq t \leq 1$ .

preprint2011arXiv

Framework for discrete-time quantum walks and a symmetric walk on a binary tree

We formulate a framework for discrete-time quantum walks, motivated by classical random walks with memory. We present a specific representation of the classical walk with memory 2 on which this is based. The framework has no need for coin spaces, it imposes no constraints on the evolution operator other than unitarity, and is unifying of other approaches. As an example we construct a symmetric discrete-time quantum walk on the semi-infinite binary tree. The generating function of the amplitude at the root is computed in closed-form, as a function of time and the initial level n in the tree, and we find the asymptotic and a full numerical solution for the amplitude. It exhibits a sharp interference peak and a power law tail, as opposed to the exponentially decaying tail of a broadly peaked distribution of the classical symmetric random walk on a binary tree. The probability peak is orders of magnitude larger than it is for the classical walk (already at small n). The quantum walk shows a polynomial algorithmic speedup in n over the classical walk, which we conjecture to be of the order 2/3, based on strong trends in data.

preprint2011arXiv

Mixing Times for the Mean-Field Blume-Capel Model via Aggregate Path Coupling

In this paper we investigate the relationship between the mixing times of the Glauber dynamics of a statistical mechanical system with its thermodynamic equilibrium structure. For this we consider the mean-field Blume-Capel model, one of the simplest statistical mechanical models that exhibits the following intricate phase transition structure: within a two dimensional parameter space there exists a curve at which the model undergoes a second-order, continuous phase transition, a curve where the model undergoes a first-order, discontinuous phase transition, and a tricritical point which separates the two curves. We determine the interface between the regions of slow and rapid mixing. In order to completely determine the region of rapid mixing, we employ a novel extension of the path coupling method, successfully proving rapid mixing even in the absence of contraction between neighboring states.

preprint2011arXiv

Mixing times via super-fast coupling

We provide a coupling proof that the transposition shuffle on a deck of n cards is mixing of rate Cn(log{n}) with a moderate constant, C. This rate was determined by Diaconis and Shahshahani, but the question of a natural probabilistic coupling proof has been missing, and questions of its existence have been raised. The proof, and indeed any proof, requires that we enlarge the methodology of coupling to include intuitive but non-adapted coupling rules, because a typical Markovian coupling is incapable of resolving finer questions of rates.

preprint2011arXiv

Tokunaga and Horton self-similarity for level set trees of Markov chains

The Horton and Tokunaga branching laws provide a convenient framework for studying self-similarity in random trees. The Horton self-similarity is a weaker property that addresses the principal branching in a tree; it is a counterpart of the power-law size distribution for elements of a branching system. The stronger Tokunaga self-similarity addresses so-called side branching. The Horton and Tokunaga self-similarity have been empirically established in numerous observed and modeled systems, and proven for two paradigmatic models: the critical Galton-Watson branching process with finite progeny and the finite-tree representation of a regular Brownian excursion. This study establishes the Tokunaga and Horton self-similarity for a tree representation of a finite symmetric homogeneous Markov chain. We also extend the concept of Horton and Tokunaga self-similarity to infinite trees and establish self-similarity for an infinite-tree representation of a regular Brownian motion. We conjecture that fractional Brownian motions are also Tokunaga and Horton self-similar, with self-similarity parameters depending on the Hurst exponent.

preprint2010arXiv

Adiabatic times for Markov chains and applications

We state and prove a generalized adiabatic theorem for Markov chains and provide examples and applications related to Glauber dynamics of Ising model over Z^d/nZ^d. The theorems derived in this paper describe a type of adiabatic dynamics for l^1(R_+^n) norm preserving, time inhomogeneous Markov transformations, while quantum adiabatic theorems deal with l^2(C^n) norm preserving ones, i.e. gradually changing unitary dynamics in C^n.

preprint2002arXiv

Brownian Bridge and Self-Avoiding Random Walk

We establish the Brownian bridge asymptotics for a scaled self-avoiding walk conditioned on arriving to a far away point $n \vec{a}$ for $\vec{a}$ in $Z^d$ , as $n$ increases to infinity.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Yevgeniy Kovchegov

Research overview

Is this your work?

16 publications

A new life of Pearson's skewness

Invariant Galton-Watson trees: metric properties and attraction with respect to generalized dynamical pruning

Critical Tokunaga model for river networks

Horton Law in Self-Similar Trees

Horton self-similarity of Kingman's coalescent tree

Path Coupling and Aggregate Path Coupling

Rapid Mixing of Glauber Dynamics of Gibbs Ensembles via Aggregate Path Coupling and Large Deviations Methods

Orthogonal Polynomials for Seminonparametric Instrumental Variables Model

A Class of Markov Chains with no Spectral Gap

Stable Adiabatic Times for Markov Chains

Framework for discrete-time quantum walks and a symmetric walk on a binary tree

Mixing Times for the Mean-Field Blume-Capel Model via Aggregate Path Coupling

Mixing times via super-fast coupling

Tokunaga and Horton self-similarity for level set trees of Markov chains

Adiabatic times for Markov chains and applications

Brownian Bridge and Self-Avoiding Random Walk

See the researcher in context

Building this map preview