English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We consider two examples for a well-known method for obtaining concentrationof measure (COM) bounds for a given observable in a given measure. The methodis to consider an auxiliary Markov chain for which the invariant distributionis the measure of interest. Then one obtains COM bounds involving twoquantities. The first is the spectral gap of the Markov transition matrix. Thesecond is an appropriate Lipschitz constant for the observable of interest withrespect to 1 step of the Markov chain.  We consider two examples of the basic method. The first is to obtain roughCOM bounds for the length of the longest increasing subsequence (LIS) in auniform random permutation. The bounds are similar to well-known bounds ofTalagrand using his isoperimetric inequality.  The second example is to consider a 1d Markov chain: $X_0,X_1,\dots,X_n$. Weassume the invariant measure for the chain $\mu$ is reversible, and let theinitial distribution of $X_0$ be $\mu$. Then the observable of interest is anyfunction $f(X_0,X_1,\dots,X_n)$, which is Lipschitz with respect to replacementof single variables. One case of this is `target frequency analysis,' which isof interest in biostatistics. The auxiliary Markov chain is Glauber dynamicswhich is gapped in 1d.

Two Examples of COM Bounds using Spectral Gaps: Length of the LIS in a Random Permutation and Lipschitz Functions of 1d Markov Chains