Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: Probability puzzle: Cars  (Citit de 12662 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
Cosmin
Echipa infoarena
Nu mai tace
*****

Karma: 351
Deconectat Deconectat

Mesaje: 1.799



Vezi Profilul
« : Noiembrie 14, 2014, 03:45:13 »

http://www.infoarena.ro/blog/cars
Memorat
raduberinde
Strain
*

Karma: 13
Deconectat Deconectat

Mesaje: 26



Vezi Profilul
« Răspunde #1 : Noiembrie 14, 2014, 05:25:35 »

First cluster happens at the minimum speed value, and for the cars ahead of that we have a similar smaller problem. Say a(N) is the expected number of clusters for N cars. For each car i, the probability that the i'th car is the slowest is 1/N. So
a(N) = sum(i=1 to N) 1/N * (1 + a(N-i))

By looking at Na(N) - (N-1)a(N-1) we get a(N) = 1/N + a(N-1) = sum(i=1 to N) 1/i

We could have also derived that directly by just looking at the first car: the probability that the first car is the minimum is 1/N, if it is it will form a cluster; if it is not this car won't matter. So a(N) = 1/N * (1 + a(N-1)) + (1 - 1/N) * a(N-1) = 1/N + a(N-1).

This is pretty much equivalent to the question of how many times you update the minimum so far when going through a random permutation, going from the first car to the last: each time you find a new minimum, that will be a separate cluster.
« Ultima modificare: Noiembrie 14, 2014, 05:36:54 de către Radu Berinde » Memorat
Cosmin
Echipa infoarena
Nu mai tace
*****

Karma: 351
Deconectat Deconectat

Mesaje: 1.799



Vezi Profilul
« Răspunde #2 : Noiembrie 14, 2014, 07:44:24 »

@Radu I should put the puzzles when Boston sleeps and Romania is up so it's not solved as quickly Tongue.
Memorat
Cosmin
Echipa infoarena
Nu mai tace
*****

Karma: 351
Deconectat Deconectat

Mesaje: 1.799



Vezi Profilul
« Răspunde #3 : Noiembrie 14, 2014, 07:56:15 »

Alex, no, it's not 2 sqrt n
Memorat
veleandu
De-al casei
***

Karma: 155
Deconectat Deconectat

Mesaje: 132



Vezi Profilul
« Răspunde #4 : Noiembrie 14, 2014, 07:59:36 »

"This is pretty much equivalent to the question of how many times you update the minimum so far when going through a random permutation, going from the first car to the last: each time you find a new minimum, that will be a separate cluster."

That was my first ideea too but it's not corect.
If you want to create a cluster, the new minimum should be at a distanve of at leaste 1
For example N .. 1
N updates but 0 clusters.

In this case the answer would've been 2sqrt
Because it's the expected value of "increasing sebsequene"
« Ultima modificare: Noiembrie 14, 2014, 08:08:48 de către Alex Velea » Memorat
Cosmin
Echipa infoarena
Nu mai tace
*****

Karma: 351
Deconectat Deconectat

Mesaje: 1.799



Vezi Profilul
« Răspunde #5 : Noiembrie 14, 2014, 08:14:56 »

Alex, the two problems are equivalent.

If A is the array of numbers in the min = a[ i] problem, then reverse(A) is the set of speeds in the car problem (if cars are going from left to right and A[0] is the last car).

On your example A = N .. 1 - n updates, reverse A = 1 .. N - n clusters

BTW 2 sqrt(n) is the average length of the LONGEST increasing subsequence, while here it's not the longest one.
« Ultima modificare: Noiembrie 14, 2014, 08:30:42 de către Cosmin Negruseri » Memorat
veleandu
De-al casei
***

Karma: 155
Deconectat Deconectat

Mesaje: 132



Vezi Profilul
« Răspunde #6 : Noiembrie 14, 2014, 10:10:58 »

I thought that a cluster if formed when 2 or more cars are stuck together  Cry
Sorry.

Memorat
vdobrota
Strain


Karma: 1
Deconectat Deconectat

Mesaje: 4



Vezi Profilul
« Răspunde #7 : Noiembrie 14, 2014, 11:39:11 »

Indeed, I got to the same result.
First car has a probability of 1 to be the head of a cluster.
The second car has a probability of 1/2 to be the head of a cluster. It's a head of a cluster only if it's smaller then car 1.
The third car has a probability of 1/3 to be the head of a cluster. It's a head of a cluster only if it's smaller then car 1 and car 2.
...
so the result is 1+1/2+1/3+...1/N, since all clusters need heads (they are not zombies, are they).
Memorat
raduberinde
Strain
*

Karma: 13
Deconectat Deconectat

Mesaje: 26



Vezi Profilul
« Răspunde #8 : Noiembrie 14, 2014, 14:33:13 »

Alex's interpretation is an interesting variant. If we want to only count clusters of 2+ cars:

a(N) = sum(i = 2 to N) (1/N * (1 + a(N-i)))

The difference is the missing a(N-1) term for i=1: if the first car is the minimum, no cluster will form.

This comes out to a(N) = 1/N [ 1 + a(N-2) + (N-1)a(N-1) ]
which makes sense: if the second car is the slowest (prob 1/N), it will form a cluster with the first car so the answer is (1 + a(N-2)), otherwise (prob (N-1)/N) we can ignore the first car (it will either be alone, or it will be part of the same cluster with the second car), so just a(N-1).
« Ultima modificare: Noiembrie 14, 2014, 14:45:23 de către Radu Berinde » Memorat
gogu
Client obisnuit
**

Karma: 42
Deconectat Deconectat

Mesaje: 98



Vezi Profilul
« Răspunde #9 : Noiembrie 14, 2014, 19:08:07 »

The problem’s been solved, but I’d like to post some insight into how you can do a Fermi-type estimation here:

The slowest car will block all other cars behind it, so about half of the cars are probably stuck in the biggest cluster. Since picking the largest cluster at each step removes a percentage of the total amount of cars (the percentage doesn't even matter), the answer is in the order of O(logN), which is ok to use as a rough approximation when the real answer is ~lnN (the value of the sum equals this when N is infinite).

Of course it’s always better to do the math, since it's just intuition that can be wrong, but this type of analysis is useful when it’s impractical to do the math or you just want a gut feeling if something is possible. If for instance you're removing chunks of something in the order of sqrt(N) cars at a time, then you'd be done in O(sqrt(N)) iterations, which was the case in Alex's assumption.
Memorat
pitrada
Strain


Karma: 5
Deconectat Deconectat

Mesaje: 5



Vezi Profilul
« Răspunde #10 : Decembrie 17, 2014, 08:51:24 »

Let vmax the maximum posible car speed, v(1), v(2), ..., v(N) the car speeds and p(N,k)=probability that k is the number of clusters. Than we have:

p(N,k)=v(N)/vmax*p(N-1,k-1)+(1-v(N)/vmax)*p(N-1,k)
Memorat
pitrada
Strain


Karma: 5
Deconectat Deconectat

Mesaje: 5



Vezi Profilul
« Răspunde #11 : Decembrie 30, 2014, 17:30:10 »

I guess i was wrong . Sorry !
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines