All Questions
Tagged with convex-geometry pr.probability
69 questions
20
votes
2
answers
922
views
A functional inequality about log-concave functions
Let $f,g$ be smooth even log-concave functions on $\mathbb{R}^{n}$, i.e.,$f=e^{-F(x)}, g=e^{-G(x)}$ for some even convex functions $F(x),G(x)$. Is it true that:
$$
\int_{\mathbb{R}^{n}} \langle \...
- 3,946
15
votes
2
answers
2k
views
Intuitive explanation of Dvoretzky's theorem
I am wondering if anyone has an enlightening explanation of why Dvoretzky's theorem (which says that a high-dimensional convex body has an almost round central section) is true -- there are a number ...
- 96.4k
14
votes
1
answer
449
views
References for reasoning about the spectrum of a convex body?
By "spectrum of a convex body", I mean: start with a convex body $B$ in $\mathbb{R}^d$, then consider the corresponding $d \times d$ covariance matrix resulting from a uniform distribution over $B$ -- ...
- 143
13
votes
0
answers
1k
views
Constructive aspects of Caratheodory's theorem in convex analysis
Let me paraphrase Caratheodory's theorem in a probabilistic setup:
Let $X$ be a real-valued random variable. For $k = 1, \ldots, m$, let $f_k: \mathbb{R} \to \mathbb{R}$ be a continuous function such ...
- 1,839
12
votes
3
answers
3k
views
Area Enclosed by the Convex Hull of a Set of Random Points
Consider $n$ points generated randomly and uniformly on a unit square. What is the expected value of the area (as a function of $n$) enclosed by the convex hull of the set of points?
- 123
11
votes
1
answer
609
views
Tighter Caratheodory on the moment curve?
The moment curve is the set of points of the form
$$(t,t^2,t^3,...,t^n) \in R^n$$
Let $M$ be the portion of the moment curve where $t\in [0,1]$, and let $\overline{M}$ be the convex hull of $M$.
...
- 3,979
9
votes
2
answers
988
views
Average size of extreme points of convex hull of $N$ points
Fix $n$ a (small) integer.
Let $N$ be a (big) integer. Consider $N$ random points in the $n$-dimensional unit cube $[0, 1]^n$. The $N$ points are independently uniformly distributed.
Define $V(N)$ ...
- 3,432
8
votes
1
answer
355
views
Lower Bound of KL-Divergence Between Two Gibbs Measures
Suppose we have two Gibbs measures with densities
$$
p_f(x) \propto \exp(f(x)),\quad q_g(x)\propto \exp(g(x)).
$$
Consider the KL-divergence between $p_f$ and $q_g$, as a functional of $f$ and $g$, ...
- 1,127
7
votes
4
answers
476
views
What does $\mathbb E_V \max_{x \in V,\,\|x\|=1} x^T Ax$ evaluate to when $V$ is random $k$-dim suspace of $\mathbb R^n$ and $A$ is fixed psd matrix?
Let $G_{k,n}$ be the grassmannian of $k$-dimensional vector spaces of $\mathbb R^n$. By the Courant–Fisher characterization, the $k$th largest eigenvalue of an $n \times n$ psd matrix $A$ is given by
$...
- 6,853
7
votes
3
answers
377
views
Expected minimum face angle of random convex polyhedron in $\mathbb{R}^3$
Let $P_n$ be a "random convex polyhedron" in $\mathbb{R}^3$ of $n$ vertices, where "random" could follow any one
of a number of models:
(1) the convex hull of $n$ points randomly and uniformly ...
- 151k
7
votes
1
answer
444
views
Is an infinite-dimensional "Lebesgue measure" uniquely determined by a set of positive finite measure?
Let $\mu$ be a probability measure on a subset $C \subset \mathbb{R}^\infty$ of the space of sequences, and assume, for simplicity, that $C$ is closed and convex.
We say that $\mu$ admits shifts if ...
- 4,010
6
votes
2
answers
413
views
Random walk in a convex body or convex polytope
Let $\Delta$ be a convex body (i.e. a compact convex subset) or a convex polytope in
$\mathbb{R}^n$. Let $x$ be a point inside $\Delta$ and consider a (uniform) random walk starting at $x$ inside $\...
- 893
6
votes
3
answers
447
views
Isoperimetric inequality for $\epsilon$-expansion of a set only along a certain subspace
Let $\gamma_n$ be the standard gaussian distribution on $\mathbb R^n$. Let $V$ be a $k$-dimensional subspace of $\mathbb R^n$. Finally let $A$ be any (nonempty) Borel subset of $A$ with $\gamma_n(A) = ...
- 6,853
5
votes
3
answers
7k
views
Estimate probability( 0 is in the convex hull of N random points ) ?
Can anyone estimate N such that Prob( 0 is in the convex hull of $N$ points ) >= .95
for points uniformly scatterered in $[-1,1]^d$, $d = 2, 3, 4, 10$ ?
The application is nearest-neghbour ...
- 265
5
votes
4
answers
906
views
Probability that convex hull of multivariate Gaussian sample contains a given point
I am generating random vectors $X_1, \dots, X_N$ from a $d$-dimensional multivariate normal $\text N(\mu, \Sigma)$. I would like to know what is the probability that a given point $y \in R^d$ falls ...
- 101
5
votes
2
answers
985
views
Expected distance of a random point to the convex hull of N other points
Let $X_1, \cdots, X_N$ be i.i.d. $d$-dimensional random vectors, the exact distribution of $X$ is not very important in my application (as long as it continuous) so pick the one that works best, but ...
- 51
5
votes
0
answers
159
views
Log Sobolev inequality uniform in parameters
Fix a positive integer $N$. For $\theta \in [0,2\pi]$, set $\sigma_k(\theta) :=(\cos(k\theta),\sin(k\theta)) \in S^1$ for each integer $1\leq k\leq N$. Now for vectors $x_1,\ldots,x_N\in \mathbb{R}^2$,...
- 873
4
votes
1
answer
290
views
On the 1/2 assumption on concentration of measure for continuous cube
The concentration of measure on $ [0, 1]^n $ equipped with uniform probability measure $\mu_{\infty}$,
states that for any $A \subset [0, 1]^n $ with $ \mu_{\infty}(A) \geq \frac{1}{2} $,
we have:
$$...
- 365
4
votes
1
answer
227
views
Matching moments in even dimensions
Let $D$ be a probability distribution on the unit interval $[0,1]$ with moments $\mu_i=\mathbb{E}_D [x^i]$. Let $\delta(x)$ be a singleton probability distribution with all weight at $x\in [0,1]$. ...
- 3,979
4
votes
1
answer
503
views
An elementary probability question
Let $X$ be a $d$-dimensional random vector distributed according to probability measure $D$. At least the second moment of the coordinates of $X$ is finite.
Consider $n+1$ samples $X_0, \ldots, X_n ...
- 461
4
votes
0
answers
116
views
Improving log-Sobolev inequalities via quadratic regularisation
Suppose that $\mu(dx) = \exp(-\psi(x)) \, \mathrm{dx}$ is a probability measure on $\mathbf{R}^d$.
For suitable functions $g \geqslant 0$, define
$$\text{Ent}(g) = \int \mu(dx) g(x) \log \left( \frac{...
- 801
4
votes
0
answers
116
views
Log-Sobolev Inequalities for convex bodies
For a measure $\mu$ supported on a convex body $K$, what are the conditions on $\mu$ and $K$ to satisfy a Log-Sobolev inequality of the form:
$$\int f^{2} \log f^{2}\,d\mu -\int f^{2}\,d\mu \log\left(\...
- 519
4
votes
0
answers
156
views
Geometric meaning of the chi-square "measure of association"
In Statistics, there's a standard test of independence of two random variables taking values in finite sets $I,J$. It relies on the computation of $\chi$-square statistics,
$$
\chi^2:=\sum_{(i,j)\in ...
- 8,992
4
votes
0
answers
93
views
On symmetry and measure concentration rate for convex bodies
The concentration of measure on the cube $ [0, 1]^n $ equipped with uniform probability measure $\mu_{\infty}$,
states that for any $A \subset [0, 1]^n $ with $ \mu_{\infty}(A) \geq \frac{1}{2} $,
we ...
- 365
3
votes
1
answer
213
views
A lottery on coins in a convex set
You play the following game.
You get $4n$ gold coins and have to arrange them in the unit square in general position (no two coins have the same x or the same y coordinate). Call this set of coins $...
- 3,549
3
votes
3
answers
439
views
Inner radius of a random convex hull
Let $\sigma_1,\ldots,\sigma_M$ i.i.d. random vectors in $\mathbb{R}^d$, and for notational convenience, let $\Sigma=(\sigma_1,\ldots,\sigma_M)$. I am interested in understanding
$$ \gamma(\Sigma) = \...
- 980
3
votes
1
answer
188
views
Equivalent Definitions of the Gaussian Surface Measure for Regular Sets
I wonder if the following definitions of the Gaussian surface measure are equivalent.
First, let $\mathbb{R}^n$ be the Euclidean space and $A \subseteq \mathbb{R}^n$ be a sufficiently regular set, e....
- 1,127
3
votes
0
answers
83
views
Ornstein-Ulhenbeck like semigroup for the orthogonal group with a hypercontractive inequality
I am looking for an Ornstein-Uhlenbeck like semigroup $P_t$ and associated generator $\mathcal{L}$ on $G = \operatorname{SO}(n)$ or $\operatorname{O}(n)$ that has a hypercontractive inequality with a ...
- 941
3
votes
0
answers
134
views
Algorithm to calculate moments of uniform distribution on convex polyhedra
There is system of linear inequalities
$$
Ax \leq K,
$$
$$
x\geq a, x\leq b.
$$
$A$ is $(n\times m)$-matrix, where $n\approx 100$ and $m\approx 10000$, $rank(A)=n$.
Suppose that on set of solutions ...
3
votes
0
answers
635
views
Wasserstein distance, convex polytopes and extreme points
Let us consider convex polytopes with $K$ extreme points in $\mathbb{R}^d$. Let $\mathbf{P}$ be such polytope, and let $\text{ext}(\mathbf{P})$ denote its set of extreme points, so that $\mathbf{P} = \...
- 1,731
2
votes
2
answers
308
views
Expected value of Tukey’s half-space depth for log-concave measures
Let ${\mathbb P}$ be a probability measure in ${\mathbb R}^n$. Let $x\in{\mathbb R}^n$ be an arbitrary point. Let ${\mathbb H}_x$ be the set of halfspaces of ${\mathbb R}^n$ containing $x$. Let
\begin{...
- 781
2
votes
3
answers
1k
views
Draw a Random Line Through a Voronoi Tessellation, What is the Average Number of Voronoi Cell the Line Intersects?
Update: problem reformulation
Following the advice in comments, I now restate my problem using Voronoi
tessellation.
Given a unit hypercube $H_n=\{(x_1,\ldots,x_n)\in \mathbb{R}^n: 0\leq x_i\leq
1\}$...
2
votes
1
answer
113
views
Existence of fine approximate of a convex body in $\mathbb R^d$ with convex hull of $\mathcal O(d)$ points
Let $K$ be a convex body in $\mathbb R^d$ which contains the origin and let $\theta \in (0,1)$.
Question. Is it always possible to find $n$ points $x_1,\dotsc,x_n \in \mathbb R^d$ such that
$$
\theta ...
- 6,853
2
votes
1
answer
133
views
Discrete random walk on polytope via involutions
Let $P$ be a convex polytope (or more generally convex body, I suppose) in $V=\mathbb{R}^n$. For each $v\in \mathbb{P}V$, we define an involution $\tau_v\colon P\to P$ by setting $\tau_v(p)$ to be the ...
- 24.2k
2
votes
1
answer
165
views
Existence of preferred direction for a random vector with arbitrary distribution on sphere, under a condition on its covariance matrix
Let $X$ be random vector on the unit-sphere $S_{n-1}$ in $\mathbb R^n$. We don't assume that the distribution of $X$ is uniform on $S_{n-1}$
I'm interested in proving the existence of a (...
- 6,853
2
votes
1
answer
114
views
Reweighting probability measures by convex potentials, and contraction in transport distance
Let $W: \mathbf{R}^d \to \mathbf{R}$ be a convex function such that $\int \exp(-W) = 1$, and define probability measures $\mu_y$ by
$$\mu_y (dx) = \exp( - W (x - y)) \,dx,$$
i.e. each $\mu_y$ is a ...
- 801
2
votes
0
answers
164
views
Log Sobolev inequality for log concave perturbations of uniform measure
Suppose $\Omega$ is a convex bounded open set of $\mathbb{R}^n$ (I would be happy with just $\Omega$ as the $n$-dimensional cube). Let $\mu$ be the uniform measure on $\Omega$ and consider the ...
- 873
2
votes
0
answers
106
views
How to judge whether the following convex set contains a given point?
Let the set $\mathcal{S}=\left\{ \sum_{i=1}^n x_i\mathbf{h}_i：x_i\in[0,1] \text{ for all }i\right\}\subset\mathbb{R}^r$, i.e., a zonotope generated by $n$ column vector $\mathbf{h_1},\cdots,\mathbf{h}...
- 550
2
votes
0
answers
104
views
Weak convergence rates for integral operators
Suppose $q=\sum_{i=1}^m\pi_i\delta_{x_i}$ is a discrete measure on $\mathbb{R}^n$ and let $q\ast \varphi_\epsilon$ denote the convolution of $q$ with some mollifier $\varphi_\epsilon$, so that $q\ast\...
- 75
2
votes
0
answers
79
views
Compute Mixed Volume with Respect to Some Regular Sets
Let $( \mathbb{R}^n, \mathcal{B}, \gamma)$ be a measure space where $\mathcal{B}$ is the Borel sigma algebra and $\gamma$ is a continuous measure. For $A, B\in \mathcal{B}$ that are convex, the mixed ...
- 1,127
2
votes
0
answers
399
views
Convexity and probability
Problem instance: A closed convex body $B\subset {\Bbb R}^n$ of volume 1; a point $p\in B$; and a real number $v\in(0,1)$.
Objective: Find the probability $P(B,v,p)$ that $p\in B'$, for $B'$ a ...
- 17.6k
1
vote
1
answer
231
views
For $x_1,...,x_n$ iid random on sphere of radius $\sqrt{d}$ in $R^d$, what is a good upper-bound on min distance of $x_{n}$ from the other $x_i$'s?
Let $n$ and $d$ be large positive integers with $n \le d^\gamma$, for some absolute constant $\gamma>0$; i.e., $n$ is at most polynomial in $d$. Let $x_1,\ldots,x_n,x_{n+1}$ be drawn iid from the ...
- 6,853
1
vote
1
answer
195
views
Reference request: Inequalities involving convex sets and Gaussian variables stated in a paper by Talagrand
I'm looking for references for two facts that are stated without proof in the paper:
Talagrand, M., Are all sets of
positive measure essentially convex?, Lindenstrauss, J. (ed.) et al.,
Geometric ...
- 484
1
vote
1
answer
176
views
Is an inner product $\langle X, \epsilon\rangle$ between log-concave $X$ and $\epsilon\gets \{0,1\}^n$ log concave?
Let $X$ be a random variable with a density $p(x)$ with respect to the Lebesgue measure. We say that $X$ is log concave if $p(x) = \exp(-V(x))dx$ for $V(x)$ a convex function.
Let $X$ be log-concave ...
- 2,183
1
vote
1
answer
176
views
Tight upper-bounds for the Gaussian width of intersection of intersection of hyper-ellipsoid and unit-ball
Let $\Lambda$ be a positive-definite matrix of size $n$ and let $R \ge 0$, which may depend on $n$. Consider the set $S := \{x \in \mathbb R^n \mid \|x\|_2 \le R,\,\|x\|_{\Lambda^{-1}} \le 1\}$ where $...
- 6,853
1
vote
1
answer
67
views
Lower-bound for $\mathbb E[e^{-b(v^\top X - c)^2}]$, when $X$ is log-concave in high-dimensions
Let $d$ be a large positive integer. Fix a unit-vector $v \in \mathbb R^d$, and scalars $b,c \in \mathbb R$ with $b > 0$. Let $X$ be a log-concave random vector in $\mathbb R^d$ normalized so that ...
- 6,853
1
vote
1
answer
59
views
Characterization of random variables whose tensor powers have subexponential "small-ball" probabilities
Is there a succinct characterization of all random variables $\zeta$ on $\mathbb R$ with the following properties
1. Symmetry: $\zeta \overset{d}{=} - \zeta$.
2. Small-ball probability: there exists ...
- 6,853
1
vote
1
answer
234
views
When is the second largest Gaussian r.v. the largest in the stochastic sense?
Let $X_1, \ldots, X_n$ be jointly Gaussian, each of which is marginally distributed as a standard Gaussian $N(0,1)$. It is well known that $\max |X_i|$ achieves the maximum in the stochastic sense if $...
- 773
1
vote
0
answers
143
views
Integer points inside the high-dimensional ball (asymptotics)
Let $N(\alpha, n)$ denote the number of integer points inside the origin-centered ball of radius $\alpha \sqrt n$ in $n$ dimensions, where $\alpha \in (0,\infty)$ is some fixed constant. Precisely:
$$...
- 435
1
vote
0
answers
45
views
Inequality Involving Concave Monotonic Function
Assume that $ f: \mathbb{R} \to \mathbb{R}_+ $ is a concave, non-decreasing and positive function. Let $\mathbb{X}$ be a finite set consisting of $ 0\leq x_1 \leq x_2 \leq x_3 \leq \ldots \leq x_n$. ...
