Question

Given an array \(A\) of length \(n\) (chosen from some set that has an underlying ordering), you can select the largest element of the array by first setting \(L=A[1]\) and then comparing \(L\) to the remaining elements of the array, one at a time, replacing \(L\) with \(A[i]\) if \(A[i]\) is larger than \(L\). Assume that the elements of \(A\) are randomly chosen. For \(i>1\), let \(X_{i}=1\) if an element \(i\) of \(A\) is larger than any element of \(A[1: i-1]\). Let \(X_{1}=1 .\) What does \(X_{1}+X_{2}+\cdots+X_{n}\) have to do with the number of times you assign a value to \(L ?\) What is the expected number of times you assign a value to \(L\) ?

Short answer

The expected number of assignments to \(L\) is the \(n\)-th Harmonic number \(H_n\).

Step-by-step solution

Understanding the Role of X Variables

Each variable \(X_i\) is an indicator that the element \(A[i]\) is larger than any previous element \(A[1] \text{ to } A[i-1]\). So, it equals 1 when a new maximum is found as you iterate through the array. Since you initialize with \(X_1 = 1\), it means \(A[1]\) sets the initial largest value.

Counting the Assignments to L

The number \(X_1 + X_2 + \cdots + X_n\) is the count of times the variable \(L\) is updated in the algorithm. This represents finding a new largest value within the array as we make comparisons. \(L\) is initially assigned and updated whenever \(X_i = 1\).

Calculate the Expected Value

The expected number of updates to \(L\) can be found by calculating \(E[X_1 + X_2 + \cdots + X_n]\). By linearity of expectation, this equals \(E[X_1] + E[X_2] + \cdots + E[X_n]\). Since \(X_1 = 1\) always, \(E[X_1] = 1\).

Analyzing Indicator Random Variables

For each \(i > 1\), \(E[X_i]\) is the probability that \(A[i]\) is larger than all of \(A[1] \text{ to } A[i-1]\). Given the elements are randomly ordered, \(A[i]\) is equally likely to be any position, meaning \(E[X_i] = \frac{1}{i}\).

Calculating Total Expected Assignments

Since \(E[X_1] = 1\) and \(E[X_i] = \frac{1}{i}\) for \(2 \leq i \leq n\), the expected number of assignments is \(E[X_1] + E[X_2] + \cdots + E[X_n] = 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n}\). This is the \(n\)-th Harmonic number \(H_n\), which is approximately \(\log n + \gamma\) where \(\gamma\) is the Euler-Mascheroni constant.

Key concepts

Expected Value

The concept of the expected value in randomized algorithms helps predict the average outcome after many iterations of a process. For a random variable, it provides a measure of the central tendency of possible outcomes. It is like calculating an average, but instead of arithmetic mean of numbers, it's a weighted average of all possible values the random variable can take, weighted by their probabilities.

In the scenario given in the exercise, the expected value determines how many times we expect to assign a new value to the variable \(L\) as we search for the largest element in an array. The formula for expected value \(E\) of a random variable \(X\) is when you multiply each possible value of \(X\) by its probability and sum it all up: \[E[X] = \sum_i x_i \times P(x_i) \]

In the step-by-step solution, we need to calculate the expected value of the sum \( X_1 + X_2 + \cdots + X_n \), which simply gives the average number of times the assignment happens in random scenarios. This is important in analyzing the efficiency of algorithms.

Harmonic Numbers

Harmonic numbers come into play when dealing with sums of the form \(1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n}\). These sums appear quite frequently in problems related to expected values in randomized algorithms. A harmonic number, denoted as \(H_n\), is defined as the sum of the reciprocals of the first \(n\) natural numbers.

The approximate formula for the \(n\)-th harmonic number is:
\[H_n \approx \log n + \gamma \]where \(\log n\) is the natural logarithm of \(n\) and \(\gamma\) is the Euler-Mascheroni constant, approximately equal to 0.5772.

In the exercise, we're using harmonic numbers to express the expected number of times you assign to \(L\) because the sum \(1 + \frac{1}{2} + \cdots + \frac{1}{n}\) is exactly represented by \(H_n\). This illustrates an elegant convergence between discrete mathematics and real analysis, showing how these concepts underpin algorithm performance prediction.

Linearity of Expectation

Linearity of expectation is a powerful principle in probability theory used to simplify the computation of expected values. It says that the expected value of the sum of random variables is the sum of their expected values, regardless of whether the random variables are independent or not.

For expressions like \(E[X_1 + X_2 + \cdots + X_n]\), linearity provides a straightforward way to compute this "average." Mathematically, it is written as:

\[E[X_1 + X_2 + \cdots + X_n] = E[X_1] + E[X_2] + \cdots + E[X_n] \]
In the context of the exercise, each random variable \(X_i\) signifies whether a new maximum has been identified in the array at position \(i\). Using linearity, instead of computing the expected number of assignments directly, we find it separately for \(X_1, X_2, ..., X_n\) and sum them up. This simplicity holds **even** when \(\{X_i\}\) are dependent.

Thus, by recognizing linearity of expectation, we found that determining this expected number of assignments reduces to computing a harmonic number, making the computation both efficient and insightful.