Search Results

For $g(n)$ a decreasing function, we have $\limsup Y_n/g(n)\geq 1$ if and only if $Y_n> g(n)(1-\epsilon)$ infinitely often. Based on an approach suggested by Aleksei Kulikov, if $n \in [2^k, 2^{k+1}]$ …

One can improve the $\log n$ factor by at most a constant. Divide the $N \times N$ board into $n\times n $ squares. (Even if $n$ is not a divisor of $N$, one can divide at most a quarter of the board …

No, $$ \frac{1}{n} \sum_{k=1}^{n}| \mu (A) \cap T^{-k}(B) - \mu(A)\mu(B)|$$ is a sum of i.i.d random varables, since $T^{-k}$ are i.i.d uniform circle rotations so by the law of large numbers it conve …

Often in mathematics, especially in applied mathematics, we have some finite object we care about, and we choose to study it by putting it in a sequence and studying the limit of the sequence, which i …

I have an approach to solve the problem for $\gamma>2/n$, which can perhaps be adapated to work for smaller $\gamma$. Consider first the optimization problem: minimize $\mathbb P( X \geq k) $ where $X …

I can do a somewhat worse estimate of $e^{ - n t^2/4}$. If I calculated right, the estimate you state is approximately true for $t$ small but fails for $t$ large, but if I got things the wrong way aro …

Let $F(x) =\int_{1-x}^{\infty} W(t) dt$. Then the inequality is $F(\rho x ) \geq \alpha F(x)$ and we also have that $\frac{dF}{dx} (\frac{1}{2}) = 1$ and $F$ is convex down. In particular for $x=\frac …

Let me give a partial answer ignoring issues of inseparability. The map $\mathbb A^{m-j}_{\mathbb F_q(x_1,\dots,x_j)} \to \mathbb A^n_{\mathbb F_q(x_1,\dots,x_j)}$ has image of dimension $r$. If $\mat …

A greedy algorithm lets us pick an element that it's at least $\lceil j n/N \rceil $ of the sets, leaving us with at most $n- \lceil j n/N \rceil $ subsets of size $j$ of an $N-1$-element set. We can …

The strategy suggested in Geoffry Irving's answer of betting the maximum amount each time is correct, but the argument given is incomplete. The expected final amount, conditional on the outcomes of th …

No. If $\mathbb E[X^+]=\infty$ then $$\infty = \mathbb E[ \lfloor X^+\rfloor ] =\sum_{n=1}^{\infty} \mathbb P(X \geq n) = \sum_{n=1}^{\infty} \mathbb P(X_n\geq n)$$ and the events $X_n \geq n$ are ind …

I have a suggestion that seems to bring the two sides to be compared much closer together. Take a block-diagonal matrix $B$ with $k$ blocks each a copy of $A$. This has the same eigenvalue measure as …

On the "Furthermore": The central limit theorem for vectors involves the variance-covariance matrix. Let $Z = X+iY$ be a complex random variable (with mean $0$ for simplicity). If $X,Y$ have variance- …

A trivial lower bound is $$p_{N,n,\gamma} \geq 1 - \binom{N}{2} \mathbb P ( d_H (x_1,x_2)< \gamma n) \geq 1 - \binom{N}{2} ( \gamma^{-\gamma} (1-\gamma)^{-(1-\gamma) } 2^{-1} ) ^n $$ with the last i …

Let $(Y_1,\dots, Y_k)$ be a random $k$-tuple uniformly distributed in $(\mathbb R/\mathbb Z)^k$. Let $X_i = \sum_{j=1}^k i^j Y_j \in \mathbb R/\mathbb Z$. Then the $X_i$ are $k$-wise independent (and …