You are currently browsing the tag archive for the ‘hypercubes’ tag.
If you are a teacher then please also visit my new site: intermathematics.com for over 2000+ pdf pages of resources for teaching IB maths!
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!
Essential Resources for IB Teachers
If you are a teacher then please also visit my new site. This has been designed specifically for teachers of mathematics at international schools. The content now includes over 2000 pages of pdf content for the entire SL and HL Analysis syllabus and also the SL Applications syllabus. Some of the content includes:
- Original pdf worksheets (with full worked solutions) designed to cover all the syllabus topics. These make great homework sheets or in class worksheets – and are each designed to last between 40 minutes and 1 hour.
- Original Paper 3 investigations (with full worked solutions) to develop investigative techniques and support both the exploration and the Paper 3 examination.
- Over 150 pages of Coursework Guides to introduce students to the essentials behind getting an excellent mark on their exploration coursework.
- A large number of enrichment activities such as treasure hunts, quizzes, investigations, Desmos explorations, Python coding and more – to engage IB learners in the course.
There is also a lot more. I think this could save teachers 200+ hours of preparation time in delivering an IB maths course – so it should be well worth exploring!
Essential Resources for both IB teachers and IB students
1) Exploration Guides and Paper 3 Resources
I’ve put together a 168 page Super Exploration Guide to talk students and teachers through all aspects of producing an excellent coursework submission. Students always make the same mistakes when doing their coursework – get the inside track from an IB moderator! I have also made Paper 3 packs for HL Analysis and also Applications students to help prepare for their Paper 3 exams. The Exploration Guides can be downloaded here and the Paper 3 Questions can be downloaded here.
If you are a teacher then please also visit my new site: intermathematics.com for over 2000+ pdf pages of resources for teaching IB maths!
Generating e through probability and hypercubes
This is a really beautiful solution to an interesting probability problem posed by fellow IB teacher Daniel Hwang, for which I’ve outlined a method for solving suggested by Ferenc Beleznay. The problem is as follows:
On average, how many random real numbers from 0 to 1 (inclusive) are required for the sum to exceed 1?
1 number
Clearly if we choose only 1 number then we can’t exceed 1.
2 numbers
Here we imagine the 2 numbers we pick as x and y and therefore we can represent them as a coordinate pair. The smallest pair (0,0) and the largest pair (1,1). This means that the possible coordinates fit inside the unit square shown above. We want to know for what coordinate pairs we have the inequality x + y > 1. This can be rearrange to give y > 1-x. The line y = 1-x is plotted and we can see that any coordinate points in the triangle BCD satisfy this inequality. Therefore the probability of a random coordinate pair being in this triangle is 1/2.
3 numbers
This time we want to find the probability that we exceed 1 with our third number. We can consider the numbers as x, y, z and therefore as 3D coordinates (x,y,z). From the fact that we are choosing a third number we must already have x +y <1. We draw the line x+y = 1, which in 3D gives us a plane. The volume in which our coordinate point must lie is the prism ABDEFG.
We now also add the constraint x+y+z >1. This creates the plane as shown. If our coordinate lies inside the pyramid ABDE then our coordinates will add to less than 1, outside this they will add to more than 1.
The volume of the pyramid ABDE = 1/3 (base area)(perpendicular height).
The volume of the prism ABDEFG = (base area)(perpendicular height).
Given that they share the same perpendicular height and base area then precisely 1/3 of the available volume would give a coordinate point that adds to less than 1, and 2/3 of the available volume would give a coordinate point that adds to more than 1.
Therefore we have the following tree diagram:
Exceeds 1 with 2 numbers = 1/2
Does not exceed 1 with 2 numbers, exceeds 1 with 3 numbers = 1/2 x 2/3 = 1/3.
Does not exceed 1 with 2 numbers, does not exceed 1 with 3 numbers = 1/2 x 1/3 = 1/6.
4 numbers
If you been following so far this is where things get interesting! We can now imagine a 4 dimensional unit cube (image above from Wikipedia) and a 4D coordinate point (x,y,z,a).
Luckily all we care about is the ratio of the 4-D pyramid and the 4-D prim formed by our constraints x+y+z <1 and x+y+z+a >1.
We have the following formula to help:
The n-D volume of a n-D pyramid = 1/n (base)(perpendicular height).
Therefore:
The 4-D volume of a 4-D pyramid = 1/4 (base 3D volume)(perpendicular height).
The 4-D volume of the prism ABDEFG = (base 3D volume)(perpendicular height).
Given that the 2 shapes share the same base and perpendicular height, the hyper-pyramid occupies exactly 1/4 of the 4-D space of the hyper-prism. So the probability of being in this space is 1/4 and 3/4 of being outside this space.
We can now extend our tree diagram:
Does not exceed 1 with 2 numbers, does not exceed 1 with 3 numbers, exceeds with 4 numbers = 1/2 x 1/3 x 3/4 = 1/8
Does not exceed 1 with 2 numbers, does not exceed 1 with 3 numbers, does not exceed with 4 numbers = 1/2 x 1/3 x 1/4 = 1/24.
In general a hyper-pyramid in n dimensional space occupies exactly 1/n of the space of the hyper-prism – so we can now continue this tree diagram.
Expected value
We can make a table of probabilities to find how many numbers we expect to use in order to exceed one.
Which gives us the following expected value calculation:
Which we can rewrite as:
But we have:
Therefore this gives:
So on average we would need to pick e numbers for the sum to exceed one! This is quite a remarkable result – e, one of the fundamental mathematical constants has appeared as if by magic on a probability question utilizing hyper-dimensional shapes.
Demonstrating this with Python
Running the Python code shown above will simulate doing this experiment. The computer generates a “random” number, then another and carries on until the sum is greater than 1. It then records how many numbers were required. It then does this again 1 million times and finds the average from all the trials.
1 million simulations gives 2.7177797177797176. When we compare this with the real answer for e, 2.7182818284590452353602874713527, we can see it has taken 1 million simulations to only be correct to 4sf.
Even 5 million simulations only gives 2.7182589436517888, so whilst we can clearly see that we will eventually get e, it’s converging very slowly. This may be because we are reliant on a random number generator which is not truly random (and only chooses numbers to a maximum number of decimal places rather than choosing from all values between 0 and 1).
I think this is a beautiful example of the unexpected nature of mathematics – we started out with a probability problem and ended up with e, via a detour into higher dimensional space! We can also see the power of computers in doing these kinds of brute force calculations.
Essential Resources for IB Teachers
If you are a teacher then please also visit my new site. This has been designed specifically for teachers of mathematics at international schools. The content now includes over 2000 pages of pdf content for the entire SL and HL Analysis syllabus and also the SL Applications syllabus. Some of the content includes:
- Original pdf worksheets (with full worked solutions) designed to cover all the syllabus topics. These make great homework sheets or in class worksheets – and are each designed to last between 40 minutes and 1 hour.
- Original Paper 3 investigations (with full worked solutions) to develop investigative techniques and support both the exploration and the Paper 3 examination.
- Over 150 pages of Coursework Guides to introduce students to the essentials behind getting an excellent mark on their exploration coursework.
- A large number of enrichment activities such as treasure hunts, quizzes, investigations, Desmos explorations, Python coding and more – to engage IB learners in the course.
There is also a lot more. I think this could save teachers 200+ hours of preparation time in delivering an IB maths course – so it should be well worth exploring!
Essential Resources for both IB teachers and IB students
1) Exploration Guides and Paper 3 Resources
I’ve put together a 168 page Super Exploration Guide to talk students and teachers through all aspects of producing an excellent coursework submission. Students always make the same mistakes when doing their coursework – get the inside track from an IB moderator! I have also made Paper 3 packs for HL Analysis and also Applications students to help prepare for their Paper 3 exams. The Exploration Guides can be downloaded here and the Paper 3 Questions can be downloaded here.
IB Maths Resources from Intermathematics 