Questions tagged [geometric-probability]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
47 votes
7 answers
5k views

Intuitive proof that the first $(n-2)$ coordinates on a sphere are uniform in a ball

It is a classical fact that if $(x_1,\ldots,x_n)$ is a random vector uniformly distributed on the sphere $S^{n-1} \subseteq \mathbb{R}^n$, then the random vector $(x_1,\ldots,x_{n-2})$ is uniformly ...
Mark Meckes's user avatar
  • 11.2k
30 votes
8 answers
3k views

A variation of the law of large numbers for random points in a square

I uniformly mark $n^2$ points in $[0,1]^2$. Then I want to draw $cn$ vertical lines and $cn$ horizontal lines such that in each small rectangle there is at most one marked point. Surely, for a given ...
Nikita Kalinin's user avatar
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 ...
Kellar's user avatar
  • 335
30 votes
1 answer
1k views

Functional-analytic proof of the existence of non-symmetric random variables with vanishing odd moments

It is known that a random variable $X$ which is symmetric about $0$ (i.e $X$ and $-X$ have the same distribution) must have all its odd moments (when they exist!) equal to zero. The converse is a ...
dohmatob's user avatar
  • 6,716
27 votes
5 answers
2k views

Moments of area of random triangle inscribed in a circle

The $2m$th moment of the (random) area of the triangle whose vertices are three independent, uniformly distributed random points on the unit circle appears to be $((3m)!/(m!)^3)/16^m$. Can anyone ...
James Propp's user avatar
  • 19.4k
25 votes
1 answer
1k views

How random are unit lattices in number fields?

I was wondering how random unit lattices in number fields are. To make this more precise: If $K$ is a number field with embeddings $\sigma_1, \dots, \sigma_n, \overline{\sigma_{r+1}}, \dots, \...
felix's user avatar
  • 639
15 votes
2 answers
743 views

Random noncrossing chords of a circle

Suppose you generate random chords of a circle, with endpoints selected uniformly over the circumference, rejecting any chord that crosses a previously generated chord. The disk is then partitioned ...
Joseph O'Rourke's user avatar
14 votes
3 answers
4k views

How to generate random points in $\ell_p$ balls?

How do I feasibly generate a random sample from an $n$-dimensional $\ell_p$ ball? Specifically, I'm interested in $p=1$ and large $n$. I'm looking for descriptions analogous to the statement for $p=2$:...
Mitch's user avatar
  • 657
14 votes
2 answers
317 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 ...
Kellar's user avatar
  • 141
14 votes
0 answers
367 views

Will a unit disk be completely covered by randomly placed disks of area $\pi,\frac{\pi}{2},\frac{\pi}{3},\dots$ with probability $1$?

On a "bottom" disk of area $\pi$, we place "top" disks of area $\pi,\frac{\pi}{2},\frac{\pi}{3},\dots$ such that the centre of each top disk is an independent uniformly random ...
Dan's user avatar
  • 2,341
13 votes
1 answer
946 views

A disc contains many random points. Each point is connected to its nearest neighbor. What is the expectation of average cluster size?

A disc contains $n$ independent uniformly distributed points. Each point is connected by a line segment to its nearest neighbor, forming clusters of connected points. For example, here are $20$ random ...
Dan's user avatar
  • 2,341
13 votes
4 answers
528 views

Alignment of random points

Whenever I draw randomly about ten points, I see that there will be always 3 points that are "almost" collinear. This observation leads me to considering the following questions: Question 1: Suppose $...
Minh-Toan's user avatar
  • 131
12 votes
2 answers
898 views

The metric of the expected difference of random variables

Suppose we have a set of independent random variables $X_1,\ldots,X_n$ over $\mathbb{R}$. It is easy to see that $$d_{ij}=E[|X_i-X_j|]$$ satisfy the triangle inequality. Is there any study of such ...
jian's user avatar
  • 401
11 votes
6 answers
3k views

Marginal density of uniform spherical distribution

Suppose that $X$ is distributed uniformly in the scaled $n$-sphere $\sqrt{n} \mathbf{S}^{n-1} \subset \mathbf{R}^n$. Then apparently the distribution of $(X_1, \dots, X_k)$, the first $k < n$ ...
Drew Brady's user avatar
11 votes
2 answers
955 views

Clique sizes in a unit disk graph

This is a spiritual successor to a question that Peter Shor answered here: Generalized Euclidean TSP Are there any results known on the asymptotic behavior of clique sizes in a unit disk graph with ...
John Gunnar Carlsson's user avatar
11 votes
1 answer
304 views

Variant of an Expander graph: Probability that S random points cast a shadow/projection of size at most S/2 on each face of a cube.

