Probability calculations for haulage bashers

[Springs Branch]

Prompted by the recent thread on Precision Mathematics, here's a small puzzle for those of a mathematical bent who understand calculation of probabilities.

The aim is to calculate probability of how many trips a regular traveller might need in order to cover a whole class of haulage.

The Problem:
- Each day I make the same journey between home and work by train.
- To reduce the monotony, I keep a note of each unit number as I travel on it.
- How many journeys will I likely need to make before I've travelled on the entire train fleet?

Ground Rules:
- It's a commuter service with a self-contained fleet of homogenous units (like Merseyrail, Tyneside Metro or one of the Light Rail systems).
- The operator has a fleet of 30 units (or trams) at the depot (30 is an arbitrary number, could use any sensible value here).
- The operator allocates units totally at random to its diagrams each day. So there's an equal probability of any unit turning up for any trip.
- I do not modify my travel to chase "required" units. Whatever turns up, I must travel on that train.

Some Comments:
- It's all down to probabilites. You can never say anything like "you must do 52 trips. Not 51, not 53, you definitely need 52".
- Obviously the minimum to cover a fleet of 30 trains is 30 trips. Certainly the chance of a different unit turning up each time can be precisely calculated, but this will be an unimagineably small probability with random allocation of trains.
- No matter how many times you travel, you cannot absolutely 100% guarantee you will ever travel on every last train. There is a statistical probabilty that you could go to work every day for 25 years and, by chance, there is one unit that never turns up for you. But as time goes on, the probability of this happening becomes incredibly small.

Questions:
1.) What is the mathematical probability of covering all 30 units in your first 30 trips?

2.) How does this probability compare with winning the National Lottery with just a single entry?

3.) How many trips are needed for >50% probability that you have travelled on all units?

4.) How many trips are needed for >99.9% probability that you have travelled on all units?

5.) What is the formula for these calculations, to allow same analysis for different sizes of train fleet?

 

[Searle]

Given this one a bit of thought whilst I'm travelling but to no avail at the moment. I'm struggling to think of a suitable Distribution Function, so I'll have a look for it when I get home. If someone beats me to it, then I'll be curious to see and critique the answer!

I can say that the probability of doing it in the quickest time is 'n! / n^n', so for 30 trials it's 30! / 30^30, which is 1.2883161 X10^-12, so very unlikely!

The chance of winning the UK lottery is 7.15112384 x 10^-8, so it's about 1.5 times less likely to get all 30 units than winning the lottery (although technically that doesn't really make sense, but you get what I mean).

 

[edwin_m]

I think this is a fairly straightforward statistics problem - the answer will be something like if you do X trips you will have a Y% probability of having travelled on all the units. However my knowledge of statistics not up to doing even straightforward problems!

 

[bb21]

I may just set this one as homework for my first year Probabilities module students next semester.

They can have that count 50% towards their module marks.

 

[theblackwatch]

Do we have to account for any variations such as one unit being out of traffic for a year due to an accident or being used as a Christmas tree? :P

 

[Emyr]

Units don't leave the depot in random order and they don't arrive back in random order either.

 

[Searle]

Units don't leave the depot in random order and they don't arrive back in random order either.

Yeah, but you have to assume randomness to actually make the question solveable :roll:

 

[87015]

Yeah, but you have to assume randomness to actually make the question solveable :roll:

If you do it without that assumed randomness its very simple, as the diagrams will almost certainly rotate on paper through the set (ie Day1 Mon works Day2 Tue etc) which accounts for the planned order on/off depot...

Its only the 'randomness' (which is reality, if not always for random reasons) that makes it interesting, and everywhere will have different logic to what comes in and out where, including often who is on shift - don't know how you'd account for that!

 

[Mag_seven]

Suggest that the answer to question 1 is given any fleet of size N is (N-1)!/(N^(N-1)) e.g. for a fleet of size 4:

(1x2x3)/(4^3)=
6/(4x4x4)=
6/64=0.09375

i.e. 9.375%

The figure for 30 is 1.28832E-10% (i.e. not a hope in hell )

 

[Searle]

I emailed my probability lecturer at the university, and he replied, saying that it's the Coupon Collector's Problem. I'll try and answer the questions, knowing this :P

1.) What is the mathematical probability of covering all 30 units in your first 30 trips?

As above, I calculate it to be 1.2883161 X10^-12 or one in 776,207,020,880.

2.) How does this probability compare with winning the National Lottery with just a single entry?

As above again, the probability of winning the National Lottery is 7.15112384 x 10^-8, or 1 in 13,983,816. It's 55507 times more likely to win the lottery!

3.) How many trips are needed for >50% probability that you have travelled on all units?

You can't work this out exactly, but I can say that (using the formula P(T>c*n*Hn) < 1/c (where Hn is the harmonic number for n)), the largest value it can take is 60. So about 60 trips are needed to have over half chance that you've travelled on all units.

4.) How many trips are needed for >99.9% probability that you have travelled on all units?

Difficult to estimate, sorry!

5.) What is the formula for these calculations, to allow same analysis for different sizes of train fleet?

See the link!

Also something final to say is the Expected number of trips to travel on all the units is 120 trips, so about a sixth of a year if you make two trips a day.

