7

Let's suppose that we have a polynomial time randomized algorithm $A$ for a decision problem $\Pi$ with the property that $$ \mathrm{Pr}[A \text{ is right}] > 1/2 $$ for all inputs. (In particular, independent of the input length $n$.) We can use Chernoff bounds to show something stronger, namely that for any fixed $c$, there is a polynomial time, ...


5

Yes, we can get a bound like this. To see why, we will need to look a little more closely at how Chernoff bounds are proved. A relatively standard form of this kind of tail bound would assume that $$ X = X_1 + \cdots + X_n $$ with all $X_i$ independent, discrete, supported in $[-1,1]$, with mean $\mu_i = 0$, variance $\sigma_i^2$. The resulting tail ...


4

In this answer I assume given scores are pairwise didtinct. Note that the probability of two scores being equal is 0 since we have continuous probability. I think the same proof can be tweaked to span the case where two probabilities are equal but it will make it more complicated. Let $p_1, \dots p_n$ be the set of employees sorted in descending order ...


4

Chernoff's bound applies to negatively correlated random variables, such as your hypergeometric distribution. You can find a full treatment in Dubhashi and Panconesi's very useful monograph Concentration of measure for the analysis of algorithms, as well as in many lecture notes, such as this one by Hariharan Ramesh.


4

You can bound the variance as follows. Let $b_i$ be an indicator variable signaling that $x_i$ was chosen. You are interested in $y = \sum_i b_i x_i$. We have $$ \mathbb{E}[(b_ix_i)^2] = \frac{x_i^2}{\sqrt{n}}, \quad \mathbb{E}[b_ix_i\cdot b_jx_j] = \frac{\sqrt{n}(\sqrt{n}-1)}{n(n-1)}x_ix_j = (1-O(1/\sqrt{n}))\frac{x_ix_j}{n}. $$ Therefore $$ \mathbb{E}[y^2]=...


4

The correct approximation here is Poisson. The occupancy of each bin is distributed roughly $P(1)$ (Poisson with expectation $1$), and tail bounds for Poisson random variables show that with probability $1-1/n^2$ (say), the variable is at most $O(\log n/\log\log n)$. A union bound shows that with high probability, all bins contain at most $O(\log n/\log\log ...


3

It is more practical just because it has the advantage of being easier to state and compute with in many situations (quoted from [1]). I am not sure whether (i) still holds for $\mu' = E[X] \le \mu$. At least, we cannot obtain that directly from the following computation: $$Pr[X \ge (1 + \delta) \mu] \le Pr[X \ge (1 + \delta) \mu'] \le e^{-\frac{\delta^...


3

Here is another way of looking at $p_A$ and $p_B$. We can think of $B$ as a deterministic algorithm which accepts an additional input $r$ representing the randomness. This input is drawn from some distribution $R$. Also, denote by $P(x)$ the correct answer. Then $$ p_B(x) = \Pr_{r \sim R} [B(x,r) = P(x)]. $$ Let $M = O(n\delta^{-2}\log m)$, and sample $r_1,\...


2

You can use a coupling. Let $X = X_1,\ldots,X_n$, and suppose that $\Pr[X_i=1] = \beta_i$ (so $\beta := \mathbb{E}[X] = \sum_i \beta_i \geq \alpha$). Let $p = \alpha/\beta$, and define $\alpha_i = p\beta_i$. Let $Z_i \sim \mathrm{Bernoulli}(p)$, and define $Y_i = X_i Z_i$. Notice that $X_i \geq Y_i$ and that $\Pr[Y_i=1] = p\beta_i = \alpha_i$. If we define $...


2

Okay, here is a full answer. We will use the fact, that any bipartite graph of maximum degree $d$ can be broken into (at most) $d$ matchings. In our case, this means that we can split $A$ into (at most) $\sqrt{k}$ disjoint sets of elements $S_i\subseteq\{(i,j)\in[n]\times[n] \mid A_{i,j}=1\}$ of size at most $n$ such that any every element in each set has ...


2

Following Yuval's answer, I found the following inequality in Dubhashi and Paconesi's book: $$ \Pr \Big[\big|Y_i - \mathbb{E}[Y_i]\big| \geq t \Big] \leq \exp\Big(\frac{-(n-1)t^2}{2(n-i)(i-1)} \Big)$$


1

If $c < 1/2$ then for any problem there is an algorithm that answers correctly with probability at least $c+1/n$, say. For small $n$, the algorithm just outputs the hardwired correct answer. When $n$ is large enough so that $c + 1/n \leq 1/2$, the algorithm just tosses a coin. What went wrong? For BPP amplification to work, we need a gap between the ...


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