If we consider the following algorithms,
RANDOMMAX($A[1...n]$)
//$A$ is an array of $n$ arbitrary integers
$max = -\infty$
for $i=1$ to $n$ in random order
if $A[i]> max$
$max$ = $A[i]$
return $max$
What is the probability that the line $max$ = $A[i]$ will be executed during the last iteration of the for loop? What is the expected number of execution of the line $max$ = $A[i]$?
My attempt is to model this in terms of an random variable $X$ which represents the number of times the line will be executed. The expectation of this random variable would give the average number of times this line will be executed. This could be broken down into indicator random variables where an each indicator random variable would represent whether the line $max$ = $A[i]$ would be executed in the $i$ iteration or not. How to proceed with these calculations?
I think you're on the right track.
Essentially, take a list of distinct integers and shuffle them; how many values in the shuffled list are bigger than anything that came before?
As you say, you can write the number as a sum of indicator random variables. So $E(X)=\sum_{i=1}^nE(X_i)$ where $X_i=1$ if the $i$th number you look at is the biggest so far, and $X_i=0$ otherwise. Since we process the list in a random order, the first $i$ elements also appear in a random order, so the probability that the $i$th element is the biggest of the first $i$ is just $1/i$.