# Tag Info

### Reverse Chernoff bound

The Generalized Littlewood-Offord Theorem isn't exactly what you want, but it gives what I think of as a "reverse Chernoff" bound by showing that the sum of random variables is unlikely to fall within ...

### How to use a 𝑝-coin so a TM can decide an undecidable language in polynomial time?

I'll take as given the existence of Chaitin's constant $\Omega\in[0,1]$, and that knowing its first $k$ bits is equivalent to be able to decide the halting problem for all Turning machines of size up ...

### Reverse Chernoff bound

The exponent in the standard Chernoff bound as it is stated on Wikipedia is tight for 0/1-valued random variables. Let $0<p<1$ and let $X_1,X_2,\ldots$ be a sequence of independent random ...
Accepted

1 vote

### Sample Complexity for Order Statistics

One way to approach this problem is via the CDF transformation. Consider $Z=F(X)$. We know $Z$ is uniformly distributed in $[0,1]$. Let $Z_{(1)},...,Z_{(m)}$ be the order statistics of these $m$ ...
1 vote

### Janson-type inequality, limited dependence

I'm posting a suitable answer that I found for this problem. The approach linked here does not exploit the fact that no $t$-tuples of elements of $\Omega$ are present in too many subsets $Y$ (for ...

Only top scored, non community-wiki answers of a minimum length are eligible