Consider an integer cube of size $\sqrt{k} \times \sqrt{k} \times \sqrt{k}$, where $k$ is an asymptotically large perfect square number. Place k points in this cube at uniformly random locations, i.e.,...
codingTheorist's user avatar
10 votes
3 answers
1k 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 ...
Silvia's user avatar
  • 193
10 votes
4 answers
897 views

The distribution of the shortest path through $n$ points

In the big picture, I'd like to know: if I sample $n$ points uniformly at random in the unit square, what is the probability that the shortest path that visits each one of them is very small? More ...
Will Schaefer's user avatar
10 votes
1 answer
537 views

Can one use Brownian motion to prove that two manifolds are not conformally equivalent?

Let me start by a very simple example; consider the following question: "Let D1 be a square and D2 a rectangle (boundary included). View them as subsets of the complex plane. Does there exist a ...
Ritwik's user avatar
  • 3,235
10 votes
2 answers
790 views

Fitting a mesh to a density function

Suppose I have a probability density function defined on a region in the plane (in my case, the pdf is of the form $f(x) = \alpha\|x\|^{-\beta}$, and the region is the unit disk). For large $N$, is ...
John Gunnar Carlsson's user avatar
10 votes
2 answers
803 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{...
Minkov's user avatar
  • 1,117
10 votes
3 answers
5k views

Mean minimum distance for K random points on a N-dimensional (hyper-)cube

Given K points in a N-dimensional (hyper-)cube with all edges length 1. What is the expected minimal distance between 2 points. I found the 1-dimensional case in this topic: Mean minimum distance for ...
Ingdas's user avatar
  • 371
10 votes
1 answer
466 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$ ...
Steve's user avatar
  • 1,117
9 votes
2 answers
422 views

Density of a saturated random packing of congruent circles

The problem of the expected density of a saturated random packing of unit circles in the plane can be described as follows. In a circular region $C$ of a large radius pick a point at random and draw ...
Wlodek Kuperberg's user avatar
8 votes
3 answers
1k views

Taking points uniformly inside a general finite geometric domain

It is well known that if we want to take $n$ uniformly and randomly points inside a circle of radius $r$ and centered at the origin the following apparently correct approach for generating $x$ and $...
AgnostMystic's user avatar
8 votes
2 answers
253 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, ...
Tom Solberg's user avatar
  • 3,929
8 votes
2 answers
938 views

Approximation of Wasserstein distance between $p_\theta$ and $p_{\theta + d\theta}$

Given a parametric family of distributions $\{p_\theta\mid\theta \in \Theta\}$, one can show that under some regularity conditions, the following approximation is valid $$\operatorname{KL}(p_\theta\...
dohmatob's user avatar
  • 6,716
8 votes
3 answers
1k views

Introduction to information geometry and/or geometric control theory

Some background: I'vebeen searching for a research project to work through my grad studies and I found information geometry like a strong candidate but the amount of work out there is overwhelming. I ...
Santiago Gil's user avatar
7 votes
3 answers
2k views

Packing density of randomly deposited circles on a plane

Let's say that I have a rectangular two-dimensional surface of bounded dimensions, $[0,A]$ and $[0,B]$: Under "no overlap" constraints, I sequentially deposit circles of radii $r_c$ on this surface,...
user14324's user avatar
  • 309
7 votes
1 answer
753 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 ...
lchen's user avatar
  • 459
7 votes
1 answer
303 views

Iterating projections to random halfspaces

Consider the following process: Start with a set $S = \mathbb R^n$. Repeat $L$ times: choose a random orthonormal basis $u_1, \ldots, u_n$, and consider the cone $C = \{ \sum \alpha_i u_i : \alpha_i \...
Daniel Paleka's user avatar
7 votes
0 answers
137 views

Probability of landing inside the convex hull of previously sampled points

Let $\{X_i\}_{0\leq i\leq\infty}$ be i.i.d. random vectors in $\mathbb{R^d}$. I would like to show that the probability of one point being in the convex hull of the others goes to one with the number ...
Maxim's user avatar
  • 233
6 votes
3 answers
703 views

Expected absolute value of the average of two points from the disc

Looking at Average distance of the mean of n random complex numbers in a unit disc, I tried to figure out  what is the expected absolute value $|\frac{z_1 + z_2}{2}|$ of two numbers $z_1, z_2\in\...
Moritz Firsching's user avatar
6 votes
3 answers
1k views

The distribution of the number of chord intersections

This is a follow-up to this question: Given $n$ random chords of a circle, what is the distribution of the number of intersections? Random is defined by "endpoints uniform on the circle". Update ...
Igor Rivin's user avatar
  • 95.6k
6 votes
2 answers
1k views

Definition of random measures

Introducing the notion of a random measure, textbooks usually start with a locally compact second countable Hausdorff space. Where does this requirement come from? I would like to have a motivation ...
Henning's user avatar
  • 123
6 votes
1 answer
275 views

Local Lipschitzness of parameterization of Gaussians in Wasserstein space

Fix a positive integer $n$ and consider the $2$-Wasserstein space $\mathcal{P}_2(\mathbb{R}^n)$. Let $X$ be the cone of $n\times n$ symmetric positive semidefinite matrices with Frobenius norm and ...
Justin_other_PhD's user avatar
6 votes
2 answers
480 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 ...
AgnostMystic's user avatar
6 votes
1 answer
317 views

Almost evenly distributed spherical random vectors

Consider $n$ i.i.d spherically distributed random vectors $z_1 ,\cdots , z_n \sim \text{Unif}(\mathbb{S}^{d-1})$. What is the best lower bound on $n$ for which whp there exists a constant $c>0$ ...
Sina Baghal's user avatar
6 votes
3 answers
293 views

Probability of random geodesics on the half-sphere intersecting

4 end points (a,b,c,d say) are chosen uniformly randomly and connected a to b and c to d by two geodesics on the 2-dim half-sphere. Here, uniform means that, probability that a point lies on a surface ...
Rahul Gangopadhyay's user avatar
6 votes
3 answers
415 views

Isoperimetric inequality for $\epsilon$-expansion of a set only along a certain subspace

Let $\gamma_n$ be the standard gaussian distribution on $\mathbb R^n$. Let $V$ be a $k$-dimensional subspace of $\mathbb R^n$. Finally let $A$ be any (nonempty) Borel subset of $A$ with $\gamma_n(A) = ...
dohmatob's user avatar
  • 6,716
6 votes
1 answer
180 views

Does there exist a Penalized Conditional Expectation?

In my recent work I've become interested in working with the minimizer of $$ \mathbb{E}[(Y-Z)^2] + \lambda P(Z), $$ $Y$ is an observed random variable, $P$ is a positive-convex penalty function, $Z$ ...
ABIM's user avatar
  • 5,019
6 votes
1 answer
232 views

Which orthant probabilities are the largest? (For a multivariate normal distribution)

I have a $k$-dimensional multivariate normal distribution $X∼N(0,\Sigma)$ with covariance matrix $\Sigma$. $\Sigma$ has two distinct eigenvalues, say $\lambda_1 > \lambda_2$, with orthogonal ...
Matthew Harrison-Trainor's user avatar
5 votes
3 answers
4k views

Distribution of the individual coordinates of a uniform random vector on a high-dimensional sphere

Let $X=(X_1,\ldots,X_n)$ be a random vector uniformly distributed on the $n$-dimensional sphere of radius $R > 0$. Intuitively, i think that for large $p$ every coordinate $X_i$ is normally ...
dohmatob's user avatar
  • 6,716
5 votes
1 answer
460 views

The expectation of two sides of rectangle is equal. Can we deduce that in the expectation the rectangle is not very far from being a square?

Let $T$ be a set of $n\ge 3$ points in the plane such that not all of them lie in a common line. Pick two distinct points $\{a=\left( \begin{array}{c} a_{1} \\a_{2} \end{array} \right) ,b=\left( \...
j.s.'s user avatar
  • 519
5 votes
4 answers
855 views

Probability that convex hull of multivariate Gaussian sample contains a given point

I am generating random vectors $X_1, \dots, X_N$ from a $d$-dimensional multivariate normal $\text N(\mu, \Sigma)$. I would like to know what is the probability that a given point $y \in R^d$ falls ...
Jugurtha's user avatar
  • 101
5 votes
1 answer
300 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}^...
user655870's user avatar
5 votes
1 answer
187 views

Probability of gaps between coordinates of a random point on the sphere

Let $X=(X_1,\ldots,X_n)$ be a point chosen uniformly at random from the sphere $S^{n-1}\subseteq \mathbb R^n$. Given $a>0$, what is the probability that $|X_1|^2-|X_i|^2\geq a$ for all $i>1$? Is ...
Hadi's user avatar
  • 731
5 votes
1 answer
544 views

Show that the Markov chain of random tiling is irreducible

Consider a Markov chain on a state-space which is slightly weird: It is the space of all tilings of a hexagon as shown in the left-hand side of the figure below with three types of rhombi: yellow, ...
user avatar
5 votes
1 answer
828 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):= \...
dohmatob's user avatar
  • 6,716
5 votes
1 answer
365 views

Sums of uniformly random vectors from the $n$-dimensional unit ball

I'm interested in some instances of the following problem. Let $n \geq 2$, and suppose we draw $k \geq 2$ vectors $v_1, \dots, v_k$ uniformly at random from the $n$-dimensional ball of radius $1$, $...
TMM's user avatar
  • 713

1
2 3 4 5