29
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
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$...
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}]}
$$
...
22
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
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)$, ...
14
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_{i-1}] \...
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 ...
10
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 ...
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 ...
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_{...
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 ...
8
There are variants of Berry-Esseen for bounded independence, although I have not seen one which is as general as the original theorem. For example Theorem 5.1. in Diakonikolas, Kane, Nelson implies a Berry-Esseen theorem for weighted sums of Bernoulli random variables with bounded independence, as long as none of the weights is too large. If you want error $\...
8
The Lopsided Lovasz Local Lemma relaxes the mutual independence condition to negative dependence. We assume we have events $A_1, \ldots, A_n$, with a lopsidependency graph $G$ defined on $[n]$ s.t. for every event $A_i$ and every $S \subseteq [n] \setminus \Gamma^+(i)$,
$$
\Pr\left(A_i \mid \bigwedge_{j \in S}{\bar{A_j}}\right) \le \Pr(A_i).
$$
As you (sort ...
8
So here, you only have two options: either your samples come from $p$, or from $q$ (and you know explicitly both).
By definition of the statistical/total variation distance, we have
$$
d_{TV}(p,q) = \sup_S( p(S)-q(S))
$$
where the supremum is taken over all measurable sets $S$. I haven't looked at the paper, but assuming all is nice (finite), the $\sup$ is ...
7
The de Moivre-Laplace Theorem shows that variables like $|T\cap S_1|$, after being suitably normalised and under certain conditions, will converge in distribution to a normal distribution. That's enough if you want constant lower bounds.
For lower bounds like $n^{-c}$, you need a slightly finer tool. Here's one reference I know of (but only by accident - I'...
7
$E[m]$ equals $n(H_n-1)$.
Here's a more complete proof sketch, following the argument suggested in my comment.
We start by showing that each permutation of the first $k-1$ elements is equally likely.
More precisely, let $X^*=(X_1,X_2,\ldots,X_K, \ldots)$ be an infinite random sequence where each $X_i$ is drawn independently and uniformly from $S$. Let ...
Only top voted, non community-wiki answers of a minimum length are eligible
