All Questions
6 questions
0
votes
1
answer
119
views
How many samples do you need to get constant dispersion?
Let $C_n$ be the hypercube $[-1,1]^n$. For $a_1,\cdots,a_s \in C_n$, define its dispersion $D(a_1,\cdots,a_s)$ as $\max_{x \in C_n}\min_{i \in [s]} \|x-a_i\|_{2}$. Let $0< \lambda < 1$ be a ...
2
votes
1
answer
201
views
Dispersion of a "random" subset of $[-1,1]^2$
Let $C$ be the square $[-1,1]^2$. Let $a_1,\dots,a_m$ be points chosen independently and uniformly at random from $C$. Let $d_m$ (dispersion) be the random variable $\max_{x \in C}{\min_{j \in [m]}{\|...
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$...
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 ...
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 $...
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 ...