Understanding Expected Running Time of Randomized Algorithms
There are two notions of expected running time here. Given a randomized algorithm, its running time depends on the random coin tosses. The expected running time is the expectation of the running time with respect to the coin tosses. This quantity depends on the input. For example, quicksort with a random pivot has expected running time $\Theta(n\log n)$. This quantity depends on the length of the input $n$.
Given either a randomized or a deterministic algorithm, one can also talk about its expected running time on a random input from some fixed distribution. For example, deterministic quicksort (with a fixed pivot) has expected running time $\Theta(n\log n)$ on a randomly distributed input of length $n$. This is known as average-case analysis. Your example of linear search fits this category.
A related concept is smoothed analysis, in which we are interested in the expected running time of an algorithm in the neighborhood of a particular input. For example, while the simplex algorithm has exponential running time on some inputs, in the &quot;vicinity&quot; of each input it runs in polynomial time in expectation.