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$.


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 ...


7

Many parameters of the largest connected component are not concentrated for $G(n,p)$ if $p=1/n$ and more generally if $p$ is in the critical window. Examples are the diameter and the size of the largest component, the size of the second largest component, the number of leaves the component has, etc. See e.g. Aldous, David. "Brownian excursions, critical ...


6

See the "inclusion-exclusion" Lemma 2.2 here https://www.cs.bgu.ac.il/~karyeh/mark-conc2.pdf . For distributions $p,q,p',q'$, we have $$ ||p\otimes q-p'\otimes q'|| \le ||p-p'|| + ||q-q'|| - ||p-p'|| \cdot ||q-q'||. $$ From here, it immediately follows that if $p=p_1=p_2=\cdots=p_k$ and $q=q_1=p_2=\cdots=q_k$ and furthermore $||p-q||=d$, then the TV ...


4

This is not a complete answer by any means, but just a quick estimate on $\mathbb{E}[\sum_{i=1}^k X_{[i]}]$ that is slightly better than the trivial bound of $O(k\sqrt{\log n})$. If this is your goal, I would think it is easier to go directly for it than consider any given $X_{[k]}$. Let $X_S=\sum_{i\in S} X_i$ for a subset $S\subseteq [n]$ and $Y_k=\sum_{i=...


4

There are 4 possibilities, name them e1-e4: e1 neither match e2 a only matches e3 b only matches e4 both match Now I restate what you want to prove: Suppose: \begin{align*} \Pr[e4] &\gt 0.25 & \text{prob of correct guess} \\ \Pr[e2] + \Pr[e4] &\leq 0.5 & \text{prob guess a correctly} \\ \Pr[e3] + \Pr[e4] &\leq 0.5 & \...


4

Instead of choosing $z\in\{-1,1\}^{2^n}$ uniformly at random, you may want to look instead at more structured (yet "pseudo-random"-ish) functions such as bent functions: Definition. A Boolean function $f\colon\{-1,1\}^n\to\{-1,1\}$ is called bent if $|\hat{f}(S)|=2^{-n/2}$ for all $S\subseteq [n]$. Such functions are known to exist; see, e.g., Chapter 6....


3

$\newcommand{\bm}{\boldsymbol}$The two scenarios are not equal even when $s = t$. In the $s,t$ case you always re-sample the same number of bits, while in the $\delta$ case you get a binomial distribution in the number of bits flipped. Let us define $\text{Maj}$ in a slightly different way than you might be used to, but assure yourself it is correct. $$\...


3

The maximum of $I(X:Y)$ in your problem is $$H(Y) - H(Z) \cdot \bigg|\Pr[Y = 0|Z = 0] - \Pr[Y = 0|Z = 1] \bigg|. $$ Let me first demonstrate an example for which this maximum is attained. Denote $\alpha = \Pr[Y = 0|Z = 0], \beta = \Pr[Y = 0|Z = 1]$. Sample $X$ uniformly at random from $[0, 1]$ and then sample $Z$ independently from $X$ according to the ...


3

So I found a simple proof, but the proof is a bit fastidious to write (the symmetries make it easy to check however). If you have a more elegant/fundamental way to prove it, let me know! Or if it's a well not result as well. So the proof goes that way: first let's define this array: b\a | 0 || 1 | _____________________ 0 | c | d || g | h | | ...


2

@odea, one can see that $\chi^2(P||Q) \leq c D(P||Q)$ cannot hold in general by taking a two point space with $P = \{ 1 , 0\}$ and $Q = \{ q, 1-q \}$. Then $\chi^2(P ; Q) = \frac 1 q -1$ while $D(P||Q) = \log \frac 1 q$. Such a $c$ would need to satisfy $c \geq \frac{x-1}{\log x}$ for $x \to \infty$. However, if one assumes that $c=\| \frac{dP}{dQ} \|_\...


1

If the number of gaps is small, you can do the following brute force approach. Try every possible way of filling those gaps (there will be exponentially many possibilities, in the number of the gaps). For every "guess", fill in the gaps accordingly and train a maximum-likelihood Markov chain on the full sequence. You can even guarantee something about the ...


1

I think $x_1 = \dots = x_{\ell-1} = 0, x_{\ell} = y_1 = \dots = y_{\ell} = n$ is better. You are guaranteed to choose red in all bins except for bin $\ell$, and bin $\ell$ has $n$ red balls and $n$ blue balls, so your overall odds of success are $1/2 > 1/e$.


1

Another (weaker) bound, along with a lower bound, both easy to obtain: using Hellinger distance as a proxy (and its relation to total variation distance), you get $$ 1-(1-d_{\rm TV}(p, q)^2 )^{k/2} \leq d_{\rm TV}(p^{\otimes k}, q^{\otimes k}) \leq \sqrt{1-(1-d_{\rm TV}(p, q) )^{2k}} $$ See e.g., Fact C.2.3 from my survey on distribution testing.


1

Here's the lower bound that OP asks for. It may give some intuition for an upper bound as well. Lemma 1. The random process described in the post moves on average at least $2n/(m+1)$ balls per time step. That is, for large $N$, the expected number of balls redistributed in the first $N$ steps is at least $(2n/(m+1))$ per step. Proof. First consider a ...


1

Well what do you know -- in a recent paper of ours, https://arxiv.org/abs/1910.05270, the inequalities leading to (12) invoke Hoeffding where the $(b_i-a_i)^2=p_i^2$, and further the $0\le p_i\le c$ satisfy $\sum_i p_i\le 1$, which implies $\sum_i p_i^2\le c$ -- precisely the sort of heterogeneous Hoeffding bound I had in mind. BTW, the argument we use in (...


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