Shravas Rao

activity

20122026

most citedImproved Lower Bounds for the Restricted Isometry Property of Subsampled Fourier Matrices

3 citations · 8 across the 11 of their papers we have counts for

collaborators

Showing math.PRShow all

5 papers · 1 filter

math.PR2025

Towards a Banach Space Chernoff Bound for Markov Chains via Chaining Arguments

Shravas Rao

Let ${Y_{i}}_{i = 1}^{\infty}$ be a stationary reversible Markov chain with state space $[N]$ , let $(X, ∥ \cdot ∥)$ be a real-valued Banach space and let $f_1, \ldots, f_n: [N] \ri…

math.PR2019

Concentration of Markov chains with bounded moments

Assaf Naor, Shravas Rao, Oded Regev

Let ${W_{t}}_{t = 1}^{\infty}$ be a finite state stationary Markov chain, and suppose that $f$ is a real-valued function on the state space. If $f$ is bounded, then Gillman's expande…

math.PR2018

A Hoeffding inequality for Markov chains

Shravas Rao

We prove deviation bounds for the random variable $\sum_{i = 1}^{n} f_{i} (Y_{i})$ in which ${Y_{i}}_{i = 1}^{\infty}$ is a Markov chain with stationary distribution and state space $[N]$ ,…

math.PR2017

A Sharp Tail Bound for the Expander Random Sampler

Shravas Rao, Oded Regev

Consider an expander graph in which a $μ$ fraction of the vertices are marked. A random walk starts at a uniform vertex and at each step continues to a random neighbor. Gillman sho…

math.PR2012★ 1 cited

Finding hitting times in various graphs

Shravas Rao

The hitting time, h_uv, of a random walk on a finite graph G, is the expected time for the walk to reach vertex v given that it started at vertex u. We present two methods of calcu…