All Questions
Tagged with pr.probability mg.metric-geometry
223 questions
5
votes
1
answer
430
views
Volume of a shape whose boundary consists of portions of spheres symmetrically placed about the origin in $d\gg 1$ dimensions
We are given a convex shape $S$ in the $d$-dimensional Euclidean space, whose boundary is formed by portions of $2d$ different spheres, one portion per sphere. The radius of each sphere is the same, $...
- 1,677
5
votes
2
answers
474
views
Another graph characteristic
This question concerns a method of drawing graphs and a graph characteristic about which I want to learn more.
Consider a connected directed graph with at least one node with in-degree 0 and one node ...
- 9,720
5
votes
1
answer
698
views
Lower bound for mutual inner products of N random unit vectors in $\mathbb{R}^n$, N > n
I have $N$ independent random unit vectors $\{v_i\}$ in $\mathbb{R}^n$, where N > n. I need a concentration inequality of the form
$$\text{P}(|v_i \cdot v_j| > \epsilon \,\,\,\, \forall i, j = 1, \...
- 337
5
votes
1
answer
1k
views
Probability distribution or the distance between two points in $n$-dimensional Euclidean space after a random perturbation of one point
Take two points, $p_0$ and $p_k$, in $n$-dimensional Euclidean space, where $d(p_0,p_k)$ is the distance between the points. Now, draw an $n$-sphere of radius $r$ centered on $p_0$ and uniformly ...
- 55
5
votes
1
answer
138
views
Complexity and length
Suppose we define continuous piecewise linear functions $f$ on $[0,1]$ using your favorite programming language, or by finite automata, or by any other suitable machine. Define the complexity $H(f)$ ...
- 2,934
5
votes
0
answers
184
views
Question about $n$ random points in a regular polygon, and a limiting probability
Suppose we choose $n$ uniformly random points in a disk, then draw the smallest circle that encloses all of those points. There is evidence suggesting that the probability that the enclosing circle is ...
- 3,567
5
votes
0
answers
74
views
Concentration bound on additive functions with constraints
Given a family of sets $F \subseteq P(\{1,\ldots,n\})$. I define the function $f_F:[0,1]^n \rightarrow R$ to be $f_F(x_1,\ldots,x_n)= \max_{S \in F} \sum_{j \in S} x_j$.
Given a series of independent ...
- 107
5
votes
0
answers
266
views
Throwing darts at a barn and putting a bullseye around them in higher dimensions
Let $X \in \mathbb R^d$ be a large domain (a ball of radius $r$ for $r$ large should suffice)
Let $B$ be a ball of radius $1$.
Consider the ratio
$$ \frac{ \left| \left\{ x_1,\dots,x_n \in X \mid ...
- 148k
5
votes
0
answers
275
views
Is there a connection between |roots| $\rightarrow$ 1 and Gromov's waist theorem?
Recent questions showed that roots of a random polynomial tend to lie on the
unit circle ("Why do roots of polynomials tend to have absolute value close to 1?"; "Distribution of roots of complex ...
- 151k
4
votes
1
answer
263
views
Knotted TSP tours in 3D?
In the plane, the Euclidean TSP tour never crosses itself—it is always a simple polygon.
I am wondering if there is a similar constraint for the Euclidean TSP tour
of points in $\mathbb{R}^3$.
...
- 151k
4
votes
2
answers
2k
views
Selecting two random points inside a sphere which are a fixed distance apart
Without appealing to a guess-and-check approach, how might I select a pair of random points inside of a sphere of radius $R$ s.t. the points always a distance $d \leq R$ apart? Can the selected ...
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
2
answers
882
views
The probability distribution for vertex degree in a unit disc graph generated from random points on a plane
Imagine I cover an arbitrarily large plane with randomly placed points at some density $\rho$ s.t. the number of points in any randomly sampled area $A$ (of arbitrary shape and size) is $\approx A*\...
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 ...
- 956
4
votes
1
answer
193
views
A bound on the square distance of a random walk on undirected graph
Fact:
Let $G$ be an $n$-vertex undirected graph and $(X_s)_{s\in \mathbb N}$ a stationary random walk on $G$. Then for every $s\in \mathbb{N}$,
$ \mathbb{E}[d_G(X_s,X_0)^2] \le C s \log n $, for some ...
- 401
4
votes
2
answers
124
views
Simulating random sequential adsorption in reverse
Please consider two processes:
Process 1 - I simulate random sequential adsorption of discs on the unit square in the continuum limit, randomly selecting real number coordinates and rejecting the ...
- 73
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 ...
user130903
4
votes
1
answer
474
views
Wasserstein distance to the set of Gaussians ; Boltzman dissipation rate
I am interested in the $2$-Wasserstein distance for probabilities over ${\mathbb R}^n$,
$$W_2(\mu,\nu)=\left(\inf\int_{{\mathbb R}^n\times{\mathbb R}^n}|w-v|^2\pi(v,w)\right)^{1/2}$$
where the infimum ...
- 52.3k
4
votes
1
answer
133
views
Union of random half spaces cover a ray
Let $x, y \in \mathbb{R}^{n}$ be two fixed unit vectors with angle $\alpha \in (\frac{\pi}{2}, \frac{3\pi}{4})$. Define the positive half space associated with a vector $z$ to be $\mathcal{H}(z) = \{h ...
- 83
4
votes
1
answer
356
views
Random spherical caps cover a spherical cap
Let $S^{n-1}$ be the unit sphere in $n$ dimensional Euclidean space. Define the spherical cap at $x \in S^{n-1}$ with angle $\theta$ to be $C(x,\theta) = \{z \in S^{n-1} \mid z^\top x \geq \cos(\theta)...
- 83
4
votes
1
answer
275
views
Nontrivial lower bounds on Cheeger inequalities for Markov chains
For a reversible Markov chain $X_{t}$ on $\mathbb{R}^{n}$ with transition kernel $K$ and stationary distribution $\pi$, it is well-known that the `spectral gap' (basically, the size of $K$ when ...
- 51
4
votes
0
answers
52
views
Isomorphism of Wasserstein space implies isomorphism of base spaces?
Assume $(X_i,d_i)$ are polish spaces (or compact metric spaces) for $i=1,2$.
Further assume that the 1- Wasserstein spaces $(P_1(X_1),W_1)$ and $(P_1(X_2),W_1)$ are isometrically isomorphic. Does that ...
4
votes
0
answers
87
views
Statistics of random Voronoi S-tessellations
Given a locally finite set of points $\{x_1,x_2,\dots\}\subset\mathbb{R}^d$, the Voronoi cell of a point $x_{i}$, denoted by $C(x_{i})$, consists of all the points in $\mathbb{R}^d$ that are closer to ...
- 41
4
votes
0
answers
144
views
Approximation of a convex shape in the $d$-dimensional Euclidean space for $d\gg 1$
We are given a convex shape $C$ lying inside the hypercube $[0,1]^d$ in the $d$-dimensional Euclidean space. Let the volume of $C$ be $\tfrac12$ (I guess nothing changes for any other fixed constant ...
- 1,677
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
756
views
Tangent space and gradient on subspace of Wasserstein space given by finitely supported measures
Let $\mathcal{P}_2(M)$ be the 2-Wasserstein space over some Riemannian manifold $(M,g)$ (connected, complete, and without boundary). Let $\mathcal{FP}_2(M,n)$ be the subspace of probability measures ...
- 1,675
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
4
votes
0
answers
100
views
Asymptotics of the joint pdf of two sums of powers of independent $\mathcal U(0,1)$ random variables
As a warm-up in words: The sum of twelve uniform random variables is a classic approximation to a normal distribution. What is the joint pdf for the sum of their cubes and the sum of their fourth ...
- 128k
4
votes
0
answers
94
views
Finding closest set of K disjoint hyperspheres to a point in $\mathbb{R}^n$ with uniform radius
I am interested in the following problem: in $\mathbb{R}^n$, we have $N$ overlapping hyperspheres all with the same radius. Given a point $p$ in $\mathbb{R}^n$, the objective is to find the $K$ non ...
- 161
4
votes
0
answers
173
views
On understanding Discrete-Valued Stochastic Processes( time series, panel data )
It seems to me that a significant proportion of work in probability theory, statistics and machine learning are on understanding continuous-valued, relatively weakly dependent, or linear dependent ...
- 41
4
votes
0
answers
128
views
Metrized categories
Motivation: Let $\Gamma = (V,E)$ be a directed graph. To each edge $e \in E$, choose a value $\kappa^e \in \mathbb R$, representing the cost of transporting one unit of "stuff" through the edge. Let $\...
- 8,512
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 ...
- 133
3
votes
1
answer
197
views
Three-dimensional Apollonian spirals
Given mutually (externally) tangent spheres $S_1$, $S_2$, $S_3$, $S_4$, let $S_n$ be the unique sphere externally tangent to $S_{n-1}$, $S_{n-2}$, $S_{n-3}$, and $S_{n-4}$ for $n \geq 5$.
Let $P_{\...
- 19.7k
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,677
3
votes
1
answer
202
views
Diameter of $n$-unit-vector closed scribble
Suppose one creates a random, closed, likely self-crossing polygon
from $n$ unit-length vectors arranged head-to-tail,
randomly oriented except for the requirement
that their sum is zero (so the ...
- 151k
3
votes
1
answer
156
views
Concentration of measure on spheres with respect to a unitary of trace approximately zero
Cross-posted from MSE, where it hasn’t received any answer yet:
This question arose out of my attempt to understand how a unitary of trace approximately zero acts on the unit sphere of a $n$-...
- 2,830
3
votes
1
answer
218
views
Bounding the number of facets of a polytope to approximate a given convex shape in higher dimensions
We are given a convex shape $S$ lying inside the hypercube $[0,1]^d$ in the $d$-dimensional Euclidean space. Let the volume $V(S)$ of $S$ be $\tfrac12$ (I guess nothing changes for any other fixed ...
- 1,677
3
votes
1
answer
350
views
Talagrand's inequality for L1 norm
I have a series of $n$ independent random variables $X_1,\ldots, X_n$, each with the support $[0,1]$, and a monotone convex function $f:\mathbb{R}^n \rightarrow \mathbb{R}$ that is 1-Lipshitz in L1 ...
- 107
3
votes
1
answer
105
views
Asymptotic radius of the smallest enclosing ball
Let $X_1,..., X_n$ be i.i.d. $d$-dimensional standard normal random variables, and let $R_n$ be the radius of the smallest ball containing $X_1,...,X_n$. What is known about the distribution of $R_n$ ...
- 724
3
votes
1
answer
187
views
Moment matching on the standard simplex
Let $\vec{\mu}_1, \vec{\mu}_2,\ldots, \vec{\mu}_k \in \Delta^{d-1}$ be $k\ (k\geq 2)$ distinct vectors on the standard simplex, where
$$\Delta^{d-1} = \{\vec{\mu}\in R^{d}:\| \vec{\mu}\|_1 = 1,\mu_j \...
- 1,127
3
votes
2
answers
207
views
Connectivity of points sampled in a grid
Suppose that I partition an $n\times n$ square into $n^2$ squares $S_1 ,\dots, S_{n^2}$ each of area $1$, and then I sample a point $X_i$ uniformly at random in each $S_{i}$. Now fix a radius $r$ and ...
- 31
3
votes
1
answer
443
views
What is the expected value for this
If there are $8$ random points in the plane whose horizontal coordinate
and vertical coordinate are uniformly distributed on the open interval
$\left(0,1\right)$, what is the expected largest size of ...
- 31
3
votes
1
answer
492
views
Random non-intersecting circles in the plane
If I give a finite region of $\mathbb{R}^{2}$ and place $k$ circles of radius $r(k)$ uniformly at random inside, are there any known results for the probability that the circles do not overlap? ...
- 903
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 ...
- 5,405
3
votes
1
answer
248
views
"Trapping" of discs after random sequential adsorption
Imagine I perform Random Sequential Adsorption (RSA) of discs of some radius $r$ on $[0, 1]^2$, eventually covering the surface to some density $Q \leq 0.543$ with $N$ total discs (where $\approx 0....
- 73
3
votes
0
answers
228
views
Are 1-Wasserstein and 2-Wasserstein distances between multivariate normal distributions equivalent?
The $p$-Wasserstein between two measures $\nu_1$ and $\nu_2$ on $X$ is given by
$$W^p_p(\nu_{1},\nu_{2})=\underset{\pi\in\Gamma(\nu_{1},\nu_{2})}{\inf}\int_{\mathbf{\mathcal{X}}^{2}}d(x,y)^p\pi(dx,dy)$...
- 1,058
3
votes
0
answers
187
views
Approximating any $d$-dimensional convex shape that occupies a constant fraction of its bounding box with a polytope having $\mathrm{poly}(d)$ facets
Given any convex set $A\in\mathbb{R}^d$, we denote by $V(A)$ its $d$-volume. Furthermore, given any two convex sets $A_1,A_2\in\mathbb{R}^d$, we denote by $V_{A_1,A_2}$ the $d$-volume of the symmetric ...
- 1,677
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 ...
- 137
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 ...
- 1,095
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 ...
