28
Here is an explicit proof that a standard Chernoff bound is tight up to constant factors in the exponent for a particular range of the parameters. (In particular, whenever the variables are 0 or 1, and 1 with probability 1/2 or less, and $\epsilon\in(0,1/2)$, and the Chernoff upper bound is less than a constant.)
If you find a mistake, please let me know.
...
22
The Berry-Esseen theorem can give tail probability lower bounds, as long as they are higher than $n^{-1/2}$.
Another tool you can use is the Paley-Zygmund inequality. It implies that for any even integer $k$, and any real-valued random variable $X$,
$$
\Pr[|X| >= \frac{1}{2}(\mathbb{E}[X^k])^{1/k}] \geq \frac{\mathbb{E}[X^k]^2}{4\mathbb{E}[X^{2k}]}
$$
...
21
Answer: $\Theta\left(\sqrt{\frac{m}{n\log n}}\right)$.
Applying a multidimensional version of the Central Limit Theorem, we get that the vector $(X_1,\dots, X_n)$ has asymptotically multivariate Gaussian distribution with
$$\mathrm{Var}[X_i] = m\left(\frac{1}{n} - \frac{1}{n^2}\right),$$
and
$$\mathrm{Cov}(X_i, X_j) = -m/n^2.$$
We will assume below that $X$...
19
They are separate (assuming $P \ne NP$). Consider the following property $P(x)$: $x$ is a $2n$-bit string, where either the first $n$ bits are not all zeros, or the last $n$ bits are a yes-instance of 3SAT. It's clear that testing whether $x$ satisfies $P$ is NP-hard, yet almost all strings satisfy it: the density $\to 1$ as $n \to \infty$.
17
Notwithstanding Friedgut's theorem about $k$-SAT, while we lack techniques to get to negligible $\epsilon$ for small $k$, it seems more useful to talk about the satisfiability threshold ($\alpha - \epsilon$) and the unsatisfiability threshold ($\alpha + \epsilon$) as separate entities.
The unsatisfiability threshold is known to be at most 4.4898, a slight ...
15
First observation: the cases with and without replacement have exactly the same answer. (Once you have drawn a red ball, say, you don't care about future draws of red balls: all you care about now is the relative order of future green and yellow balls).
A good way to attack the case with replacement is by embedding in continuous time.
Imagine that the ...
15
The answer is $\Theta(\sqrt{n})$.
First, let's compute $E_{n-1}$.
Let's suppose we throw $n$ balls into $n$ bins, and look at the probability that a bin has exactly $k$ balls in it. This probability comes from the Poisson distribution, and as $n$ goes to $\infty$ the probability that there are exactly $k$ balls in a given bin is $\frac{1}{e} \frac{1}{ k!}$....
15
The intended answer is probably that the length of the longest codeword is approximately $$-\log_2 10^{-6} = 20.$$ But this is wrong. The information given doesn't come close to specifying the length of the longest codeword. Even the entire probability distribution doesn't specify the length of the longest codeword.
One can see this by constructing a ...
15
I think there is a concentration result about $e \log n$, but I haven't filled in the details yet.
We can get an upper bound for the probability that node $n$ has $d$ ancestors not including $0$. For each possible complete chain of $d$ nonzero ancestors $(a_1,a_2,...,a_d)$, the probability of that chain is $(\frac{1}{a_1})(\frac{1}{a_2})\cdots (\frac{1}{a_d}...
14
If you are indeed okay with bounding sums of Bernoulli trials (and not, say, bounded random variables), the following is pretty tight.
Slud's Inequality*. Let $\{X_i\}_{i=1}^n$ be i.i.d. draws from a Bernoulli r.v. with $\mathbb{E}(X_1) = p$, and let integer $k\leq n$ be given. If either (a) $p\leq 1/4$ and $np \leq k$, or (b) $np \leq k \leq n(1-p)$, ...
13
For your first question, I think you can show that w.h.p. $X_{\max}-X_{\textrm{sec-max}}$ is
$$o\left(\sqrt{\frac{m}{n}\frac{\log^2\log n}{\log n}}\right).$$
Note that this is $o(\sqrt{m/n})$.
Compare your random experiment to the following alternative: Let $X_1$ be the maximum load of any of the first $n/2$ buckets. Let $X_2$ be the maximum load of any of ...
13
I can't find a reference, so I'll just sketch the proof here.
Theorem. Let $X_1, \cdots, X_n$ be real random variables. Let $a_1, \cdots, a_n, b_1, \cdots, b_n$ be constants. Suppose that, for all $i \in \{1,\cdots,n\}$ and all $(x_1,\cdots,x_{i-1})$ in the support of $(X_1, \cdots, X_{i-1})$, we have
$\mathbb{E}[X_i | X_1=x_1, \cdots, X_{i-1}=x_{...
11
EDIT: (2014-08-08)
As Douglas Zare points out in the comments, the argument below, specifically the 'bridge' between the two probabilities, is incorrect. I don't see a straight forward way to fix it. I'll leave the answer here as I believe it still provides some intuition, but know that $$ \Pr(E_m) \le \prod_{l=1}^{m}\Pr(F_l) $$ is not true in general.
...
11
I think the solution to your problem is not reading a probability book, but reading more papers in TCS.
Most papers in TCS don't actually use very advanced probability tools. Most of them use a small collection of basic and well known probability tricks. The reason you have a hard time following them is that you are not yet familiar with this bag of tricks, ...
11
Fan Chung and Linyuan Lu.
Concentration inequalities and martingale inequalities: a survey
available at
http://projecteuclid.org/euclid.im/1175266369 or at Fan Chung Graham's web page.
10
Bob's best bet is to guess the $t$ values with largest probability.
If you're willing to use Rényi entropy instead, Proposition 17 in Boztaş' Entropies, Guessing and Cryptography states that the error probability after $t$ guesses is at most
$$ 1 - 2^{-H_2(\mu)\left(1-\frac{\log t}{\log n}\right)} \approx \ln 2 \left(1-\frac{\log t}{\log n}\right) H_2(\mu), ...
10
The following is an extended comment, it does not answer your question in the terms you posed it but does give a semantics for higher-order probabilistic calculi which you may find of interest.
In the past few years there has been a very active line of research around so-called quantitative denotational semantics of linear logic, based on the idea (...
10
The following is a rather straight-forward $O(n \log n)$ toss algorithm.
Assume $1-\exp(-n)$ is the error probability we are aiming for. Let $N$ be some power of $2$ that is between say $100n$ and $200n$ (just some big enough constant times $n$). We maintain a candidate set of coins, $C$. Initially, we put $N$ coins in $C$.
Now for $i=1,\dots,\log N$, do ...
9
Another classic of TCS/Combinatorics oriented probability is Alon and Spencer's The Probabilistic Method.
9
The Kushilevitz-Mansour algorithm in learning theory establishes, that whenever $\hat{f}(x)$ is approximately sparse, i.e. there are only $O(poly(n))$-many large Fourier coefficients of absolute value $\Omega(1/poly(n))$, then we can find their locations and approximate their complex values in $\sf{BPP}$. Of course you can also efficiently sample from that ...
9
You probably want to look at David et al's paper, Asymptotically Almost All λ-terms are Strongly Normalizing:
We present a quantitative analysis of various (syntactic and behavioral) properties of random λ-terms. Our main results show that asymptotically, almost all terms are strongly normalizing and that any fixed closed term almost never appears in a ...
9
We now understand that for any fixed bound $k \in \mathbb{N}$ on the treewidth, we can convert any Boolean circuit of treewidth less than $k$ to a so-called d-SDNNF circuit, in linear time and with the dependency on $k$ being singly exponential.
The so-called d-SDNNFs are circuits satisfying conditions on the use of negation (only at the leaves), ...
9
Let me denote the sum as $S_{n,p}$. It gives the probability that a random sample from the binomial distribution $B(n,p)$ exceeds its expected value.
For $0<p<1$ constant, the central limit theorem tells you that $B(n,p)$ looks like the normal distribution $N(pn,p(1-p)n)$ for large $n$. Since this is symmetric, $S_{n,p}$ will be approximately $1/2$ as ...
answered Apr 1 '15 at 18:03
Emil Jeřábek supports Monica
11.2k3 gold badges42 silver badges65 bronze badges
9
Here's how to do it.
First, choose a random $k$ between 1 and $n$ to be the "crowded bin".
Next, choose a random permutation $\pi$ of $1,2,\ldots, n-1$.
Now, for $1 \leq i \leq n-1$,
$$ \mbox{put ball } i \mbox{ into bin }
\begin{cases} k \ \ \ \ \ \ \ \ \ \ \ \ \mbox{with probability }\ \frac{1}{\sqrt{n}}, \\
k + \pi(i) \mbox{ with probability }1 - \frac{...
9
I think it's a simple application of Hoeffding's inequality. Using your notation, let $Q_i = \frac1m C_i$, i.e. $Q$ is the empirical distribution that approximates $P$. The total variation distance between $P$ and $Q$, i.e. half the $\ell_1$ distance, is
$$
\max_{S \subseteq [n]} \left| \sum_{i \in S}{P_i} - \sum_{i \in S}{Q_i}\right|.
$$
Let $P(S):= \sum_{...
9
It is well known that a barbell graph (two cliques of size $n/3$ connected by a path of length $n/3$) has average hitting time $\Omega(n^3)$, but I believe the same applies to minimum hitting time (for uniform or stationary distribution). Whatever vertex you choose as the one that you think is easiest to hit, you have constant probability of starting in the ...
9
This fact is a corollary of a more general theorem. Let $\gamma_1,\dots, \gamma_{2n}$ be (jointly) Gaussian random variables; we don't assume that they are independent or identically distributed. Let $c_{ij} = {\mathbb E}[\gamma_i \gamma_j]$ be the covariance of $\gamma_i$ and $\gamma_j$. Consider the complete graph on $\{1, \dots, 2n\}$; assign weight $c_{...
9
This answer may be disappointing, but working on a log scale really mostly just makes the formulas nicer. The definition, as written, has the following important properties:
Composition: If $A(\cdot)$ is an $\varepsilon$-DP algorithm, and for any $a$ in the range of $A$, $A'(\cdot, a)$ is an $\varepsilon'$-DP algorithm, then the composed algorithm $A' \circ ...
8
Suppose to the contrary that
$$ P(x^2 \geq n_i) \geq C/n_i^2 $$ for some infinite sequence $n_1$, $n_2$, $\ldots$, $n_i$, $\ldots$, with $P(x^2 > n_i) > 2P(x^2 > n_{i+1})$. Then we have $$ Var(x) = \int_{x=0}^\infty x^2 d \mu.$$
But now, let's set $n_0 = 0$ and break this integral up into
$$ Var(x) = \sum_{j=0}^\infty \int_{n_j}^{n_{j+1}}x^2 d \mu.$...
8
Here are some "nearby best" references, for what it's worth. It would seem the way to go on this question is to reduce it to a question on "noisy Turing machines", which have been studied (somewhat recently), and which are apparently the nearest relevant area of the literature. The basic/general/reasonable answer seems to be that if the TM can resist/correct ...
Only top voted, non community-wiki answers of a minimum length are eligible
