You are currently browsing the tag archive for the ‘average distance’ tag.

Finding the average distance between 2 points on a hypercube

This is the natural extension from this previous post which looked at the average distance of 2 randomly chosen points in a square – this time let’s explore the average distance in n dimensions.  I’m going to investigate what dimensional hypercube is required to have an average distance of more than one, and then also what happens to the average distance as n approaches infinity.

Monte Carlo method

The Monte Carlo method is a very powerful technique which utilizes computational power.  Basically we use the fact that the average of a very large number of trials will serve as an approximation to an exact result.  In this case I will run a Python program 10 million times – each time it will select 2 coordinate points and then work out the distance between them.  It will then find the average of these 10 million trials.  The code above generates 2 coordinates in 3 dimensional space inside a unit cube.  We can modify this for n-dimensional space by remembering that Pythagoras still works in higher dimensions.  

Results

Running this code helps to generate the above results.  This answers our first question – we need a 7 dimensional unit hypercube until the average distance between two randomly chosen points is greater than 1.  We can also see that the difference between the average distances is reducing – but it’s not clear if this will approach a limit or if it will continue growing to infinity.  So let’s do some more trials.

Further trials

This takes us up to a 22-dimensional hypercube.  At this point it’s probably useful to plot a graph to see the trend.

Reciprocal model

 

This reciprocal model is of the form:

We can see that this is a pretty good fit (R squared 0.9994).  If this model is accurate then this would suggest that the average distance approaches a limit as n approaches infinity.

Polynomial model

This polynomial model is of the form:

We can see that this is also a very good fit (R squared 0.9997).  If this model is accurate then as b is greater than 0, this would suggest that the average distance approaches infinity as n approaches infinity.

Reflection

Quite annoyingly we have 2 model which both fit the data very accurately – but predict completely different results!  Logically we could probably say that we would expect the average distance to approach infinity as n approaches infinity – and also we could possibly justify this by the fact that the polynomial model is a slightly better fit.  Given the similarity between the 2 models it probably time to find out the actual results for this.

Average n-dimensional distance bounds

Not surprisingly the mathematics required to work this out is exceptionally difficult – and ends up with non-solvable integrals which require analytic solutions.  The Monte Carlo method with very large numbers of trials is a reasonably good approach to approximating this answer.  There is however a very useful lower and upper bound for the average distance in n dimensional space given by:

This shows immediately that the average distance will approach infinity as n grows large – as the lower bound will grow to infinity.  Quite pleasingly we can see that the polynomial model we derived is similar to the lower bound.  We can plot both upper and lower bound along with our polynomial model to see how these all compare.  We have lower bound (green), polynomial model (black) and upper bound (green):


We can see that our polynomial model very closely follows the upper bound in our domain.  As we extend the domain this polynomial approximation remains above the lower and tracks the upper bounds before gradually growing less accurate.  When n is 50 our model predicts a distance of 2.94, whereas the upper bound is 2.88.  This is quite a nice result – we have used the Monte Carlo method to derive a polynomial approximation to the average distance in n-dimensional hypercubes and it both closely follows the upper bound over a reasonable domain and also is of a very similar form to the lower bound.  We can use this lower bound to see that a 36 dimensional hypercube (and higher) would be guaranteed to have an average distance of more than 2.

Conclusion

This was a nice example of the power of the Monte Carlo method in these kind of problems – we were able to use it quite successfully to get a polynomial approximation which turned out to be reasonably accurate.  We could have significantly improved this accuracy by running 100 million (or 1 billion etc) trials each time – though this would have probably required a more powerful computer!

Website Stats

  • 7,989,119 views

IB HL Paper 3 Practice Questions (120 page pdf)

IB HL Paper 3 Practice Questions 

Seventeen full investigation questions – each one designed to last around 1 hour, and totaling around 40 pages and 600 marks worth of content.  There is also a fully typed up mark scheme.  Together this is around 120 pages of content.

Available to download here.

IB Maths Exploration Guide

IB Maths Exploration Guide

A comprehensive 63 page pdf guide to help you get excellent marks on your maths investigation. Includes:

  1. Investigation essentials,
  2. Marking criteria guidance,
  3. 70 hand picked interesting topics
  4. Useful websites for use in the exploration,
  5. A student checklist for top marks
  6. Avoiding common student mistakes
  7. A selection of detailed exploration ideas
  8. Advice on using Geogebra, Desmos and Tracker.

Available to download here.

Modelling Guide


IB Exploration Modelling Guide 

A 50 page pdf guide full of advice to help with modelling explorations – focusing in on non-calculator methods in order to show good understanding.

Modelling Guide includes:

Linear regression and log linearization, quadratic regression and cubic regression, exponential and trigonometric regression, comprehensive technology guide for using Desmos and Tracker.

Available to download here.

Statistics Guide

IB Exploration Statistics Guide

A 55 page pdf guide full of advice to help with modelling explorations – focusing in on non-calculator methods in order to show good understanding.

Statistics Guide includes: Pearson’s Product investigation, Chi Squared investigation, Binomial distribution investigation, t-test investigation, sampling techniques, normal distribution investigation and how to effectively use Desmos to represent data.

Available to download here.

IB Revision Notes

IB Revision Notes

Full revision notes for SL Analysis (60 pages), HL Analysis (112 pages) and SL Applications (53 pages).  Beautifully written by an experienced IB Mathematics teacher, and of an exceptionally high quality.  Fully updated for the new syllabus.  A must for all Analysis and Applications students!

Available to download here.

Recent Posts

Follow IB Maths Resources from British International School Phuket on WordPress.com