Timeline for A disc contains many random points. Each point is connected to its nearest neighbor. What is the expectation of average cluster size?
Current License: CC BY-SA 4.0
23 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 10 at 14:46 | comment | added | Dan | @user1536 No worries. Sure, we can delete our comments. | |
| Aug 10 at 14:40 | comment | added | user1536 | @Dan Sorry, I misread the solution - I can delete the comment if thats helpful | |
| Aug 6 at 8:18 | comment | added | Dan | @user1536 I'm not sure which part of my answer you think is incorrect. Is it my sentence "The number of clusters equals the number of pairs of points that are mutually nearest neighbors"? If so, can you show or describe an example of a set of points in which this sentence is not true? In your example with points a,b,c, I would say that the three points form one cluster, and this cluster contains exactly one pair of mutually nearest neighbors (a and b). | |
| Aug 6 at 6:48 | comment | added | user1536 | I do not think this solution is correct - the assumption that they need to be mutually nearest neighbors is wrong - if that were the case all component would have cardinality 2. Consider points a,b,c on a line a and b are mutually nearest neighbors but b and c are not as b is closer to a than to c..so this argument does not work. | |
| Jan 26 at 10:22 | comment | added | Jérôme JEAN-CHARLES | @Dan Perfect response (that teached me something). Thanks you. | |
| Jan 22 at 13:29 | vote | accept | Dan | ||
| Jan 17 at 21:59 | comment | added | Dan | @JérômeJEAN-CHARLES We use disk point picking. | |
| Jan 17 at 20:22 | comment | added | Jérôme JEAN-CHARLES | How do you pick random points on the disk? ( i.e. be wary of Buffon'needle paradox). | |
| Jan 16 at 5:23 | comment | added | მამუკა ჯიბლაძე | With 100000 attempts, for $n=5,6,7,...$ I get $3.27, 3.43, 3.49, 3.505, 3.49, 3.475, 3.45, 3.42, ...$ | |
| Jan 16 at 5:08 | comment | added | მამუკა ჯიბლაძე | Oh I see - you suggest that the expectations decrease monotonously with $n$. This souns very convincing indeed. | |
| Jan 16 at 5:02 | comment | added | Dan | @მამუკაჯიბლაძე I don't know, but I did trials with $4$ points and got $3.44$ (I guess that's the exact value for $n=4$). | |
| Jan 16 at 4:58 | comment | added | მამუკა ჯიბლაძე | Maybe. Can you guess what could produce the upward bias? | |
| Jan 16 at 4:57 | comment | added | Dan | @მამუკაჯიბლაძეI reckon it's just experimental error. | |
| Jan 16 at 4:54 | comment | added | მამუკა ჯიბლაძე |
Here is Mathematica code f[M_, A_] := Mean[Table[With[{pts = Select[RandomReal[{-1, 1}, {M, 2}], Norm[#] <= 1 &]}, N[Length[pts]/Length[ConnectedComponents[Graph[Table[p \[UndirectedEdge] First[SortBy[Complement[pts, {p}], EuclideanDistance[#, p] &]], {p, pts}]]]]]], {A}]]
|
|
| Jan 16 at 4:50 | comment | added | მამუკა ჯიბლაძე | I now started runs on 10000 points, but so far only got 3 attempts, mean is $3.22722$ | |
| Jan 16 at 4:49 | comment | added | მამუკა ჯიბლაძე | I took mean of 1000 attempts with 100 points, and of 10 attempts with 1000 points, about 5 times each | |
| Jan 16 at 4:46 | comment | added | Dan | @მამუკაჯიბლაძე How many points are you using? | |
| Jan 16 at 4:42 | comment | added | მამუკა ჯიბლაძე | Not sure, but certainly above $3.225$ | |
| Jan 16 at 4:40 | comment | added | Dan | @მამუკაჯიბლაძე I could be wrong. What do your experiments suggest for the expectation? | |
| Jan 16 at 4:35 | comment | added | მამუკა ჯიბლაძე | Experimentally I keep getting values larger than $3.218$. Actually I never got anything below $3.22$ | |
| Jan 16 at 3:50 | history | edited | Dan | CC BY-SA 4.0 |
deleted 1 character in body
|
| Jan 16 at 3:44 | history | edited | Dan | CC BY-SA 4.0 |
deleted 1 character in body
|
| Jan 16 at 3:38 | history | answered | Dan | CC BY-SA 4.0 |