[Probability] Expected Value of Random Variable

[trash]

Homework Statement

A man wants to travel to four cities (A,B,C,D) but he has such a bad memory that he can't remember the cities that visited, therefore, if he travel to city A he can choose between (B,C,D) and if he then travel to B he can choose between (A,C,D).
Find v, If v it's the expected value of how many times he would have to travel before visited all cities at least once.

Homework Equations

X= "# of times required to visit all cities at least once."
[itex]E(X) = \Sigma xp_{X}(x)itex]

The Attempt at a Solution

I'm having some issue trying to find the probability function [itex]p_{X}(x)[/itex].
Since he already traveled to some city -let's say A- and then travels to another city -let's say B-, then P("going to another city not traveled before") = {C,D}/{A,C,D} = 2/3.
It seems to me that P{X=4}= (2/3)*(1/3).

Now, how can i get P {X=n} ?. I've been thinking about a binomial distribution, but it doesn't seem quite right because with X~Bin(n,p) i can't just use one value of p -that changes depending of how many different cities he already visited.

 

[mfb]

It seems to me that P{X=4}= (2/3)*(1/3).

Right.

What is the probability that the man visited just 2 cities after n visits? What is the probability that he visited just 3?
If you know those two, it is easier to calculate p(x).

 

[Ray Vickson]

Homework Statement

A man wants to travel to four cities (A,B,C,D) but he has such a bad memory that he can't remember the cities that visited, therefore, if he travel to city A he can choose between (B,C,D) and if he then travel to B he can choose between (A,C,D).
Find v, If v it's the expected value of how many times he would have to travel before visited all cities at least once.

Homework Equations

X= "# of times required to visit all cities at least once."
[itex]E(X) = \Sigma xp_{X}(x)itex]

The Attempt at a Solution

I'm having some issue trying to find the probability function [itex]p_{X}(x)[/itex].
Since he already traveled to some city -let's say A- and then travels to another city -let's say B-, then P("going to another city not traveled before") = {C,D}/{A,C,D} = 2/3.
It seems to me that P{X=4}= (2/3)*(1/3).

Now, how can i get P {X=n} ?. I've been thinking about a binomial distribution, but it doesn't seem quite right because with X~Bin(n,p) i can't just use one value of p -that changes depending of how many different cities he already visited.

This is much like the "coupon collector's problem", except that here we cannot immediately collect a coupon of the type that we have just now collected. See, eg., http://en.wikipedia.org/wiki/Coupon_collector's_problem

The number of trips is a sum on three independent, but not identically-distributed geometric random variables. Getting the mean is a lot easier than getting the whole probability distribution.

 

[trash]

Thanks, both of you.

Right.

What is the probability that the man visited just 2 cities after n visits? What is the probability that he visited just 3?
If you know those two, it is easier to calculate p(x).

Let me give it a try:
>What is the probability that the man visited just 2 cities after n visits?
He's in a random city and travel to another random city, then if he chooses always the city he already visited from a total of three, then

P{"the man visited just 2 cities after n visits" } = (1/3)^(n-2)

>What is the probability that he visited just 3?
I'm not sure if i know how to do this, but here what I'm heading:
Case 1: After he arrives to the second city he chooses a different city, then keep traveling between
---> P (case 1) = (2/3)^(n-2)
Case 2: After he arrives to the second city he chooses a city he already visited, then a different city:
---> P (case 2) = (1/3)[(2/3)^(n-3)]
...
Case k: After he arrives to the k city he chooses a city he already visited k times, then a different city:
---> P (case k) = (1/3)[(2/3)^(n-(k+1))]

And P{"What is the probability that he visited just 3?"} = [itex]\bigcup[/itex] P(case i)

Then P("the man visited just 4 cities after n visits") = 1 - P("the man visited just 3 cities after n visits") - P("the man visited just 2 cities after n visits").

This is much like the "coupon collector's problem", except that here we cannot immediately collect a coupon of the type that we have just now collected. See, eg., http://en.wikipedia.org/wiki/Coupon_collector's_problem

The number of trips is a sum on three independent, but not identically-distributed geometric random variables. Getting the mean is a lot easier than getting the whole probability distribution.

Then, for this excersise would be something like "Suppose that there are 4 types of cities, and that each day a traveler randomly visit one of those with probability pi corresponding to the ith city, how many travels do you expect he needs to do before having visited every city at least once?"

Maybe can i use the k cases i used before -the corresponding pi-?

 

[Ray Vickson]

Thanks, both of you.



Let me give it a try:
>What is the probability that the man visited just 2 cities after n visits?
He's in a random city and travel to another random city, then if he chooses always the city he already visited from a total of three, then

P{"the man visited just 2 cities after n visits" } = (1/3)^(n-2)

>What is the probability that he visited just 3?
I'm not sure if i know how to do this, but here what I'm heading:
Case 1: After he arrives to the second city he chooses a different city, then keep traveling between
---> P (case 1) = (2/3)^(n-2)
Case 2: After he arrives to the second city he chooses a city he already visited, then a different city:
---> P (case 2) = (1/3)[(2/3)^(n-3)]
...
Case k: After he arrives to the k city he chooses a city he already visited k times, then a different city:
---> P (case k) = (1/3)[(2/3)^(n-(k+1))]

And P{"What is the probability that he visited just 3?"} = [itex]\bigcup[/itex] P(case i)

Then P("the man visited just 4 cities after n visits") = 1 - P("the man visited just 3 cities after n visits") - P("the man visited just 2 cities after n visits").


Then, for this excersise would be something like "Suppose that there are 4 types of cities, and that each day a traveler randomly visit one of those with probability pi corresponding to the ith city, how many travels do you expect he needs to do before having visited every city at least once?"

Maybe can i use the k cases i used before -the corresponding pi-?

Assume he starts is some city, so that starting place is a "visit", but is not a "trip". (If you don't like that convention, just shift the number of steps by 1.) So, he starts by having visited 1 city. On the first step he travels to some other city, so after 1 step he will have visited 2 cities. After that, the number of steps N3 he needs to take to visit a new (as-yet-unvisited) city is a geometric random variable with success probability p3 = 2/3. Once a new city has been visited (so he has now visited 3 different cities) the number of steps N4 he needs to take to take to first visit the 4th city is a geometric random variable with success probability p4 = 1/3. The total number of steps is N = 1 + T3 + T4, where T3 and T4 are independent. Of course, the expected value is EN = 1 + E(T3) + E(T4), and this is easy to get (because there are standard formulas for the expected value of a geometric random variable).

We can get the probability P{N = n}, n = 3,4,5, ... either by computing the convolution of the two geometric distributions, or by using generating-function methods.