N = 10000 # number of MC simulations

set.seed(12345)

cost_to_go_a = rep(NA, N)
cost_to_go_b = rep(NA, N)
cost_to_go_c = rep(NA, N)
for( si in 1:N ){

    # What are the costs on two outgoing links we see:
    #
    c12_hat = sample( c(2, 10), 1, prob=c(0.4, 0.6) )
    c13_hat = sample( c(2, 8), 1, prob=c(0.2, 0.8) )
    c24_hat = sample( c(3, 9), 1, prob=c(0.5, 0.5) )
    c34_hat = sample( c(4, 8), 1, prob=c(0.5, 0.5) )

    # Part (a):
    #
    if( c12_hat < c13_hat ){
        # Go to 2:
        #
        cost_to_go_a[si] = c12_hat + c24_hat
    }else{
        # Go to 3:
        #
        cost_to_go_a[si] = c13_hat + c34_hat
    }

    # Part (b):
    #
    cost_to_go_b[si] = min( c( c12_hat + c24_hat, c13_hat + c34_hat ) )

    # Part (c):
    #
    if( runif(1) < 0.5 ){ # flip a coin to determine which path to take
        # Go to 2:
        #
        cost_to_go_c[si] = c12_hat + c24_hat
    }else{
        # Go to 3:
        #
        cost_to_go_c[si] = c13_hat + c34_hat
    }
}
V_a = mean(cost_to_go_a)
s_a = sd(cost_to_go_a)
V_b = mean(cost_to_go_b)
s_b = sd(cost_to_go_b)
V_c = mean(cost_to_go_c)
s_c = sd(cost_to_go_c)

print(sprintf('V_a= %.3f (%.2f); V_b= %.3f (%.2f); V_c= %.3f (%.2f)', V_a, s_a/sqrt(N), V_b, s_b/sqrt(N), V_c, s_c/sqrt(N)))