OU blog

Personal Blogs

Richard Walker

Linearity of Expectation Again

Visible to anyone in the world

Linearity of Expectation can pop in surprising places.

Buffon's needle is a famous experiment first published by the Comte de Buffon in 1777. His idea was to repeatedly throw a short needle on to an array of equally spaced parallel lines and count how often the needle crossed a line. This can then be used to estimate the value of the famous number π, a rather surprising fact.

Suppose the lines are spaced 1 unit apart and the needle is of length L less than 1, so the needle will cross at most one line. Then it can be shown the average number of crossings is 2 x L/π.

The standard way to work this out uses calculus, but reading around Linearity of Expectation I came a cross a far simpler way.

In the sketch below the circles are of diameter 1 and you can see that a circle however positioned will have exactly 2 points in common with the array of paralle lines.


So we can say immediately that the expected number of crossings when a circle is placed on the array of parallel lines is 2.

Now imagine replacing the circle with a polygon made up of many tiny needles each of identical length L. The polygon will only be an approximate circle, but if the needles are very short the approximation will be good.

Given the circle has diameter 1 its circumference will be π x 1 = π and the approximating polygon will require π / L needles. Suppose we define an indicator which is 1 if a given needle crosses a line and 0 otherwise. Let the expected value of this indicator variable be E. This is the same for all the needles; it represents the average number of crossings, not the actual number of crossing by any particular needle.

Using linearity of expectation and adding this expectation E across all the π / L needles we get E x π / L and this must be the expected number of crossing for the circle, because the needles taken together make up the circle! So E x π / L = 2.

Rearrange this slightly and voilà! - we have Buffon's formula.

E = 2 x L / π

This extremely neat and simple approach was found by Barbier as long ago as 1860 but I only stumbled across it a couple of days back.

We need to do a little more work before we have a complete proof, because we've assumed L is very small. What if it's not? I'll add something in the comments about this.



Permalink 1 comment (latest comment by Richard Walker, Friday, 6 Sep 2019, 18:48)
Share post
Richard Walker

Solution To 'Dermatoglyphics' Question

Visible to anyone in the world

The question at

https://learn1.open.ac.uk/mod/oublog/viewpost.php?post=221531

asked for the average, i.e. the mean, number of letters that would be left unchanged in position if the letters of 'Dermatoglyphics' are scrambled at random. The answer is 1 and surprisingly, to me anyway, the answer would be exactly the same for any other word with no repeated letters, whatever its length. Even though I know why this is it still amazes me, it seems to go against intution.

We can try this out with short word.

1 letter - 'a'
There is 1 arrangement, with 1 letter in the right place.
So the average is 1.

2 letters - 'at'
Now there are 2 arrangements.
'at' with 2 letters in the right place.
'ta' with 0 letters in the right place.
So the average is 2 + 0 = 2, divided by 2, which is 1.
 
3 letters - 'cat'
Now there are 6 arrangements.
'cat' with 3 letters in the right place.
'cta' with 1 letter in the right place.
'act' with 1 letter in the right place.
'atc' with 0 letters in the right place.
'tca' with 0 letters in the right place.
'tac' with 1 letter in the right place.
So the average is 3 + 1 + 1 + 0 + 0 + 1 = 6, divided by 6, which is 1.

Doing it this way will rapidly become hard work, but luckily there is something called 'linearity of expectation' which provides a general argument why this average will always be 1. For anyone interested, I'll put something in the comments tomorrow.

Permalink 5 comments (latest comment by Richard Walker, Sunday, 1 Sep 2019, 22:04)
Share post

This blog might contain posts that are only visible to logged-in users, or where only logged-in users can comment. If you have an account on the system, please log in for full access.

Total visits to this blog: 1858287