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 times \(L\) is assigned a value is the \(n\)th Harmonic number \(H_n\).

Step-by-step solution

Understanding the Problem

The problem asks us to understand how often the variable \(L\) is updated to be the largest element as we iterate through the array \(A\). We start with \(L = A[1]\) and compare \(L\) with each subsequent element \(A[i]\). By the condition of \(X_i\), it indicates if \(A[i]\) is larger than all previous elements, meaning \(L\) would be updated.

Define \(X_i\) and Its Implications

Define \(X_i = 1\) if the element \(A[i]\) is a new maximum compared to any of the previous elements \(A[1:i-1]\). Hence, \(X_i = 1\) if \(L\) gets updated to \(A[i]\). The sum \(X_1 + X_2 + \cdots + X_n\) counts how many times \(L\) is updated, since \(X_i = 1\) each time \(L = A[i]\) becomes the new largest value.

Calculate Expected Value of \(X_i\)

For any specific element \(A[i]\), the probability \(A[i]\) is larger than all preceding elements in their initial random order is \(\frac{1}{i}\), as any of the first \(i\) elements could be the largest with equal probability. Thus, \(\mathbb{E}[X_i] = \frac{1}{i}\).

Expected Number of Updates for \(L\)

Using linearity of expectation, calculate the expected number of updates: \(\mathbb{E}[X_1 + X_2 + \cdots + X_n] = \mathbb{E}[X_1] + \mathbb{E}[X_2] + \cdots + \mathbb{E}[X_n] = 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n}\). This is equivalent to the \(n\)th Harmonic number, \(H_n\).

Conclusion

The expected number of times \(L\) is assigned a value is the \(n\)th Harmonic number \(H_n\). This is approximately \(\ln(n) + \gamma\), where \(\gamma\) is the Euler-Mascheroni constant, as \(n\) becomes large.

Key concepts

Harmonic Numbers

Harmonic numbers appear naturally in various algorithmic contexts, especially in analysis involving average-case scenarios. A harmonic number, denoted as \(H_n\), is the sum of the reciprocals of the first \(n\) natural numbers. It is represented mathematically as:

\[ H_n = 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n} \]

This sum grows logarithmically, which means that as \(n\) becomes very large, \(H_n\) approximates \(\ln(n) + \gamma\), where \(\gamma\) is the Euler-Mascheroni constant, approximately equal to 0.577.
Harmonic numbers are crucial when evaluating the expected performance of algorithms, especially those involving comparisons, such as finding the maximum value in an array. In the given exercise, the expected number of updates to the highest value is characterized by the \(n\)th harmonic number.

Expectation in Probability

Understanding the expectation of a random variable is vital in probability and algorithms. Expectation, sometimes referred to as the expected value, gives a measure of the center of a probability distribution. It tells us the average outcome we expect if we could repeat an experiment an infinite number of times.
In the context of this problem, each variable \(X_i\) tells us if a new maximum is found when scanning through an array. It's defined as 1 if a number is the new maximum and 0 otherwise. The probability that the \(i\)-th element is greater than all previous elements is the same as being the largest among the \(i\) elements. Thus, this chance is \(\frac{1}{i}\).
The expectation, \( \mathbb{E}[X_i] \), becomes \( \frac{1}{i} \) for each \(i\). By the linearity of expectation—a property that states the expected value of a sum of random variables is the sum of their expected values—the calculation of expected updates to \(L\) simplifies to a sum of expectations: \(1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n}\), which is the harmonic number \(H_n\). This powerful rule significantly simplifies complex calculations, especially those involving independent random processes.

Array Maximum Selection

The task of identifying the maximum element in an array is fundamental in computer science and algorithm design. It frequently involves iterating through the array while maintaining the largest value observed so far.
To find the maximum value in an array \(A\) of length \(n\), we initially set \(L = A[1]\). We then compare \(L\) to each subsequent element \(A[i]\) and update \(L\) whenever a new maximum is found. The key here is understanding when updates occur—each update represents an element larger than any of its predecessors.
This scenario introduces random variables \(X_i\), each denoting whether an update happens at step \(i\). The sum \(X_1 + X_2 + \cdots + X_n\) equals the total number of updates to \(L\). Calculating the expected sum provides insights into the algorithm's average performance. As previously noted, due to the initial randomness of elements, this expectation aligns with the harmonic number \(H_n\), highlighting the often logarithmic growth rate in complexity related to maximum selection.