Search Results

Deterministic $\Psi$ is bound to fail. You must randomize. Consider three probability measures supported on $\{1,2\}$. A deterministic $\Psi$ will have only two of the measures in its image. The adver …

The conjectured inequality is false in General. Proof: Let $\ell=\lfloor n^{1/2}/2 \rfloor$ and let $G_1,G_2,\dots,G_\ell$ be disjoint cliques of size $\ell$. Let $K$ be a clique on $n-\ell^2 >n/2$ …

The connection between uniform spanning trees $T$ and stable polynomials used in Fedor Petrov's answer is indeed beautiful, and yields a sharp bound. I want to mention that the slightly weaker bound o …

Let $(X_n)_{n\in\mathbb{N}}$ be i.i.d. real random variables and let $0<c<1$. Then the following are equivalent: (a) There exists $r>0$ such that $P(|X_k|>e^{rk} \; \, \text{infinitely often} )=0$. ( …

Observe that $X_n=X_{n-1}(1+Z_n)$ where $\{Z_k\}_{k \ge 1}$ are i.i.d. standard normal. Hence to analyze the asymptotic distribution of $|X_n|$, pass to logarithms, to get $$\log(|X_n|)= \log(|X_1|) + …

There was part of the hint that you ignored, namely using Levy's construction. To add some detail, the approximation of $S^{n}$ by BM is done recursively in each dyadic interval, rather than globally. …

First suppose that hypotheses (a) and (b) hold. I will write $w_{i,n}$ instead of $w_i^n$ for clarity. Given $\epsilon>0$, the Monotone convergence theorem implies that there exists $M$ such that $ …

As noted in the comment by James Martin, some assumption is needed on the Markov chain, e.g., that each step of the chain can be implemented on a Turing machine in polynomial time. The Swendsen-Wang …

Yes, $\mathcal{P}$ is closed in the spaces \begin{equation} \mathcal{P}_1:=\left\{ X = (X_t)_{t \in \mathbb{Z}} \, : \, \mathbb{E} X_t = 0 \hbox{ and } \mathbb{E}[X_t^2]< \infty, \, \forall\, …

Here is another variation of the fine solution suggested by Mike and made precise by Iosif Pinelis. Let $Z$ be a polish (i.e., separable and complete) metric space with metric $d(\cdot,\cdot).$ Given …

One can avoid the $n$-dependence. Let $H$ be a Hilbert space, endowed with the norm $\|\cdot\|$. Given $f:\mathbb{S}^{d-1}\to H$ which is $L$-Lipschitz, the goal is to prove a concentration inequalit …

For the one dimensional case, a quite nice bound is in Theorem 4.2 of [1]. See also [2]. The dependence on $\epsilon$ that you seek was first shown by Kesten[3]. The combinatorial approach was revive …

For $0<\beta \le 1/2$, any limiting distribution of the rescaled process $S_n/n^\beta$ will be fully supported in $[-1,1]$, so it will not be normal. The downward drift will imply (using Hoeffding's …

A more general theorem is proved in [1] for the limits of random walks in the domain of attraction of a stable law. In the case described in the problem, one can also use the strong approximation appr …

The parameters $p_n$ are not arbitrary numerical parameters. They represent the expectation of one binary variable in a product space. Changing them additively is very different from changing the powe …