anyone know how to solve the problem

[Byte]

A tourist wants to visit n cities and starts by choosing one at random. After visiting a city, the tourist selects the next one among the rest (regardless of whether a city has been visited already) with equal probability. Find the expected number of trips required until all n cities have been visited.

 

[ajpa123]

tourist needs to hire an assistant. problem solved.

 

[SVT Cobra]

42^n^2

 

[mugs]

Just guessing... 2N

 

[DAGTA]

Traveling salesman problem... it's a classic. Search for 'traveling salesman problem' in google and read the variations. Should help you out.

 

[mugs]

Originally posted by: DAGTA
Traveling salesman problem... it's a classic. Search for 'traveling salesman problem' in google and read the variations. Should help you out.

This isn't the travelling salesman problem. Travelling salesman is a path optimization problem.

 

[shortylickens]

Dont wanna sound like a dummy here, but couldnt the answer be infinity?

I mean, if he has a chance to revisit cities and its all random, isnt it possible he could never get to all of them?

 

[mugs]

Originally posted by: shortylickens
Dont wanna sound like a dummy here, but couldnt the answer be infinity?

I mean, if he has a chance to revisit cities and its all random, isnt it possible he could never get to all of them?

That's not the expected outcome though.

 

[DAGTA]

Originally posted by: mugs

Originally posted by: DAGTA
Traveling salesman problem... it's a classic. Search for 'traveling salesman problem' in google and read the variations. Should help you out.

This isn't the travelling salesman problem. Travelling salesman is a path optimization problem.

It's a variation on the travelling salesman problem, as I stated in my first post.

 

[sniperruff]

n! (not exclaimation mark)

 

[Fenixgoon]

Originally posted by: sniperruff
n! (not exclaimation mark)

indeed, n! (factorial)

 

[Kyteland]

As best as I can figure the answer to the problem is f(n) = 1+n/(n-1)*f(n-1) where f(1)=1. Keep in mind that this is far from a statistical proof. The logic behind it is that the nth city is obviously the last one picked, so you've only visited it once. That gives you the f(n)=1+(something) part. For the remaining n-1 cities you apply the recursive definition of the problem, but for each of them you expect to visit it 1/(1-1/n) times, that being the geometric series of (1/n). 1/(1-1/n)=n/(n-1), so that makes the (something) part of the last equation to be n/(n-1)*f(n-1).

I verified it with a simple simulation and some tables in excel.

Edit: Oops, looking back at this I made a mistake. I assumed that you could visit the city you are currntly in, which is wrong.

 

[gar3555]

whats with everyone bringing there Combinatorial homework here all of a sudden

 

[Kyteland]

Aparantly that formula above has non-recursive solution
f(n) = 1+n/(n-1)*f(n-1)
=n*h(n), where h(n) is the harmonic series. h(n)=sum(1,n,1/n)

 

[Wallydraigle]

Originally posted by: mugs

Originally posted by: shortylickens
Dont wanna sound like a dummy here, but couldnt the answer be infinity?

I mean, if he has a chance to revisit cities and its all random, isnt it possible he could never get to all of them?

That's not the expected outcome though.

If I planned my trips that way, I would expect to be beaten about the head and laughed at, because that's pretty weak.

 

[IHateMyJob2004]

Originally posted by: mugs

Originally posted by: shortylickens
Dont wanna sound like a dummy here, but couldnt the answer be infinity?

I mean, if he has a chance to revisit cities and its all random, isnt it possible he could never get to all of them?

That's not the expected outcome though.

With what probability is it expected?

 

[Byte]

Originally posted by: gar3555
whats with everyone bringing there Combinatorial homework here all of a sudden

Because some of us actually go to school, and someone needs to go to THEIR english class.