Probability of ending up with Rhode island

[willem2]

Today the youtube algorithm directed me to a video of someone playing geoguessr in the US until he got all of the 50 states at least once.



If all states are equally likely this would take about 50*ln(50) tries. 50*(1+1/2+1/3+ ... 1/50), so about 200.
Of course all states aren't equally likely. I thought you'd end up clicking hundreds of times with only Rhode Island left. I saw 3 video's and they all ended with some other state. The process still takes hours.
I then wondered how to compute the probability you'd end up in with a certain state, and the number of maps you'd have to see.

I can only think of an algorithm with time complexity of n!, so this won't get far beyond 10.

S is a set of states.
p_i with i ∈ S is the probability the state i comes up. The input for the algorithm
L(S, i) is the probability that i is the last state, if you start with the set of states S.
T(S) is the number of maps you have to view until you are done if you have the set of states S left.

$$L(S,i) = \frac { \sum_{j \in S \land j \ne i } p_j L(S \setminus \{ j \}, i) } { \sum_{j \in S} p_j }$$

$$T(S) = \frac { 1 + \sum_{j \in S} p_j T(S \setminus \{ j \} ) } { \sum_{j \in S} p_j }$$

and L({i}, i) = 1 en T({i}) = 1/p_i to kick off the recursion.

For each set of N states, you recurse once for each subset of N-1 states.

This can be done with a short if not efficient python program

prob = [0.01, 0.04, 0.05, 0.1, 0.3, 0.5]

def prob_last(s, i):
    if len(s) == 0:
        print ('Error')
        return 0;
    if len(s) == 1:
        return 1

    sum = 0
    for j in s:
        sum += prob[j-1]
    sumprob = 0
    for j in s:
        if j != i:
            sumprob += prob[j-1] * prob_last ([k for k in s if k != j], i)
    return sumprob/sum

      
for i in range (1, len(prob)+1):
    print( i, prob[i-1], prob_last(range(1, len(prob)+1), i))

with output

1 0.01 0.7210365685084836
2 0.04 0.14655804293227526
3 0.05 0.10298312628916247
4 0.1  0.027588400240604494
5 0.3  0.0015509841743875583
6 0.5  0.00028287785508652823

This takes less than a second for N = 10, but needs to be left overnight for N = 15
Can someone compute this quicker?

 

[anuttarasammyak]

Say the game ends when all the states are visited, the probability of a defined state which you said Rhode Island to be the goal would become $\frac{1}{50}$.

 

[PeroK]

If all states are equally likely this would take about 50*ln(50) tries. 50*(1+1/2+1/3+ ... 1/50), so about 200.
Of course all states aren't equally likely. I thought you'd end up clicking hundreds of times with only Rhode Island left. I then wondered how to compute the probability you'd end up in with a certain state, and the number of maps you'd have to see.

Can someone compute this quicker?

What you have is a series of binomial experiments with changing probability. If there are $n$ states left, then the probability of picking one of them is $n/50$. And, the expected number of trials until you get one is $50/n$. The expected number of trials for the whole game is equal to $$\sum_{n = 1}^{50} \frac {50}{n} \approx 225$$
PS As above, each state is equally likely to be the last.

 

[willem2]

Note I am trying to compute this for the case where the states are not equally likely, and you are likely to end up with a small state like Rhode Island.

 

[PeroK]

Note I am trying to compute this for the case where the states are not equally likely, and you are likely to end up with a small state like Rhode Island.

Sorry, I missed that! Certainly makes it tricky.