Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA Characteristic Polynomial for The Transition Probability Matrix of A Correlated Random Walk on A Graph
106
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We define a correlated random walk (CRW) induced from the time evolution matrix (the Grover matrix) of the Grover walk on a graph $G$, and present a formula for the characteristic polynomial of the transition probability matrix of this CRW by using a determinant expression for the generalized weighted zeta function of $G$. As applications, we give the spectrum of the transition probability matrices for the CRWs induced from the Grover matrices of regular graphs and semiregular bipartite graphs. Furthermore, we consider another type of the CRW on a graph.
rate research
Read More
Given a random walk a method is presented to produce a matrix of transition probabilities that is consistent with that random walk. The method is a kind of reverse application of the usual ergodicity and is tested by using a transition matrix to produce a path and then using that path to create the estimate. The two matrices and their predictions are then compared. A variety of situations test the method, random matrices, metastable configurations (for which ergodicity often does not apply) and explicit violation of detailed balance.
Consider a discrete-time one-dimensional supercritical branching random walk. We study the probability that there exists an infinite ray in the branching random walk that always lies above the line of slope $gamma-epsilon$, where $gamma$ denotes the asymptotic speed of the right-most position in the branching random walk. Under mild general assumptions upon the distribution of the branching random walk, we prove that when $epsilonto 0$, the probability in question decays like $exp{- {beta + o(1)over epsilon^{1/2}}}$, where $beta$ is a positive constant depending on the distribution of the branching random walk. In the special case of i.i.d. Bernoulli$(p)$ random variables (with $0<p<{1over 2}$) assigned on a rooted binary tree, this answers an open question of Robin Pemantle.
A t by n random matrix A is formed by sampling n independent random column vectors, each containing t components. The random Gram matrix of size n, G_n, contains the dot products between all pairs of column vectors in the randomly generated matrix A; that is, G_n = transpose(A) A. The matrix G_n has characteristic roots coinciding with the singular values of A. Furthermore, the sequences det(G_i) and per(G_i) (for i = 0, 1, ..., n) are factors that comprise the expected coefficients of the characteristic and permanental polynomials of G_n. We prove theorems that relate the generating functions and recursions for the traces of matrix powers, expected characteristic coefficients, expected determinants E(det(G_n)), and expected permanents E(per(G_n)) in terms of each other. Using the derived recursions, we exhibit the efficient computation of the expected determinant and expected permanent of a random Gram matrix G_n, formed according to any underlying distribution. These theoretical results may be used both to speed up numerical algorithms and to investigate the numerical properties of the expected characteristic and permanental coefficients of any matrix comprised of independently sampled columns.
In 1991, Persi Diaconis and Daniel Stroock obtained two canonical path bounds on the second largest eigenvalue for simple random walk on a connected graph, the Poincare and Cheeger bounds, and they raised the question as to whether the Poincare bound is always superior. In this paper, we present some background on these issues, provide an example where Cheeger beats Poincare, establish some sufficient conditions on the canonical paths for the Poincare bound to triumph, and show that there is always a choice of paths for which this happens.
Very sparse random graphs are known to typically be singular (i.e., have singular adjacency matrix), due to the presence of low-degree dependencies such as isolated vertices and pairs of degree-1 vertices with the same neighbourhood. We prove that these kinds of dependencies are in some sense the only causes of singularity: for constants $kge 3$ and $lambda > 0$, an ErdH os--Renyi random graph $Gsimmathbb{G}(n,lambda/n)$ with $n$ vertices and edge probability $lambda/n$ typically has the property that its $k$-core (its largest subgraph with minimum degree at least $k$) is nonsingular. This resolves a conjecture of Vu from the 2014 International Congress of Mathematicians, and adds to a short list of known nonsingularity theorems for extremely sparse random matrices with density $O(1/n)$. A key aspect of our proof is a technique to extract high-degree vertices and use them to boost the rank, starting from approximate rank bounds obtainable from (non-quantitative) spectral convergence machinery due to Bordenave, Lelarge and Salez.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
