Search Results

Let me sketch why I think the answer is still $\Theta(\sqrt{n})$. Given any distribution such that, for each pair of the $2n$ random numbers, the probability that they are the same is $1/n$, we can s …

When you average a chain of ascending numbers, for two of the averages to be close to each other, three of the original numbers must be close to each other. This means that the probability of two of t …

Not every. Every convex function is either bounded below or monotonic. The first kind cannot produce any submartingale that is not bounded below. The second kind cannot produce any submartingale that, …

Yes in probability: The definitions of convergence in distribution to a constant random variable and convergence in probability to a constant random variable are the same. No almost surely: If we let …

Let $u_k$ be the number of variables with value exactly $k$. If you pick a distribution of the $u_k$ such that $E[u_k]=1$, $E[u_k^2] = 2-1/n$, $E[u_ku_l] = 1-1/n$ for $k \neq l$ and $\sum_{k=1}^n u_k$ …

I can do $k\geq 4$. This is done using a method similar to the upper bound from last time. Let $N_m$ be the number of samples that are at most $m$. Then we wish to upper bound the probability that $N_ …

The best deterministic constructions of matrices with the restricted isometry property are much worse than random matrices. Matrices with the restricted isometry property are important in compressed s …

Aaron and fedja have pointed out that the problem is equivalent to finding the convex region in the plane with area $1/2$ with the highest probability that a random line does not intersect it. The o …

Calculus of variation shows that the segment of the boundary of the optimal shape where the tangent line intersects two opposite sides must be a parabola. To see, this observe that the tangent line …

This has nothing to do with convergence, as there are counterexamples which do not depend on $N$. It also has nothing to do with time, as you didn't specify any condition that would restrict how the s …

Let $f_X$ be the pdf of $X$. Let $$C = \int_{-\infty}^{\infty} f_X(x) \log F_X(x) dx $$ and define $$\mathscr{Z}_n = \left\{ x_1,\dots, x_n \in \textrm{Supp}(X) \mid \sum_{i=1}^n \log f_X(x_i) \geq n …

I claim that the answer is yes. The key point that makes a distribution exponential is that there is a set of sufficient statistics, of the dimension of the manifold, that are additive. On an $n$-dim …

One way to see this technique is as a way of dealing with certain bad cases. $E[P/Q]$ can be unhelpfully dragged up by the inclusion of certain cases where $Q$ is small and $P$ is medium. $E[P]/E[Q]$ …

Clearly not. Let the measure space be the uniform measure on {$1,2,3,4$}. $A$ allows you to discern whether the number is greater or less than $2.5$ or not. $B$ allows you to discern whether the numbe …

It suffices to calculate $\mathbb E ( (P_E)_{ab} (P_E)_{cd})$ for all $1\leq a,b,c,d\leq n$, or, equivalently, calculate $\mathbb E( P_E \otimes P_E ) \in \mathbb R^n \otimes \mathbb R^n \otimes \math …