Question

A set of \(n\) cities is to be connected via communication links. The cost to construct a link between cities \(i\) and \(j\) is \(C_{i j}, i \neq j .\) Enough links should be constructed so that for each pair of cities there is a path of links that connects them. As a result, only \(n-1\) links need be constructed. A minimal cost algorithm for solving this problem (known as the minimal spanning tree problem) first constructs the cheapest of all the (in) links. Then, at each additional stage it chooses the cheapest link that connects a city without any links to one with links. That is, if the first link is between cities 1 and 2, then the second link will either be between 1 and one of the links \(3, \ldots, n\) or between 2 and one of the links \(3, \ldots, n .\) Suppose that all of the \(\left(\begin{array}{c}n \\\ 2\end{array}\right)\) costs \(C_{i j}\) are independent exponential random variables with mean \(1 .\) Find the expected cost of the preceding algorithm if (a) \(n=3\), (b) \(n=4\).

Short answer

The expected cost of the minimal spanning tree algorithm is: (a) For \(n=3\), the expected cost is \(\frac{5}{6}\). (b) For \(n=4\), the expected cost is \(\frac{11}{6}\).

Step-by-step solution

Find the initial connection cost

To connect the first two cities 1 and 2, we must consider the minimum of three exponential random variables, \(C_{12}, C_{23},\) and \(C_{13}\). The minimum of exponential random variables with the same mean (\(\mu=1\)) preserves its exponential property with the mean that is \(\mu'=1/3\).

Find the second connection cost

The next step is linking the third city to the already connected cities (1 and 2) by choosing the cheapest link. We can choose to link city 3 either with city 1 or city 2. In other words, we are choosing the minimum of two exponential random variables (\(C_{13}\) and \(C_{23}\), without the one that was taken in step 1). The minimum of two exponential random variables with the same mean (\(\mu=1\)) preserves its exponential property with the new mean that is \(\mu'=1/2\).

Calculate the expected cost

Since the variables are independent, we can calculate the total expected cost for the algorithm as the sum of the expected costs calculated in each step: Expected cost = \( \frac{1}{3}+\frac{1}{2}= \frac{5}{6}\) So, the expected cost when \(n=3\) is \(\frac{5}{6}\). ##Case (b): When \(n=4\)## Now, we need to find the expected cost for connecting four cities using the minimal spanning tree algorithm.

Find the initial connection cost

We again start by connecting the two closest cities, so we need to find the minimum of six exponential random variables: \(C_{12}, C_{13}, C_{14}, C_{23}, C_{24},\) and \(C_{34}\) (\({4 \choose 2} = 6\)). The minimum of six independent exponential random variables with the same mean (\(\mu=1\)) preserves its exponential property with the new mean \(\mu'=1/6\).

Find the second connection cost

Next, we will link the third city to the already connected cities by choosing the cheapest link. Let's say we connected city 1 and 2 initially, we can either choose to link the new city (3 or 4) with city 1 or city 2. We will again choose the minimum of two exponential random variables, without the one that was taken in step 1 and taking into account the 3 remaining options (\(\mu'=1/3\)).

Find the third connection cost

Now, we have the last city left to connect. It can either be connected to one of the three previously connected cities. In this last step, all the variables are equally probable, and we can just pick a single exponential random variable with mean 1. No need for a minimum since there are no other alternatives.

Calculate the expected cost

As before, since the variables are independent, we can calculate the expected cost for the algorithm as the sum of the expected costs for each step: Expected cost = \( \frac{1}{6}+\frac{1}{3}+1= \frac{11}{6}\) So, the expected cost when \(n=4\) is \(\frac{11}{6}\).

Key concepts

Probability Models

Understanding probability models is essential when dealing with randomized processes such as constructing minimal spanning trees with random costs. A probability model is a mathematical representation of a random phenomenon that is defined by its sample space, events within the sample space, and probabilities associated with each event.

For our minimal spanning tree problem, we use the probability model of exponential random variables to describe the random costs of constructing links between cities. Each cost, represented by an exponential random variable, is associated with the time between events in a Poisson process, which in this context are the construction of links. The exponential model is particularly useful because of its memoryless property, suggesting future probabilities do not depend on past values.

By utilizing this model, we can apply the properties of exponential random variables to compute the expected costs of constructing a minimal spanning tree, as demonstrated in the solutions for the cases where cities are numbered 3 and 4.

Exponential Random Variables

Exponential random variables play a pivotal role in modeling the time between independent events that occur continuously and at a constant average rate. They are characterized by a single parameter, commonly denoted as \(\lambda\), which indicates the rate of occurrence.

In our minimal spanning tree problem, the cost links between cities are modeled as exponential random variables with a mean of 1 (i.e., \(\lambda = 1\)). One interesting and useful characteristic is that the minimum of several exponential random variables with the same rate parameter also follows an exponential distribution, with a new rate parameter that is the sum of the individual rates. This concept facilitates the calculation of expected costs in the step-by-step solution provided for the problem in both cases of 3 and 4 cities.

Expected Cost Algorithm

An expected cost algorithm assists in forecasting the average outcome of a randomized process, considering all possible scenarios and their probabilities. In the context of the minimal spanning tree problem, the algorithm calculates the expected cost by taking into account the exponential distribution of each link's cost.

The underlying principle used to determine the expected cost of each stage in constructing the minimal spanning tree is the fact that the expected value of an exponential random variable is the inverse of its rate parameter. Combining the minimum cost at each stage, the algorithm proceeds iteratively until all cities are connected. This approach simplifies the complex problem of forecasting costs in a probabilistic setting and elicits a clear, step-wise path to finding the solution, ensuring each step minimizes the cost.

Combinatorial Optimization

Combinatorial optimization is the process of searching for the best solution from a finite set of possible solutions. This field of mathematics and computer science is often concerned with problems involving networks, like our minimal spanning tree problem.

The minimal spanning tree problem is a classic example of combinatorial optimization, where we are tasked to find the subset of edges (or links) that connects all vertices (or cities) at the minimal total cost. This problem requires careful analysis of combinations and permutations of links between cities, optimized via algorithms such as the expected cost algorithm applied in our exercise.

By leveraging the principles of combinatorial optimization, the minimal spanning tree problem is efficiently solved in a way that ensures each decision—to construct a link between cities—is optimized in terms of the overall cost objective. This clear objective helps in driving the step-by-step algorithm towards the most cost-effective solution.