Skip to main content

All Questions

Filter by
Sorted by
Tagged with
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 ...