Search Results

Let $a<1<b$. I prove that for large $n$: 1) the probability that a random sequence of length $n$ has at least $B:=b\log_2 n$ consecutive zeroes is at most $n^{1-b}$; 2) the probability that a rando …

We may sample $x$ as follows: choose i.i.d. standard Gaussian $\xi_1,\ldots,\xi_d$ and put $$x_i=\frac{\xi_i}{\sqrt{\sum_{j=1}^d \xi_j^2}},\quad i=1,2,\ldots,d.$$ Then $$\frac1{\|x\|_1^2}=\frac{\sum \ …

Denote $p_k=P(X=k)$. Then $E(R_n)=\sum_k P(k\in \{X_1,\ldots,X_n\})\leqslant \sum_k \min(1,np_k)$. We are given that $\sum kp_k<\infty$. Fix $\varepsilon>0$. The sum of $\min(1,np_k)$ over $k<\varepsi …

Every $\gamma>0$ seems ok. We have $$ \mathbb{P}(|x_k|\geqslant e^{\gamma k})\leqslant \mathbb{P}(1+|x_k|\geqslant e^{\gamma k})= \mathbb{P}(\gamma^{-1}\log(1+|x_k|)\geqslant k), $$ and the sum of th …

This result belongs to P. Erdös, W. Feller, and H. Pollard (1949). It worth mention that if $\sum a_n p_n<\infty$, this follows from Wiener division theorem in the algebra of absolutely summable Fouri …

Imagine that for all $k=1,2,\ldots$ all events $A_n$ for $n\in [k!,(k+1)!-1)$ are the same event $C_k$. Then if $x$ belongs to all $A_i$ along a subsequence of positive density yields that it belongs …

For reals $x<y$ denote $\rho(x,y)=1/2^n$ if integer $n$ is minimal such that there exist integer $i$ with $x<i/2^n\leqslant y$. We have $\rho(x,y)\geqslant |x-y|/2$ and ``in average'' $\rho(x,y)$ beha …

[Previous answer was completely wrong.] Denote by $p_k$ the probability that at least $k$ vertices remain. Then the expectation is of course $\sum p_i$. I claim that $p_k=\frac{(n-k+1)! (n-k)!}{(n-2k …

Compare 56 and 55 instead. Denote $a=6$ in the first case and $a=5$ in the second, $b=11-a$. Look at the first 5. If the next term equals $a$, we are done (the same thing for both cases). If the next …

I count $(0,0)$ and $(n,n)$ as crossings, subtract 2 if you do not want. For $k\in \{0,1,\dots,n\}$ denote by $\xi_k$ the random variable which equals 1 if $(k,k)$ lies on the path and 0 otherwise. Th …

I claim that even $$\frac{\Phi(-\theta)}{\Phi(-\lambda \theta) }< e^{\frac{\theta^2(-1+\lambda^2)}{2}}.$$ Rewrite this as $h(\theta)<h(\lambda \theta)$, where $h(\theta)=\Phi(-\theta)e^{\theta^2/2}$. …

yes, if $\sum_{i,j\in A}$ means double summation (each pair $i,j$ is taken twice) then denote $f_i$ and $g_i$ characteristic functions of your events from $A$ and $B$ respectively, LHS equals $2 \sum …

If I am not mistaken, this expectation equals the coefficient of $x^{\varepsilon n}$ in $(1-x)^{\alpha n}(1+x)^{(1-\alpha) n}$ divided by the corresponding coefficient in $(1+x)^n$ (which equals, of c …

Even $c=1-\varepsilon$ works when $n$ is large enough. This question is about bounding the diagonal bipartite Ramsey, see the recent achievement of David Conlon here http://people.maths.ox.ac.uk/~conl …

Usually not. Denote $f_i=\mathbb{1}_{i\in S}$, then $\mathbb{E} f_i=\mathbb{E} f_i^2=kp_i$, $\sum f_i\equiv k$, $\mathbb{E} f_if_j=cp_ip_j$ if $i\ne j$. Thus $$k^2p_i=k\mathbb{E} f_i=\mathbb{E} \sum_j …