Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userHow long is the convex minorant of a one-dimensional random walk?
73
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We prove distributional limit theorems for the length of the largest convex minorant of a one-dimensional random walk with independent identically distributed increments. Depending on the increment law, there are several regimes with different limit distributions for this length. Among other tools, a representation of the convex minorant of a random walk in terms of uniform random permutations is utilized.
rate research
Read More
We consider a nearest-neighbor, one-dimensional random walk ${X_n}_{ngeq 0}$ in a random i.i.d. environment, in the regime where the walk is transient with speed v_P > 0 and there exists an $sin(1,2)$ such that the annealed law of $n^{-1/s} (X_n - n v_P)$ converges to a stable law of parameter s. Under the quenched law (i.e., conditioned on the environment), we show that no limit laws are possible. In particular we show that there exist sequences {t_k} and {t_k} depending on the environment only, such that a quenched central limit theorem holds along the subsequence t_k, but the quenched limiting distribution along the subsequence t_k is a centered reverse exponential distribution. This complements the results of a recent paper of Peterson and Zeitouni (arXiv:0704.1778v1 [math.PR]) which handled the case when the parameter $sin(0,1)$.
We consider the sums $S_n=xi_1+cdots+xi_n$ of independent identically distributed random variables. We do not assume that the $xi$s have a finite mean. Under subexponential type conditions on distribution of the summands, we find the asymptotics of the probability ${bf P}{M>x}$ as $xtoinfty$, provided that $M=sup{S_n, nge1}$ is a proper random variable. Special attention is paid to the case of tails which are regularly varying at infinity. We provide some sufficient conditions for the integrated weighted tail distribution to be subexponential. We supplement these conditions by a number of examples which cover both the infinite- and the finite-mean cases. In particular, we show that subexponentiality of distribution $F$ does not imply subexponentiality of its integrated tail distribution $F^I$.
Domains of attraction are identified for the universality classes of one-point asymptotic fluctuations for the Kardar-Parisi-Zhang (KPZ) equation with general initial data. The criterion is based on a large deviation rate function for the rescaled initial data, which arises naturally from the Hopf-Cole transformation. This allows us, in particular, to distinguish the domains of attraction of curved, flat, and Brownian initial data, and to identify the boundary between the curved and flat domains of attraction, which turns out to correspond to square root initial data. The distribution of the asymptotic one-point fluctuations is characterized by means of a variational formula written in terms of certain limiting processes (arising as subsequential limits of the spatial fluctuations of KPZ equation with narrow wedge initial data, as shown in [CH16]) which are widely believed to coincide with the Airy$_2$ process. In order to identify these distributions for general initial data, we extend earlier results on continuum statistics of the Airy$_2$ process to probabilities involving the process on the entire line. In particular, this allows us to write an explicit Fredholm determinant formula for the case of square root initial data.
Motivated by storage applications, we study the following data structure problem: An encoder wishes to store a collection of jointly-distributed files $overline{X}:=(X_1,X_2,ldots, X_n) sim mu$ which are emph{correlated} ($H_mu(overline{X}) ll sum_i H_mu(X_i)$), using as little (expected) memory as possible, such that each individual file $X_i$ can be recovered quickly with few (ideally constant) memory accesses. In the case of independent random files, a dramatic result by Pat (FOCS08) and subsequently by Dodis, Pat and Thorup (STOC10) shows that it is possible to store $overline{X}$ using just a emph{constant} number of extra bits beyond the information-theoretic minimum space, while at the same time decoding each $X_i$ in constant time. However, in the (realistic) case where the files are correlated, much weaker results are known, requiring at least $Omega(n/polylg n)$ extra bits for constant decoding time, even for simple joint distributions $mu$. We focus on the natural case of compressingemph{Markov chains}, i.e., storing a length-$n$ random walk on any (possibly directed) graph $G$. Denoting by $kappa(G,n)$ the number of length-$n$ walks on $G$, we show that there is a succinct data structure storing a random walk using $lg_2 kappa(G,n) + O(lg n)$ bits of space, such that any vertex along the walk can be decoded in $O(1)$ time on a word-RAM. For the harder task of matching the emph{point-wise} optimal space of the walk, i.e., the empirical entropy $sum_{i=1}^{n-1} lg (deg(v_i))$, we present a data structure with $O(1)$ extra bits at the price of $O(lg n)$ decoding time, and show that any improvement on this would lead to an improved solution on the long-standing Dictionary problem. All of our data structures support the emph{online} version of the problem with constant update and query time.
We derive properties of the rate function in Varadhans (annealed) large deviation principle for multidimensional, ballistic random walk in random environment, in a certain neighborhood of the zero set of the rate function. Our approach relates the LDP to that of regeneration times and distances. The analysis of the latter is possible due to the i.i.d. structure of regenerations.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
