My Math Forum  

Go Back   My Math Forum > College Math Forum > Advanced Statistics

Advanced Statistics Advanced Probability and Statistics Math Forum


Thanks Tree1Thanks
  • 1 Post By mathman
Reply
 
LinkBack Thread Tools Display Modes
August 29th, 2017, 01:26 AM   #1
Newbie
 
Joined: Aug 2017
From: Singapore

Posts: 2
Thanks: 0

Prove a large number of samplings converge to a set of small number of samples

In a $k$-dimensional space, given a set of $n$ points: $X=\{x_1, x_2,..., x_n\}$ which is sampled from an known distribution $P$. Given a set of $m$ points ($m << n$): $Y=\{y_1,y_2,...,y_m\}$ which is also drawn from $P$. Suppose $\{z_1, z_2,...,z_m\} \subset X$ are the closest points (in term of Euclidean distance) of $\{y_1,y_2,...,y_m\}$ respectively. A gap $g$ is defined as follows:

$\displaystyle g = max\{|z_1 - y_1|^2, |z_2 - y_2|^2,..., |z_m - y_m|^2\}$

where $|a-b|^2$ denotes the Euclidean distance between a, b.

Prove that if $m$ is fixed, $g \rightarrow 0$ as $n \rightarrow \infty$.

I don't know how to start this problem. Thank you.

Last edited by thanhvinh0906; August 29th, 2017 at 02:00 AM.
thanhvinh0906 is offline  
 
August 29th, 2017, 02:11 PM   #2
Global Moderator
 
Joined: May 2007

Posts: 6,380
Thanks: 542

The applicable theorem is the law of large numbers, but I haven't tried to work it out. I'll leave that to you.
Thanks from thanhvinh0906
mathman is offline  
August 30th, 2017, 02:34 AM   #3
Newbie
 
Joined: Aug 2017
From: Singapore

Posts: 2
Thanks: 0

Quote:
Originally Posted by mathman View Post
The applicable theorem is the law of large numbers, but I haven't tried to work it out. I'll leave that to you.
Thank you for your hint.

Could you please check whether my below proof is correct? I do it in a uniform distribution.

Suppose $g = max\{|z_1 - y_1|^2, |z_2 - y_2|^2,..., |z_m - y_m|^2\} = \| z_{max} - y_{max} \|$.

For any $\varepsilon > 0$, put a hypersphere radius $\varepsilon$ around $y_{max}$ in that $y_{max}$ is the centroid (*).

Suppose there is no sample of $S$ exists in the hypersphere as $n \rightarrow \infty$. (**)

We project $y_{max}$ to dimension $k$, denoted as $y_{max,k}$. Suppose the boundary of dimension $k$ is $[a, b]$, i.e. $a \leq y_{max,k} \leq b$. According to the law of large numbers, $E[x_k]$ (the average of $X$ projected to dimension $k$) $\rightarrow (a + b)/2$ as $n \rightarrow \infty$. Now if there is no sample in the hypersphere:

\begin{equation}
\begin{split}
E[x_k] \rightarrow \int_a^b \mathrm{\frac{x}{b-a}}\,\mathrm{d}x = \int_a^{y_{max,k} - \varepsilon} \mathrm{\frac{x}{b-a}}\,\mathrm{d}x + \int_{y_{max,k} + \varepsilon}^b \mathrm{\frac{x}{b-a}}\,\mathrm{d}x \\
= \frac{a+b}{2} - \frac{2\varepsilon y_{max,k}}{b - a} \neq \frac{a + b}{2}
\end{split}
\end{equation}
Equation (1) conflicts the law of large numbers, this indicates that (**) is false; so there exists at least one sample in the hypersphere. This statement accompanied by (*) indicates that $g = \| z_{max} - y_{max} \| \rightarrow 0$ as $n \rightarrow \infty$.

Please share if you have another proof. Thank you.

Last edited by skipjack; August 30th, 2017 at 05:38 PM.
thanhvinh0906 is offline  
August 30th, 2017, 05:27 PM   #4
Global Moderator
 
Joined: May 2007

Posts: 6,380
Thanks: 542

There may be a flaw in that as n increases, the set of x's changes and so would the set of z's. Therefore y_{max} may change with n.

I had further thoughts after my first post. Qualitatively, a histogram, with narrower intervals for increasing n, of the x values should resemble the density function of the probability. The y values correspond to specific points of the density. The intervals (containing y values) of the histograms should eventually contain some x (therefore z) value close to the y value. I have never taken a course in statistics, although my specialty is probability theory, so I am not sure hot to develop a proof.

Last edited by mathman; August 30th, 2017 at 05:29 PM.
mathman is offline  
Reply

  My Math Forum > College Math Forum > Advanced Statistics

Tags
converge, large, number, prove, samples, samplings, set, small



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Small number at bottom right. Azarashi Algebra 10 December 12th, 2016 09:38 AM
Number of factors of a large number ishaanmj007 Number Theory 2 May 14th, 2015 06:07 PM
Large number modulo FloorPlay Number Theory 2 October 30th, 2013 09:59 PM
What are the number of rainfalls in each samples? Jessicasamide Algebra 1 November 24th, 2012 06:47 PM
Number of unique after n samples BigBugBuzz Advanced Statistics 3 December 15th, 2010 02:25 PM





Copyright © 2017 My Math Forum. All rights reserved.