Breaking median records $\newcommand{\median}{\operatorname{median}}$
Suppose $X_1,X_2,X_3,\ldots$ are independent identically distributed real random variables.  The process $Y_n=\max\{X_1,\ldots,X_n\},\quad n=1,2,3,\ldots$ has been studied; one may ask, for example, what is the expected waiting time until the next time, after $n$, that the maximum increases, i.e. the "record is broken".
Now do with medians what was done above with maximums:
\begin{align}
N_1 & = \min\{ n : X_n = \median\{X_1,\ldots,X_n\} \} \qquad\text{(So $\Pr(N_1=1)=1.$)} \\[8pt]
N_2 & = \min\{n\ge N_1 : X_n = \median\{X_1,\ldots,X_n\}\} \\[8pt]
N_3 & = \min\{n\ge N_2 : X_n = \median\{X_1,\ldots,X_n\}\} \\[8pt]
N_4 & = \min\{n\ge N_3 : X_n = \median\{X_1,\ldots,X_n\}\} \\[8pt]
& {}\  \vdots
\end{align}
So the question is: What can be said about the probability distribution of the process $\{N_n : n = 1,2,3,\ldots\}$ or about $\{X_{N_n} : n=1,2,3,\ldots\}$?
 A: Some preliminary observations:
The analysis seems slightly simpler if we'd consider only odd values of $n$ (i.e: double time steps), and continuos densities. 
In this case, when we go from $2n-1$ to $2n+1$, the median keeps unchanged if the two new values fall on each side of the previous median, which has probability $2 F_x(a) (1-F_x(a))$ - where $a$ is the previous median value. Obviously, this tends to 1/2 when $n$ is large.
We can also compute the conditional probability that the median increases by an amount $\delta>0$ as:
$$f_{m(2n+1) \mid m(2n-1)}(a+\delta,a)=(1-F_x(a))(n+1)\left(\frac{1-F_X(a+\delta)}{1-F_X(a)}\right)^n f_X(a+\delta)$$
An analogous expression can be obtained for the probability of decrease, and hence it is possible, in principle, to compute the joint probability for the median value for odd $n$.
Update: Actually, the above is not enough to compute the full joint probabilities, because the sequence of medians is not a markov process - knowing the previous values gives less information than knowing all previous values.
