All Questions
11 questions
0
votes
0
answers
44
views
Large Deviation Principle for an adaptive sampling rule for Multi Armed Bandits
Consider the following adaptive strategy for sampling from a Multi Armed Bandit with $K$ arms:
Split the $T$ rounds into $N (\in \mathbb{N})$ disjoint intervals. Each interval is indexed by $i=1,2,\...
- 9
1
vote
0
answers
131
views
Large-deviation inequalities for a class of simple random multivariate polynomials
Let $N$ be a large positive integer and let $[N] := \{1,2,\ldots,N\}$. For any $k$, let $K_{N,k}$ denote the collection of $k$-element subsets of $[N]$. Let $x=(x_1,\ldots,x_N)$ be a uniformly random ...
- 6,853
2
votes
0
answers
129
views
Large deviation principle for product of iid bounded symmetric random variables
Let $n$ and $k$ be positive integers. Let $X$ be the empirical mean of $n$ iid Rademacher random variables. Note that the distribution of $X$ is symmetric about 0, and also $|X| \le 1$ w.p 1. Let $X_1,...
- 6,853
4
votes
2
answers
308
views
Concentration of minimum Hamming distance between $N$ points sampled iid from uniform distribution on $n$-dim hypercube $\{0,1\}^n$
Let $n$ be a large positive integer. Sample $N \ge 2$ points $x_1,\ldots,x_N$ iid from the uniform distribution on the $n$-dimensional hypercube $\{0,1\}^n$. Define the gap $\delta_{N,n} := \min_{i \...
- 6,853
2
votes
1
answer
99
views
Concentration Inequality for Bounding Lipschitz Empirical Lass
Let $(\Omega,\mathcal{F},\mathbb{P})$ be a probability space, $(X_n:\Omega\rightarrow \mathbb{R}^m)_n$ be a sequence of i.i.d. random variables and let $L:\mathbb{R}^m\rightarrow [0,\infty)$ be ...
- 77
9
votes
1
answer
350
views
Concentration inequalities for very rare events on a multiplicative scale
Let $E_1, \dots, E_N$ be independent events, each of probability $p$, where $p$ is very close to $0$. Let $A_N = \frac{1}{N} ( 1_{E_1} + \dots + 1_{E_N} )$ be the proportion of the events $E_i$ that ...
- 323
0
votes
1
answer
140
views
Tail bounds for the absolute difference of a coupled pair of sub-Gaussian random variables
Let $P$ and $Q$ are sub-Gaussian distributions on $\mathbb R$, and $(X,X')$ be a coupling of $P$ and $Q$, i.e $(X,X') \sim \pi$ for some distribution on $\mathbb R^2$ with marginals $P$ and $Q$.
...
- 6,853
1
vote
0
answers
123
views
Sanov-type finite-sample bound on $KL(P\|\hat{P}_n)$
Let $P$ be a distribution on an alphabet of size $k$ and let $\hat{P}_n$ be an empirical version of $P$ via $n$ i.i.d samples $a_1,\ldots,a_n \sim P$, i.e $\hat{P}_n := (1/n)\sum_{i=1}^n\delta_{a_i}$.
...
- 6,853
5
votes
0
answers
1k
views
Asymptotic behavior of row sums in 2-d array of random variables
Set-up. Let $f : \mathbb{N} \to \mathbb{N}$ be increasing. For each $m \in [0,1]$, consider an infinite two-dimensional array of random variables, where row $n$ has $f(n)$ variables:
$B^m_{1,1}$ $B^...
- 61
3
votes
1
answer
294
views
Concentration inequalities specialized for log-likelihood / log-density functions
Let $P$ be a probability measure and $f$ be some probability density function (not necessarily related to $P$). Consider the function
$$
L(X_1,\ldots,X_n)
=\frac1n\sum_{i=1}^n\log f(X_i),
\quad
X_i\...
- 710
7
votes
2
answers
594
views
Large deviation/concentration inequality for submartingale
Let $S_t = M_t + D_t$ be the sum of a martingale $\left(M_t\right)_{t=1,2,\ldots}$ and a predictable process $(D_t)_{t=1,2,\ldots}$ such that the variance of the increments of $M$ is uniformly bounded ...
- 355