Hope this helps!

 

[ian1944]

As said, with totally random occurrences it's equivalent to the coupon collector's problem. If there are n items, the expected (= arithmetic mean) value of the number of occasions to see them all is E(n) = n(1 + 1/2 + 1/3 + ... +1/n), being 119.8 for n=30. Alternatively, E(n+1) = 1 + [(n+1)/n].E(n), with E(1) = 1.

 

[Springs Branch]

OP here again. Thanks for the contributions - the Coupon Collectors Problem does give the best insight into this.

One on-line explanation of the CCP includes the following statement which might ring true with bashers (the set size is 50 and I substituted trains/units and journey in place of the generic coupons & collect)

".... it takes very little time to cross off the first few trains. On the other hand, it takes a long time to collect the last few units. In fact, for 50 trains, it takes on average 50 journeys to travel on the very last unit after the other 49 have been collected. This is why the expected trips to travel on all trains is much longer than 50."

This is all viewed in the cold light of statistics - nothing to do with the vagaries of rail operations ("017 was in the Works after collision damage"..... etc)


While the Statistics textbook is still open, a supplementary question is:
"How many journeys must you make before better than 50% probability that one of the 30 units has been travelled on twice?"

This is a version of the well-known statistical Birthday Problem & my calculation is that 7 trips needed for >50% probability.

 

[Searle]

OP here again. Thanks for the contributions - the Coupon Collectors Problem does give the best insight into this.

One on-line explanation of the CCP includes the following statement which might ring true with bashers (the set size is 50 and I substituted trains/units and journey in place of the generic coupons & collect)

".... it takes very little time to cross off the first few trains. On the other hand, it takes a long time to collect the last few units. In fact, for 50 trains, it takes on average 50 journeys to travel on the very last unit after the other 49 have been collected. This is why the expected trips to travel on all trains is much longer than 50."

This is all viewed in the cold light of statistics - nothing to do with the vagaries of rail operations ("017 was in the Works after collision damage"..... etc)


While the Statistics textbook is still open, a supplementary question is:
"How many journeys must you make before better than 50% probability that one of the 30 units has been travelled on twice?"

This is a version of the well-known statistical Birthday Problem & my calculation is that 7 trips needed for >50% probability.

That's the number of trips I got (after looking up the formula online!)

 

[talltim]

One thing that hasn't been accounted for is that even if the units come off depot at random in the morning, they will probably stay on the the same diagram throughout the day
If you always travel to and from work at the same times each day, you could possibly end up catching the same unit on both journeys each day or always a different one on the out and return trips

 

[Springs Branch]

One thing that hasn't been accounted for is that even if the units come off depot at random in the morning, they will probably stay on the the same diagram throughout the day
If you always travel to and from work at the same times each day, you could possibly end up catching the same unit on both journeys each day or always a different one on the out and return trips

In my real-life situation, it's the case that the unit I have in the morning never works any of the trains I choose to return in the evening.
The timetable cycle means the morning's railcar is always elsewhere at home time.

It means I am choosing 1 from 30, then 1 from 29 units for the two daily trips.
Having fewer possible combinations slightly reduces the expected time to cover the full fleet, but the expected value has such variance that I don't anticipate this will guarantee much help!

In reality I am commuting in Adelaide, South Australia, using Adelaide Metro's 3000-class railcars.
Current count is 26 out of 30 units (87%) in 78 single trips.
And working on these kinds of puzzle helps relieve the monotony.

 

[12CSVT]

I'd say it is entirely down to luck, unless you happen to know where a certain unit is.

To give an example, here's a couple of my own bashing trips.

A few years ago I went to East Anglia to track down the two remaining Anglia DMUs I required (153335 and 170272). Shortly after arriving at Ely, the 170 turned up with a Norwich - Cambridge service, so I took this to Cambridge. Within minutes of arriving at Cambridge the 153 arrived with an Ipswich service.

Contrast this with earlier this week then I spent a whole day at Crewe trying to track down the last class 390 I require in extended form (390153). During the time I was there, 27 of the 35 eleven car 390s passed through but not 390153.

 

[Searle]

I'd say it is entirely down to luck, unless you happen to know where a certain unit is.

To give an example, here's a couple of my own bashing trips.

A few years ago I went to East Anglia to track down the two remaining Anglia DMUs I required (153335 and 170272). Shortly after arriving at Ely, the 170 turned up with a Norwich - Cambridge service, so I took this to Cambridge. Within minutes of arriving at Cambridge the 153 arrived with an Ipswich service.

Contrast this with earlier this week then I spent a whole day at Crewe trying to track down the last class 390 I require in extended form (390153). During the time I was there, 27 of the 35 eleven car 390s passed through but not 390153.

That's the cruel way that probability works! If it's any consolation, the more classes you try to finish, the more average the time you'll have to wait will be (in general of course!)

 

[Searle]

Interestingly, in our latest set of lectures we came across this problem, but in a different form (naturally I changed the example of fishing in my personal notes to unit bashing!), in our lecture on Cryptography (Code Solving and related). If anyone's interested, I can send them some lecture notes and give them some background information on how the problem links into Cryptography. Give me a PM if you're interested :P