All Questions
Tagged with pr.probability mg.metric-geometry
223 questions
10
votes
2
answers
847
views
Minimum separation among $m$ random points on an $n$-dimensional unit sphere
Consider $m$ points $v_1, \ldots, v_m \in R^{n}$, which are uniformly distributed on the $n$-dimensional unit sphere $S^{n-1} = \{v:\|v\|_2 = 1\}$. Let the minimum separation be
$$
\rho = \min_{i,j\in{...
CommunityBot
- 1
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 ...
CommunityBot
- 1
2
votes
2
answers
810
views
Terrain Generation: Infinite 2D space filled with Diffusion-limited aggregation clusters?
Disclaimer: I don't have a deep understanding of fractals or any higher math, I'm just personally interested in it, so please excuse me if I'm using wrong terms or if I'm being inaccurate. Making ...
14
votes
2
answers
319
views
Shortest path through $n^{1/3}$ points out of $n$
Say I sample $n$ points uniformly at random in the unit cube in $\mathbb{R}^3$, and then I look for the shortest path through $n^{1/3}$ of those points (rounding up, say). What happens to the length ...
- 28k
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
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
1
vote
1
answer
524
views
Convergence in the Wasserstein metric and the square root function
Let $f$ be a smooth probability distribution on the unit square $S$ such that $f(x)>0$ on $S$. Let $\{g_i\}$ be a sequence of smooth probability distributions such that $g_i(x)>0$ on $S$ as ...
CommunityBot
- 1
1
vote
2
answers
1k
views
Pairwise distance distribution for point clouds (normal distribution) [closed]
I have a point cloud (2D for now) of $N$ normally distributed points (with a certain $\sigma$).
My first question would be how the pairwise distance distribution looks (just by chance I discovered a ...
CommunityBot
- 1
17
votes
2
answers
1k
views
A probability distribution in n dimensional space which its projection on any line is a uniform distribution?
Does there exist, for any natural $n$, a probability distribution in $\mathbb{R}^n$ whose projection on any line is a uniform distribution?
- 3,085
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 ...
CommunityBot
- 1
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 ...
CommunityBot
- 1
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 ...
- 2,158
0
votes
0
answers
320
views
Gromov-Hausdorff distance measure between minimum spanning trees
I am trying to compare minimum spanning trees through time. I have two questions:
1-Is it possible to measure the similarity between two minimum spanning trees with Gromov-Hausdorff distance measure ...
- 1
32
votes
5
answers
6k
views
What is a good method to find random points on the n-sphere when n is large?
As part of a more complex algorithm, I need a fast method to find random points of the n-sphere, $S^n$, starting with a RNG (random number generator). A simple way to do this (in low dimensions at ...
CommunityBot
- 1
21
votes
2
answers
3k
views
A measure on the space of probability measures
This question was originaly posted in the stackexchange https://math.stackexchange.com/questions/1226701/a-measure-on-the-space-of-probability-measures but since it only got a comment I decided to ...
- 7,197
19
votes
2
answers
569
views
Repeated random two-steps in $\mathbb{R}^3$: unbounded?
I created a random isometry $T$ of $\mathbb{R}^3$ by generating
a random orthogonal matrix $M$,
uniformly distributed among all such,
and a random displacement $v$, whose coordinates
are drawn from a ...
- 151k
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
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_{\...
CommunityBot
- 1
3
votes
0
answers
119
views
Probability that a random projection doesn't reduce the distance of a point from a subspace too much
Consider the natural uniform measure (is it called the Haar measure?) on the set of $(n-k)$-dimensional subspaces of $R^n$. We are given a $d$-dimensional affine subspace $U$ (think of $d, k \ll n$; ...
- 111
2
votes
0
answers
157
views
Better Sobolev inequality holds in this case when assuming doubling and Poincare inequality?
Let $X$ be a Polish space and let $m$ be a locally finite Borel measure on $X$.
Let $\epsilon$ be a strongly local, regular Dirichlet form on $L^2(X,m)$ with Domain $V :=\{f\in L^2(X,m):\epsilon(f)&...
- 471
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? ...
- 6,210
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 ...
CommunityBot
- 1
1
vote
1
answer
337
views
Estimating the volume of a union of balls
Let $\{ B_i \}_{i=1}^n$ be a set of $n$ ball in the unit cube $C$ of dimension $d$.
If I want to estimate
$$
\frac{ \lambda \left( \cup B_i \right) }{\lambda\left( C \right) }, \tag{1}
$$
where $\...
CommunityBot
- 1
1
vote
0
answers
211
views
Quadrilaterals from a Unit Stick
This question could be seen as a coordinate-free variant of Sylvester's Four Point Problem (cf e.g. http://mathworld.wolfram.com/SylvestersFour-PointProblem.html):
Suppose one are given an ...
- 13.2k
18
votes
0
answers
667
views
The lonely molecule
Suppose $n$ air molecules (infinitesimal points) are bouncing around in
a unit $d$-dimensional cube, with perfectly elastic wall collisions.
Let $k=n^{\frac{1}{d}}$.
For example, in 3D, $d=3$, with $n=...
CommunityBot
- 1
30
votes
2
answers
1k
views
Shortest path through $\sqrt{n}$ points out of $n$
Say I sample $n$ points uniformly at random in the unit square, and then I look for the shortest path through $\sqrt{n}$ of those points (rounding up, say). What happens to the length of this path as ...
- 28k
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 ...
- 1,676
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 ...
- 156
12
votes
1
answer
2k
views
Limit of distance between two random points in a unit-radius $n$-sphere
This is a companion contrast to the earlier analogous question for unit $n$-cubes,
where the answer (provided by several respondents) is $\infty$ .
What is the limit, as $n \to \infty$, of the ...
CommunityBot
- 1
11
votes
2
answers
3k
views
Limit of distance between two random points in a unit $n$-cube
What is the limit, as $n \to \infty$, of the expected distance between two
points chosen uniformly at random within a unit edge-length hypercube
in $\mathbb{R}^n$?
For $n=1$, the average distance ...
- 29.8k
15
votes
2
answers
571
views
Spearing rolling hula hoops
Or: Stabbing rolling disks.
Imagine there are $n$ unit-diameter disks rolling between $x=0$ and $x=d$,
reflecting off either end.
The disk centers start at a random location within $[\frac{1}{2}, d-\...
- 6,206
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 ...
- 24.8k
16
votes
3
answers
2k
views
Expected Degree of a vertex in Delaunay Triangulations
Assume you have a Poisson point process of constant intensity $\lambda$ in the Euclidean plane. From this point process we construct the Delaunay triangulation (or the Voronoi tessellation for that ...
- 6,210
0
votes
1
answer
136
views
What is the area of the piece of an $n$-sphere within a given angle of a vector? [closed]
Let $x$ be the unit vector $(1,0,0,\ldots,0)$ in $\mathbb{R}^n$, and let $A(\theta)$ be the subset of $\mathcal{S}^{n-1}$ whose angle to $x$ is less than $\theta$, i.e.
$$ A(\theta) = \left\{ y \in \...
CommunityBot
- 1
17
votes
2
answers
1k
views
What kind of probability distribution maximizes the average distance between two points?
If $f$ is a probability distribution on the unit disk in $\mathbb{R}^2$, and $X_1$ and $X_2$ are two independent samples from $f$, then what is the distribution $f^*$ that maximizes the average ...
- 32.4k
0
votes
0
answers
404
views
When is the median closest nearest-neighbor distance larger than the mean closest nearest-neighbor distance?
Consider a random Poisson process in an $d$-dimensional cube of arbitrary size (alternatively, consider an arbitrarily large $(d-1)$-dimensional sphere in an $d$-dimensional space). If we have a ...
0
votes
0
answers
104
views
Minimum distance larger than a fraction $f$ of the closest nearest-neighbor distances for points placed by a random Poisson process?
Consider a random Poisson process on arbitrarily large volume in $R^d$ enclosed by an $R^{(d-1)}$ dimensional sphere. The process terminates when a density of points $\rho$ is achieved (letting $N$ ...
- 1
21
votes
2
answers
1k
views
Probability that a convex shape contains the unit ball
This probability problem seems interesting and I don't know if it has been solved before.
If you pick $n$ points uniformly at random from the surface of a $d$ dimensional sphere of radius $r>1$ ...
2
votes
2
answers
331
views
what's the best way to characterise the distribution of prime elements in simple perfect squared squares
DEFINITIONS: A squared rectangle is a rectangle dissected into a finite number, two or more, of squares, called the elements of the dissection. If no two of these squares have the same size the ...
0
votes
1
answer
376
views
Probability of disc-disc overlap for discs placed with uniform probability on a surface until a density $\rho$ is achieved
Imagine I place discs of radius $r$ on a two-dimensional plane, selecting their positions with uniform probability across the surface of the plane, and stop when I reach a disc density $\rho$. As a ...
- 6,210
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 ...
- 14.4k
0
votes
1
answer
89
views
Is a $CD(K,\infty)$ space a length space?
Let $(X,d)$ be a complete and separable metric space endowed with a nonnegative Borel measure $\mu$ with support $X$ and satisfying
\begin{eqnarray}
\mu(B(x,r))<\infty,\quad\mbox{for every }x\in X\...
- 14.4k
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 ...
- 96.4k
2
votes
1
answer
121
views
Expected length of a certain kind of nearest-neighbor graph
Suppose I have sets of points $Z_1,\dots,Z_N$, such that $|Z_i|=m$ for all $i$, and where all $m\times N$ points are independently distributed uniformly at random in the unit square. Can someone give ...
- 6,210
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
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-$*$ ...
- 3,584
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
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
129
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
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$-...
- 61.9k