All Questions
Tagged with pr.probability mg.metric-geometry
223 questions
1
vote
1
answer
100
views
$L^p$-barycenters via continuous selectors
Let $\mathbb{P}$ be a Borel probability measure on $\mathbb{R}^n$ with $\int_{x \in \mathbb{R}^n} \|x\|^p\mathbb{P}(dx)<\infty$. For which $p\in [1,\infty)$ (other than $p=2$) is the following ...
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&...
0
votes
1
answer
146
views
Upper bound of Wasserstein distance given by subvariables of codim 1
recently I am considering the upper-bound of Wasserstain distance. Say we have random vectors $X,Y$ of dimension $n$, and let $\tilde{X}_i (\tilde{Y}_i,$ resp.) be the $(n-1)$-dim random vector of $X (...
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 ...
2
votes
1
answer
245
views
Union bound over infinitely many events
Let $p_1, ... ,p_n$ be chosen independently from the uniform distribution on the unit torus $[0,1]^2$.
I want to prove a theorem of the form: "With high probability, every circle of radius $r$ ...
1
vote
1
answer
138
views
Least square assignment and hyperplanes
Let $S$ be a finite set of points in $\mathbb{R}^{d}$, $c(s) \in [0,1]$ such that $\sum_{s \in S} c(s) = 1$, $\rho$ continuous and non-vanishing probability distribution on $[0,1]^{d}$ and $\mu $ ...
4
votes
1
answer
567
views
Random graphs and Benjamini-Schramm convergence
I am looking for literature on the question whether a randomly chosen sequence of $k$-regular graphs converges in the Benjamini-Schramm sense to the universal covering with probability one.
There are ...
3
votes
1
answer
206
views
Random planes separating points in $\mathbb{R}^3$
We are given a unit origin-centered sphere $S$ in $\mathbb{R}^3$, and three points $\mathbf{x},\mathbf{y},\mathbf{z}\in S$. Let $\mathbf{h}$ be a point selected uniformly at random from $S$ and let $H$...
1
vote
1
answer
117
views
Modulus of continuity of parameterizing Wasserstein
Let $x_1,\dots,x_n\in X$ some Polish space $X$ and let $\Delta$ be the probability simplex in $\mathbb{R}^n$. Consider the map sending every $(w_1,\dots,w_n)\in\Delta$ to the finitely supported ...
2
votes
1
answer
151
views
Given an input point in $\mathbb{R}^n$, select (one of) the closest point(s) from a fixed large set of points given in advance
We are given a set $S$ of $m\gg 1$ points in $\mathbb{R}^n$.
In the problem I am trying to solve, in a sequential fashion, we obtain a new point $p_r\not\in S$ at each round $r\ge 1$ and the goal is ...
0
votes
0
answers
113
views
How much a probability distribution is non-uniform in a convex subspace of $\mathbb{R}^d$?
I know a number of (standard and well known) ways to measure the distance between two probability distributions and, more in general, to quantify how much one is far from another.
Could you please ...
3
votes
1
answer
321
views
Is disintegration continuous?
Let $X,Y$ be Polish spaces and suppose that $X$ is compact. Denote by $\mathcal{Mes}(X,\mathcal{P}(X\times Y))$ the set of (Borel) measurable functions from $X$ to the set of Borel probability ...
2
votes
0
answers
174
views
Random sets of points and hyperplanes in high dimensions
We are given a set $X$ of $n$ points $\mathbf{x}_1, \mathbf{x}_2, \ldots, \in\mathbb{R}^d$ selected uniformly at random from the unit origin-centered ball $\mathcal{B}^{d}$.
Consider the random ...
1
vote
1
answer
92
views
Geometric sampling problem in the Euclidean space in high dimensions
Let $T$ be the triangle whose vertices are three given points $\mathbf{x}, \mathbf{y}, \mathbf{z}\in\mathbb{R}^d$.
Question: What computationally efficient strategy can we use to sample a point $\...
1
vote
2
answers
197
views
Sampling method for a specific distribution in high dimensions
We are given a set $X$ of $n$ points $\mathbf{x}_1, \mathbf{x}_2, \ldots, \mathbf{x}_n\in\mathbb{R}^d$, where $d\ll n$. Given any point $\mathbf{p}$ on the unit $(d-1)$-sphere $\mathcal{S}$, we define
...
2
votes
1
answer
404
views
Euclidean distance bound with geometric constraints
Let $S_n$ be a set of $n$ points belonging to $\mathcal{B}_d:=\{\mathbf{x}\in\mathbb{R}^d:\|\mathbf{x}\|_2\le 1\}$, where $d\ll \log(n)$.
Let $s_n$ and $\ell_n$ be respectively defined as follows:
$$...
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 $...
2
votes
2
answers
379
views
Probabilistic combinatorial optimization problem on the distances between pairs of points in $[0,1]$
Let $S$ be a set of $n \gg 1$ points lying on the interval $[0,1]$. Given a point $p\in[0,1]$, let $S_p\subseteq S\times S$ be the set formed by all pairs of points $(x,y)$ with $x,y\in S$, such that ...
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 ...
1
vote
1
answer
1k
views
Closed-form upper-bounds for Wasserstein distance between finite measures
Let $x_1,\dots,x_n,y_1,\dots,y_n\in \mathbb{R}$ and such that $x_i\neq x_j$ and $y_i\neq y_j$ if $i\neq j$. Let $a,b$ be elements of the probability n-simplex. Define the measures $\mu\triangleq \...
4
votes
1
answer
218
views
Mass distributions for high dimensional simplex and cross polytope
In this question, it is shown that the radial mass distribution of an $n$-cube (i.e. the probability density for the distance from a point selected uniformly from within an $n$-cube to the cube's ...
0
votes
1
answer
289
views
Dither in Leech lattice quantization!
Can you please help me how to generate a dither signal $\mathbf{U}$, where $\mathbf{U}$ is a random vector of length 24 that is uniformly distributed over the Voronoi region of the Leech lattice.
Best,...
11
votes
0
answers
307
views
Entropy, magnitude, diversity of finite metric spaces in number theory
I was reading the article by Tom Leinster, (Maximizing
diversity in biology and beyond, arXiv link), and find it very interesting.
Since I was searching for entropies of finite metric spaces I found
...
2
votes
3
answers
290
views
Geometric probabilistic problem on triangles on a plane
We are given a triangle $T$ on a plane $P$, with sidelengths $a$, $b$ and $c$, where $c \ge b \ge a > 0$. A straight line $L$ on $P$ is selected uniformly at random from the set of all the ...
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}^...
3
votes
0
answers
132
views
Probability that a Voronoi cell contains exactly k random points
Consider two independent point processes in the unit square $[0,1]^2$. The two point processes are identically independent and typically binomial/Poisson. One, say $\Phi^*$, is used to generate a ...
19
votes
1
answer
448
views
Precise estimate for probability an $n$-point set has diameter smaller than $1$
This question was inspired by an earlier question that I answered but would like a more precise bound for.
Consider random points $x_1, \dots, x_n$ in the unit ball in $\mathbb R^d$, uniformly and ...
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. ...
1
vote
0
answers
113
views
Metrics on the space of distributions in terms of p.d.fs
If two probability distributions (on the same measure space) are s.t they have p.d.fs and the $L^1$ distance between the p.d.f.s is large, then is there a choice of a ``nice" metric $d_{\rm ...
1
vote
0
answers
184
views
Bounding the total variation metric between Gaussian mixtures
Let $\mathcal{P}(\mathbb{R}^d)$ the space of probability measures on $\mathbb{R}^d$ with total variation metric $\delta$, fix $k \in \mathbb{N}$, and let $\mathcal{P}'\subset \mathcal{P}(\mathbb{R}^d)$...
60
votes
1
answer
7k
views
Probability that a stick randomly broken in five places can form a tetrahedron
Edit (June 2015): Addressing this problem is a brief project report from the Illinois Geometry Lab (University of Illinois at Urbana-Champaign), dated May 2015, that appears here along with a foot-...
2
votes
0
answers
159
views
Maximizing $\iiint|(x-z)\times(y-z)|d\mu d\mu d\mu$ over probability measures on the unit sphere
This is a follow-up question to the one asked here (the unit circle case). What probability measure(s) maximize the quantity $\iiint_{\mathbb{S}^2}|(x-z)\times(y-z)|d\mu(x)d\mu(y)d\mu(z)$?
The ...
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 ...
26
votes
3
answers
11k
views
L1 distance between gaussian measures
L1 distance between gaussian measures: Definition
Let $P_1$ and $P_0$ be two gaussian measures on $\mathbb{R}^p$ with respective "mean,Variance" $m_1,C_1$ and $m_0,C_0$ (I assume matrices have full ...
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 ...
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):= \...
3
votes
0
answers
253
views
Metric ($f$-divergence) on space of probability measures that satisfies pythagorean theorem
Let $E$ be a polish space, $\mathcal{P}(E)$ the Borel probability measures on $E$ with the topology of weak convergence and $\mathcal{Q} \subset \mathcal{P}(E)$ a convex and compact set.
First, the ...
3
votes
1
answer
473
views
On 4 random points in a rectangle [closed]
Given a bounded rectangular area, I generate 4 random points. What is the probability that the fourth point lie within a triangle formed the first 3?
How would I attack this problem? The goal is to ...
17
votes
3
answers
923
views
Random permutations from Brownian motion
Let $B(t)$ be a Brownian motion. The ordering of $(0, B(1), ..., B(n-1)) $ is a random permutation in $S_n$. This is not uniform for $n>2$ since the probabilities of the identity permutation $[123.....
3
votes
0
answers
234
views
Are random convex polygons on a sphere themselves sphere-like?
Say $\mathbb{R}^n$ is divided by $k>n$ randomly chosen hyperplanes. Each connected region away from the hyperplanes is the intersection of $k$ half-spaces, so it is a convex cone. It is known that ...
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....
1
vote
1
answer
242
views
Barycenter Map on Wasserstein Space
Let $(X,d)$ be a complete separable metric space, $P_1(X,d)$ be the set of Radon probability measures on $X$ satisfying
$$
P_1(X,d)\triangleq \left\{
\nu:\,(\exists x_0\in X)\, \int_{x\in X} d(x,x_0)d\...
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$ ...
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 ...
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 ...
11
votes
1
answer
393
views
Growing a chain of unit-area triangles: Fills the plane?
Define a process to start with a unit-area equilateral triangle,
and at each step glue on another unit-area triangle.
$50$ ...
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})$$
"...
2
votes
1
answer
110
views
A questions concerning Laguerre/Voronoi tessellations
Fix $n>1$ distinguished points $x_1,\ldots, x_n\in \mathbb R^d$, the Voronoi tessellations are the subsets $V_1,\ldots V_n\subset\mathbb R^d$ defined by
$$V_k~~ := ~~ \big\{x\in\mathbb R^d:\quad |...
1
vote
1
answer
239
views
Probability of two Points being divided by an high-Dimensional Hyperplane
I have two points $x_1,x_2 \in \mathbb S^n $ which are distant $d$ from each other, where $d<<1$.
I also have a vector $v$ sampled uniformly at random from $\mathbb S^n$.
What is the ...
10
votes
3
answers
2k
views
Mean maximum distance for N random points on a unit square
Following up on Mean minimum distance for N random points on a one-dimensional line and Mean minimum distance for N random points on a unit square (plane), I have the following questions.
Given N ...