All Questions
Tagged with pr.probability geometric-probability
164 questions
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 ...
- 188k
5
votes
1
answer
549
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, ...
- 39.8k
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 ...
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\...
- 1,048
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$ ...
- 724
2
votes
0
answers
57
views
Given a set of marginals, what is the largest support of a distribution satisfying these?
Given a random variable $X$ with support over $\{0,1\}^I$, we can define the marginal distribution on the bits indexed by $A \subseteq I$ by $Pr(X_A = x_A) = \sum_{x \in \{0,1\}^{I - A}} Pr(X = x \cup ...
8
votes
2
answers
976
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\...
- 4,729
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 ...
- 4,361
1
vote
1
answer
95
views
gaussian isoperimetric result for minimal measure under translation
Consider two spherical Gaussian distributions in $\mathbb{R}^n$, $A = \mathcal{N}(x, I)$ and $B=\mathcal{N}(y, I)$ where the difference in means is $\delta = y - x$.
Let $S \subset \mathbb{R}^n$ be a ...
- 133
0
votes
1
answer
253
views
Does log-concave approximable distribution satisfy transportation-cost inequality?
Definition: Recall that a distribution $\mu$ on $\mathbb R^d$ is said to be log-convave with constant $c > 0$, if density $d\nu \propto e^{-V}dvol$ satisfying the curvature condition
$$
\...
- 11.4k
4
votes
1
answer
2k
views
What is the nearest-neighbor distribution in this picture?
Consider the following process: sample $n$ points uniformly at random in the unit square, and for each point $i$, let $d_i$ be the distance from $i$ to its nearest neighbor. Finally, let $z_i = d_i\...
- 23.2k
4
votes
1
answer
116
views
Distribution of the $pn$ shortest edges out of $n$ uniform points, $p\to 0$
Suppose I sample $n$ points independently and uniformly at random in the unit square, and then I select the $pn$ shortest edges between all pairs of points, for fixed $0<p<1$. For large $n$ and ...
- 23.2k
28
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 ...
- 2,902
0
votes
0
answers
165
views
Probability that the perturbed convex hull is larger than the original one
I am wondering if any convex geometers/probabilists have looked at the following question:
Given $n$ randomly distributed (not sure what assumption to put there) points in $\mathbb{R}^d$, for each ...
- 133
4
votes
1
answer
355
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)...
- 232
2
votes
1
answer
319
views
Minimum distance to a sampled point with given pdf
Let $f(x)>0$ be a probability density function defined on the unit square $[0,1]^2$ in $\mathbb{R}^2$. Suppose that we take $N$ independent samples, $X_1,\dots,X_N$, of $f$. Now, sample a point $...
- 4,713
10
votes
2
answers
797
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 ...
- 4,713
1
vote
0
answers
94
views
Measure of the boundary of the support of a certain function defined by an expectation
Suppose:
$\mathcal{S} = \{ S \in \mathbb{R}^d \ | \ S_i > 0, \forall i = 1,...,d \} $
$R$ is a random vector (on some probability space, $\Omega$) such that, $R: \Omega \to \mathcal{S}$.
$h : ...
- 111
8
votes
2
answers
256
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, ...
CommunityBot
- 1
0
votes
0
answers
137
views
Expected Number of Triangles
A unit square is divided up with $n$ random lines. The random lines are chosen as follows, we choose one side of the square and pick a random point on that side. From there we choose a random point on ...
- 505
3
votes
0
answers
85
views
Expected Largest Area with Random Lines
We take the unit square and have it divided by $n$ lines which are chosen randomly. We choose the lines as follows, choose one of the four sides of the square at random and then choose a random point ...
- 4,713
3
votes
2
answers
590
views
The Largest Piece of Circumference
We add $n$ random lines to the unit disc. We do so by adding two points on the disc, transcribing a line between them and extending that line to the boundary of the disc, namely the unit circle. Each ...
- 4,713
6
votes
3
answers
2k
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 ...
- 37.7k
2
votes
0
answers
899
views
norm of projection of a random vector on the sphere onto a linear subspace
Let $x$ be a random vector uniformly distributed on the unit sphere $\mathbb{S}^{D-1}$ and let $\mathcal{V}$ be a linear subspace of dimension $m$. Then it is known that the euclidean norm of the ...
- 398
4
votes
0
answers
180
views
Volume difference in random approximation of polytope
The following easily stated problem has arisen in my research. However, it's outside my field, and I'm unfamiliar with the literature. I would greatly appreciate any references.
Let $K\subset \...
- 44.4k
4
votes
1
answer
539
views
Buffon's needles revisited
Hi,
I recently came across the famous Buffon's needle problem (http://en.wikipedia.org/wiki/Buffon%27s_needle), and there is no doubt that the problem as well as its answer are elegant.
However, the ...
- 44.4k
2
votes
2
answers
571
views
The consequence of overlap sharing for the length-distribution of rods randomly placed on a line
Please imagine that one populates a finite line of unit length, or circle with unit length contour (to avoid edge-effects), with $N$ one-dimensional 'rods' such that their LHS-ends, at positions $(p_1,...
- 44.4k
5
votes
1
answer
415
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$, $...
- 44.4k
4
votes
0
answers
481
views
The probability distribution for the number of pairwise distances $\leq$ some threshold for points uniformly placed in a sphere
If I place place $N$ particles in a sphere of radius $R$, selecting positions across the sphere's volume with uniform probability, what is the exact probability distribution for the number of pairwise ...
- 44.4k
1
vote
2
answers
2k
views
Minimum distance between $n$ points in a cube
What is the expected value for the minimum distance between $n$ points placed randomly, assuming a uniform distribution, within a cube of volume $V$?
CommunityBot
- 1
2
votes
1
answer
396
views
Manhattan distance vs. absorption time on an unbounded integer lattice
Imagine I have unbounded $d$-dimensional integer lattice where I take two vertices, $v_a$ and $v_b$, separated by a fixed Manhattan distance $L$, and I release a random walker at $v_a$ and allow for ...
- 44.4k
13
votes
4
answers
535
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 $...
- 44.4k
3
votes
0
answers
133
views
Partitioning a sphere with a random tessellation
I have a $d$-dimensional sphere of radius $1$. I now tessellate the space with $d$-dimensional cubes of side $L$ and uniform distribution of the origin of the tessellation. Thus the size of the ...
- 44.4k
10
votes
4
answers
904
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 ...
- 1,228
1
vote
1
answer
234
views
When is the second largest Gaussian r.v. the largest in the stochastic sense?
Let $X_1, \ldots, X_n$ be jointly Gaussian, each of which is marginally distributed as a standard Gaussian $N(0,1)$. It is well known that $\max |X_i|$ achieves the maximum in the stochastic sense if $...
CommunityBot
- 1
15
votes
2
answers
755
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 ...
- 4,713
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 ...
- 17k
1
vote
1
answer
431
views
Properties of moment generating function of random walk on unit sphere
Question in brief
Let $a$ and $b$ be unit vectors in $\mathbb{R}^d$. Let $f$ be the $1-step$ transition function of a random walk on the $d$ dimensional unit sphere.
I am interested in evaluating $\...
CommunityBot
- 1
4
votes
1
answer
910
views
Uniformly Random Independent Unit Vectors Inner Product Limit
Suppose $V$ is a $N\times n$ matrix the columns of which are independently distributed uniformly on $\mathbf S^{N-1}$ the surface of the unit sphere in $\mathbf R^N$. I conjecture that $V^TV$ ...
- 1,533
4
votes
2
answers
1k
views
Total progeny of a Galton-Watson branching process - standard textbook question
While analyzing some parallel-computing related algorithm, I came across a probability distribution with a particularly nice property (at least to me), but I am unable to write it down explicitly.
...
- 396
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( \...
- 19k
4
votes
1
answer
286
views
Upper tail concentration of sample covariance matrices
I'm interested in concentration of the following random matrix sum in spectral norm
$\frac{1}{m}\sum_{k=1}^m b_k^2\mathbf{a}_k\mathbf{a}_k^*$
Here $\mathbf{a}_k\in\mathbb{R}^n$ are i.i.d. standard ...
CommunityBot
- 1
6
votes
1
answer
188
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$ ...
- 4,529
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
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
0
answers
134
views
Algorithm to calculate moments of uniform distribution on convex polyhedra
There is system of linear inequalities
$$
Ax \leq K,
$$
$$
x\geq a, x\leq b.
$$
$A$ is $(n\times m)$-matrix, where $n\approx 100$ and $m\approx 10000$, $rank(A)=n$.
Suppose that on set of solutions ...
6
votes
3
answers
298
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 ...
CommunityBot
- 1
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
4
votes
1
answer
447
views
Area enclosed by Brownian motion (without winding number)
The question Average Value of Area Closed by Brownian Motion turned out to be about the Lévy area process, which measures "signed area with multiplicity" enclosed by Brownian motion (e.g. each ...
CommunityBot
- 1
1
vote
1
answer
150
views
Probability Content of a random ball in R^n
As a follow up to this question, concerning this paper:
Given random variables $X_1,\ldots,X_N,X_q:\Omega\rightarrow\mathbb{R}^d$, where $X_1,\ldots,X_N$ are independent and identical distributed. ...
CommunityBot
- 1