All Questions
Tagged with pr.probability mg.metric-geometry
223 questions
10
votes
1
answer
484
views
Stochastic Covering Number of a Convex Set
Consider a convex set, say $S = [0,1]^d$. Let $X_1, X_2,\ldots,X_n, \ldots$ be i.i.d. random variables that are uniformly distributed on $S$. Denote the Euclidean ball centered at $x \in \mathbb{R}^d$ ...
- 1,127
9
votes
1
answer
484
views
What does convergence in distribution "in the Gromov–Hausdorff" sense mean?
I am trying to understand this survey article by Le Gall on Brownian geometry, especially the statement of Theorem 1.
The basic statement of the theorem is
$$(m_n,d_n) \to (m_{\infty}, d_{\infty})$$
"...
- 7,857
9
votes
4
answers
371
views
Diameter of random segment intersection graph?
I have an even number of points $n$ randomly distributed (uniformly) in a disk.
Then the points are randomly connected to form $n/2$ segments, a perfect
matching.
Finally, I form the intersection ...
- 151k
9
votes
2
answers
658
views
Probability that randomly chosen balls have a nonempty common intersection
Fix some $0 < r < 1$. A collection of points $x_1, \dots, x_n$ are chosen independently and uniformly at random from the closed unit ball in $\mathbb R^d$.
What is the probability that the ...
- 6,223
9
votes
1
answer
784
views
Width of a random convex polygon
Consider a planar (2D) random walk comprised of N steps.
Consider the minimum convex polygon enclosing the N points visited by the random walker.
Assume the definition of the width of a convex polygon ...
- 91
9
votes
1
answer
642
views
Twisted random walks
Suppose the points of two random walks in $\mathbb{R}^2$ are given the
step number (or time) as a third coordinate, so that they become paths in $\mathbb{R}^3$.
Here are several pairs of walks of $n=...
- 151k
9
votes
1
answer
2k
views
Uniform sampling from general simplex with a twist
This is part of a question I had asked elsewhere, and then some of the links redirected me to CS stack exchange.
Given $0\leq a_1\leq\dots\leq a_D\leq1$ (all strictly positive), I want to draw points ...
- 221
9
votes
2
answers
560
views
Integrating a simple exponential over the space of matrices that define a metric
I want to interpret an $n\times n$ matrix $D$ as a set of pairwise distances, and assume that $D$ obeys metric properties. Namely, $D_{ii} = 0$, $D_{ij} \geq 0$, $D_{ij} = D_{ji}$ and $D_{ij} \leq D_{...
- 147
9
votes
1
answer
338
views
Visibility in a growing orchard
This is a variant on Polya's orchard problem.1,2
Suppose trees are planted randomly in the plane.
The question is: How many trees are visible from the origin as
their radii grow?
More precisely, ...
- 151k
9
votes
2
answers
519
views
The fraction of the sphere a fixed distance from a subspace
The following problem has a beautiful geometric interpretation in terms of the proportion of points on the Euclidean sphere in $\mathbb{R}^d$ that lie at least a certain distance away from a $k$-...
- 91
9
votes
2
answers
674
views
Small crown probabilities (and infinite dimensional margin assumption)
My question is:
How do I find sharp upper bounds on $P(|q|\leq \epsilon)$ uniformly over a set of gaussian polynomes $q$ of degree two.
Notations and definitions (to make the question rigorous)
Let ...
9
votes
0
answers
242
views
Does there exist such a probability distribution?
Does there exist a probability distribution over the set $\{(x,y,z)\in[0,1]^3\colon x+y+z=3/2\}$ whose projection on each of the three coordinate axes is the uniform distribution over the interval $[0,...
- 128k
8
votes
2
answers
1k
views
Talagrand's inequality for the discrete cube
Talagrand showed that if $f$ is a convex $1$-Lipschitz function on $\mathbb{R}^n$, and if $\mu$ is a product of probability measures supported over the interval, then $f$ has Gaussian concentration w....
- 2,772
8
votes
3
answers
660
views
The minimum-perimeter triangle of three sets of points
If $X$ and $Y$ are two sets of $n$ independent, uniformly sampled points in the unit square, then standard methods can show that the expected minimum distance between points in $X$ and $Y$ is ...
- 4,049
8
votes
3
answers
1k
views
Expected distance between two points in the plane
Let $f(x)$ be a continuous probability distribution in the plane. It is obvious that if $X$ and $X'$ are two independent random samples from $f$, then $\mathbf{E}(\|X - X'\|) \leq 2 \mathbf{E}(\|X\|)$...
- 83
8
votes
4
answers
2k
views
How to interpret couplings in optimal transport?
Let $\mu$ and $\nu$ be two measures on some (at least measurable) space $X$. In optimal transport theory, Monge's problem to
$$ \text{minimize} \quad \int c(x,T(x))\mu(dx) \quad \text{over measurable ...
- 309
8
votes
2
answers
256
views
What is the probability that these sets intersect?
Let $A$ be the subset of $\mathbb{R}^n$ defined by $A=\{x\in\mathbb{R}^{n}:|x_{1}-x_{n}|+\sum_{i=1}^{n-1}|x_{i+1}-x_{i}|\leq d\}$ for a given $d$. Next, sample a point $p$ uniformly in the unit cube, ...
- 4,049
8
votes
1
answer
314
views
Longest induced cycles in random geometric graphs near criticality
We make a random geometric graph $X(n;r)$ as follows. Choose $n$ points uniformly, independently, in the unit square $[0,1]^2$, for vertices, and then connect a pair of vertices $\{ p,q \}$ by an edge ...
- 7,857
8
votes
1
answer
270
views
Sizes of connected components from a random choice in a grid
This is inspired by the illustration in this recently updated question. So we take a (fairly big) $n$ and an $n \times n$ grid where we draw at random one diagonal in each of the $1 \times 1$ squares. ...
- 13.4k
8
votes
0
answers
257
views
Variations on Gauss' trick
Cross-posted from MSE. This question is inspired by these two:
Non-trivial values of error function erf(x)?
Where is the mass of a hypercube?
Upon reading these two, I realized there might be a ...
- 956
8
votes
0
answers
183
views
Can the GUE be thought of as a uniform point in a high-dimensional polytope
I have thought about this question for a long time and could only find partial answers.
The Gaussian Unitary Ensemble (or GUE) is the eigenvalues of a random Hermitian matrix with complex Gaussian ...
- 22.8k
7
votes
1
answer
318
views
Finding a short path using $(0.99n)!$ permutations
Suppose I have $n$ points $x_1,\dots,x_n$ that are all independent uniform samples in the unit square, and I'd like to find a short path (in terms of Euclidean length) that touches all of them (a ...
- 4,049
7
votes
1
answer
509
views
An order statistics problem with some interesting geometry
Let $a_n$ be a given sequence of positive numbers, and $X_n$ a sequence of independent random variables with each $X_n$ uniformly distributed on $[0, a_n]$.
Question: Let $N \geq 2$ be an arbitrary ...
- 6,223
7
votes
2
answers
460
views
Gaussian Surface Area of Positive Semidefinite Cone
Let $\mathbb{R}^n$ be the Euclidean space and $A \subseteq \mathbb{R}^n$ be a sufficiently regular set, e.g., one that has smooth boundary or is convex. We define the $\epsilon$-neighbor of $A$ in the ...
- 1,127
7
votes
1
answer
757
views
Length of nearest neighbor path in travel salesman problem
Given $n$ nodes uniformly distributed in $[0,1]^2$, consider the nearest neighbor algorithm to solve traveling salesman problem, i.e., each time I select the nearest neighbor not visited so far as the ...
- 367
7
votes
1
answer
186
views
$d$-ball approximation for $d\gg 1$ with a convex hull of random points on its boundary
Given a $d$-ball $\mathcal{S}^{d}$, let $P_n$ a set of $n$ points selected uniformly at random on the boundary $\mathcal{S}^{d-1}$ of $\mathcal{S}^{d}$. Let $\mathcal{C}_n$ the convex hull of $P_n$. ...
- 1,677
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
0
answers
162
views
Approximating any convex shape in $\mathbb{R}^d$ with a polytope having $\mathrm{poly}(d)$ facets
We denote by $V(A)$ the $d$-volume of any convex set $A$. Furthermore, given any two convex sets $A,B\in\mathbb{R}^d$, we denote by $V_{A,B}$ the $d$-volume of the symmetric difference $V\left(A \...
- 1,677
7
votes
0
answers
122
views
Discrepancy of the finite approximation of the Lebesgue measure
Let $\mu$ be a probabilistic measure on the unit square $Q$ which is the average of $N$ delta-measures in some points in this square; let $\lambda$ denote the Lebesgue measure on $Q$. What is the rate ...
- 109k
7
votes
0
answers
209
views
Stabbing disks in space, or: Galactic alignment
I have a collection of $n$ unit-radius disks in $\mathbb{R}^3$, whose centers are
random within a sphere of radius $R>1$, and which are each oriented randomly.
I'd like to find a line $L$ that ...
- 151k
6
votes
2
answers
702
views
2D closed convex shape which minimizes average distance between points
For a 2D closed convex shape, with metric $d$ and fixed area $A$, we can calculate the average distance between random (interior) points. For different shapes, we will get different values for this ...
6
votes
1
answer
333
views
Trasportation metric (AKA Earth-Mover's, Wasserstein, etc.) as "natural" / "induced"?
Context: Given a discrete finite metric space $X$ (in my case X={0,1}$^n$ with the Hamming/L$_1$ distance), I need to define the natural or canonical metric on the set of all probability distributions ...
- 111
6
votes
2
answers
568
views
Number of neigbour Voronoi cells for a random set of points on S^k or cube [-1, 1]^k?
Consider $S^k \subset R^{k+1} $. Sample $N$ points by say uniform distribution. (Example k=120, N=2^24, i.e. N>>k ).
Consider Voronoi cell around each point.
How many neighbours would a cell have ...
- 24.9k
6
votes
2
answers
497
views
Average distance of the mean of $n$ random complex numbers in a unit disc
Let $z_1,z_2,\dots,z_n$ be $n$ complex numbers distributed uniformly and randomly over the unit disc $x^2+y^2 \leq 1$. Let $z$ be the complex number defined by the mean of the of these numbers,that ...
- 826
6
votes
1
answer
180
views
Expected value of the length of the shortest non-zero vector in a lattice?
$\DeclareMathOperator\SL{SL}$What is the expected value of the length of the shortest non-zero vector in a (unimodular) lattice? I.e., let $G=\SL_n(\mathbb{R})$ with Haar measure $\mu$, $\Gamma=\SL_n(...
- 609
6
votes
1
answer
718
views
What is the distribution of the maximum nearest-neighbor distance of a point cloud sampled from a solid body like?
Let $\mathcal{B} \subseteq \mathbb{R}^n$ be an $n$-dimensional solid body. Assume that we sample $N$ points, say $S = \{ x_1, ..., x_N \}$, from $\mathcal{B}$ uniformly at random. Consider the ...
6
votes
1
answer
330
views
Best and worst centrally symmetric convex covering shapes
Suppose you have a centrally symmetric convex 2D shape $C$ of area $A$, and you randomly throw
down copies of $C$ on the plane so that each $C$-center lies within a given unit square $S$,
until $S$ is ...
- 151k
6
votes
1
answer
261
views
Area of $n$-sphere contained outside $\ell_1$ ball
For a given $r>1$, what is the surface area of $\mathbb S^{n-1}$ (the sphere of radius 1 in $\mathbb R^n$) which is contained outside of the $\ell_1$ ball of radius $r$? Or equivalently, if $X\sim ...
6
votes
1
answer
525
views
Wasserstein geometry of measures on manifolds related to the generalized Legendre transform and $d^2/2$-convexity
Let $(M,g)$ be a fixed closed Riemannian manifold, normalized to have volume 1. We'll write $d_M(x,y)$ for the (geodesic) distance between two points $x,y\in M$. I'm interested in the following class ...
- 7,197
6
votes
1
answer
424
views
Probability of intersecting a rectangle with random straight lines
We are given a rectangle $R$ with sides lengths $r_1$ and $r_2$, contained in a square $S$, with sides lengths $s_1=s_2\ge r_1$ and $s_2=s_1\ge r_2$. $R$ and $S$ are axis-aligned in a cartesian plane $...
- 1,677
6
votes
1
answer
273
views
Proof of a statement from Steele's "Probability theory and combinatorial optimization"
I am reading "Probability theory and combinatorial optimization" by J.M. Steele and am hung up on a statement made in Section 2.2 of Chapter 2, "Easy size bounds", in which it is stated (paraphrasing ...
6
votes
1
answer
396
views
Does a metric refine the weak-* topology on a dual space?
Let $X$ be a topological affine space over $\mathbb C$, with no additional assumptions. Let $X^*$ denote its dual space of continuous affine functionals $X \to \mathbb C$, equipped with the weak-$*$ ...
- 8,512
6
votes
0
answers
197
views
What are compact manifolds such that GROWTH (of spheres volumes) is well approximated by the Gaussian normal distribution?
Consider some compact Riemannian manifold $M$. Fix some point $p$.
Consider a "sub-sphere of radius $r$" - i.e. set of points on distance $r$ from $p$.
Consider growth function $g(r)$ to be ...
- 24.9k
6
votes
0
answers
281
views
Covariance operator analogue for manifolds and respective measure manifolds
Assume $E$ is a connected riemannian manifold with geodesic metric space structure given by $d$ and $P$ is a probability measure over $E$ with Borel sigma-algebra given by this metric structure. Also ...
- 519
5
votes
2
answers
472
views
Product of random diagonals on the unit circle
Let $P_1, P_2, ..., P_n$ be points randomly placed on a unit circle from a uniform distribution. Consider the product $D$ of all pairwise distances:
$D=\displaystyle \prod_{1\leq i < j \leq n} \...
- 413
5
votes
2
answers
245
views
Differentiability of the map $x\mapsto \delta_x$ in the Arens-Eells/Lipschitz-free space
$\DeclareMathOperator\AE{AE}\DeclareMathOperator\Lip{Lip}$Let $\AE(X)$ denote the Arens-Eells space on a Banach space $X$. Consider the map:
$$
\begin{aligned}
\delta: X & \rightarrow \AE(X)
\\
x&...
5
votes
1
answer
313
views
What is the probability that a random chord in a sphere touches opposite hemispheres?
(edited) Consider the unit sphere $\mathbb{S}^2\subset \mathbb{R}^3$, and its upper $(z>0)$ and lower $(z<0)$ hemispheres.
Draw two independent, uniformly distributed points $X,Y$ on $\mathbb{S}^...
- 223
5
votes
1
answer
389
views
Maximizing $\iiint|(x-z)\times(y-z)|d\mu d\mu d\mu$ over probability measures on the unit circle
What probability measure(s) maximize the quantity $\iiint_{\mathbb{S}^1}|(x-z)\times(y-z)|d\mu(x)d\mu(y)d\mu(z)$?
The answer appears to be uniform measure, since informally it appears better to have ...
- 3,209
5
votes
1
answer
928
views
Hausdorff distance is a lower (or upper bound) for what probability metric?
In a metric space $X=(X, d)$, given a probability measure $\mu$ and two subsets $A$ and $B$ of positive measure, it's not hard to prove that
$$
d(A, B) \le W(\mu|_A, \mu|_B),
$$
where
$d(A, B):= \...
- 6,853
5
votes
2
answers
1k
views
Inequality involving probability measures [closed]
I have been working on a problem(alternate minimization) where I want to establish an inequality in which I am stuck.
An $\alpha$- parameterized version of the divergence(Kullback-Leibler) takes the ...
- 779