Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe quantile transform of a simple walk
119
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We examine a new path transform on 1-dimensional simple random walks and Brownian motion, the quantile transform. This transformation relates to identities in fluctuation theory due to Wendel, Port, Dassios and others, and to discrete and Browni
rate research
Read More
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.
We study a random walk on $mathbb{F}_p$ defined by $X_{n+1}=1/X_n+varepsilon_{n+1}$ if $X_n eq 0$, and $X_{n+1}=varepsilon_{n+1}$ if $X_n=0$, where $varepsilon_{n+1}$ are independent and identically distributed. This can be seen as a non-linear analogue of the Chung--Diaconis--Graham process. We show that the mixing time is of order $log p$, answering a question of Chatterjee and Diaconis.
We consider Boolean functions f:{-1,1}^n->{-1,1} that are close to a sum of independent functions on mutually exclusive subsets of the variables. We prove that any such function is close to just a single function on a single subset. We also consider Boolean functions f:R^n->{-1,1} that are close, with respect to any product distribution over R^n, to a sum of their variables. We prove that any such function is close to one of the variables. Both our results are independent of the number of variables, but depend on the variance of f. I.e., if f is epsilon*Var(f)-close to a sum of independent functions or random variables, then it is O(epsilon)-close to one of the independent functions or random variables, respectively. We prove that this dependence on Var(f) is tight. Our results are a generalization of the Friedgut-Kalai-Naor Theorem [FKN02], which holds for functions f:{-1,1}^n->{-1,1} that are close to a linear combination of uniformly distributed Boolean variables.
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.
We study the Doobs $h$-transform of the two-dimensional simple random walk with respect to its potential kernel, which can be thought of as the two-dimensional simple random walk conditioned on never hitting the origin. We derive an explicit formula for the Greens function of this random walk, and also prove a quantitative result on the speed of convergence of the (conditional) entrance measure to the harmonic measure (for the conditioned walk) on a finite set.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
