All Questions
Tagged with pr.probability geometric-probability
164 questions
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 ...
- 4,049
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\...
- 6,853
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 ...
- 19.7k
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
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
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
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 ...
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 ...
- 96.4k
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 ...
- 133
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 ...
- 133
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
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, ...
- 4,049
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 $...
- 773
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)...
- 83
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
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$ ...
- 2,239
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
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 $\...
- 720
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( \...
- 519
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 ...
- 162
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$ ...
- 5,405
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$?
- 31
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 \...
- 211
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 $...
- 131
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{...
- 1,127
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 ...
- 141
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 ...
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 ...
- 363
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$ ...
- 1,127
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 ...
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 ...
- 367
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 ...
- 29.8k
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. ...
- 329
0
votes
1
answer
292
views
Volume of randomly changing sphere follows beta distribution
We are given $X,X_1,\ldots,X_N$ independent and identically distributed $k$-dimensional vectors. For a given query point $X_q\in\mathbb{R}^k$ assume without loss of generality that $X_1,\ldots,X_m$ ...
- 329
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
0
votes
0
answers
454
views
Reference: Bochner Integral`
What would be an easily accessible book dealing with Bochner integration as applied to probability theory (I'm looking to understand random elements and their basic related concepts in a formal yet ...
- 5,405
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 ...
- 121
1
vote
0
answers
234
views
Strong Dependence
I don't know if this definition has been already given.
Suppose $X$ and $Y$ are two random variables over finite alphabets $\mathcal{X}$ and $\mathcal{Y}$. We say $Y$ is strongly dependent on $X$ if ...
- 1,109
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 ...
- 335
12
votes
2
answers
928
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 ...
- 401
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
2
votes
0
answers
242
views
What transformations preserve the von Mises distribution?
The von Mises distribution is entirely defined on the circle with a density given by
$$f(x) = (2\,\pi\, I_0(\kappa))^{-1} \exp(\kappa \cos(x-\mu))\ ,$$
where $x$ is in an arbitrary real interval of ...
- 236
5
votes
4
answers
906
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 ...
- 101
4
votes
2
answers
2k
views
Do Random Walks on the Hexagonal Lattice have a limit?
For every positive integer $n$, consider a regular hexagon $\mathrm{H}_n$ such that
the distance of each vertex from the center is $\frac{1}{\sqrt{n}}$. That in turn
induces a tiling of $\mathbb{R}^...
- 3,245
0
votes
1
answer
197
views
Area on the unit sphere swept out by big circles corresponding to a curve
For a point on the unit sphere, we know the plane perpendicular to the line through the origin and the point cuts the sphere with a big circle. When the point moves along a sphere curve, the ...
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$, $...
- 733
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 ...
- 41
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
1
vote
0
answers
245
views
Random walk conditioned on sum and last step
Can anyone help with the following (slightly weird) random walk question? I have a random walk starting at $X_0 = 1 = S_0$ where the steps $X_i$ are independent uniform random variates in $[-1,1]$. ...
- 747
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 ...
- 173