# Tag Info

### 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 ...
• 10.5k
Accepted

You have $\mathbb{E}[y_i]=\epsilon q(x_i) + (1-\epsilon)/2$ and $0 \leq y_i \leq 1$, with all they $y_i$s being independent. Thus the Chernoff-Hoeffding bound gives $$\mathbb{P}\left[\left|\frac{1}{n} ... • 2,803 3 votes ### Sum of Independent Exponential Random Variables For the Laplace distribution, if you use the Bernoulli bound you can write$$Ee^{u\sum_i X_i} = \prod_i \frac1{1-u^2/\lambda_i^2} \le \frac1{1-u^2\sigma^2/2},$$where \sigma^2=2\sum_i\lambda_i^{-2}.... • 958 2 votes Accepted ### Chernoff bound for weighted sums of Bernoulli random variables Your bound (at least when t\le E[S]) seems to follow from the standard multiplicative Chernoff bound, as follows. Lemma 1. (a standard multiplicative Chernoff bound) Let S be the sum of ... • 10.7k 2 votes ### \rho OPT + k approximation for bin packing (Unpublished result of David P. Williamson) Using Chandra's hint, I think I got the idea. We bounded the probability:$$Pr(G_i \leq b_i) \leq e^{-\frac{\rho(1-\frac{1}{\rho})^2 b_i}{3}} Now consider an item of size $s_i$ that was left. It was ...
• 1,153
1 vote
Accepted

The generic Chernoff bound for a random variable $X$ is attained by applying Markov's inequality to $e^{t X}$. For positive $t$ this gives a bound on the right tail of $X$ in terms of its moment-...
• 109
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 ...
• 203

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