Complexity of keeping track of $K$ smallest integers in a stream
If the value of the $i$-th element is $x$, it causes a heapify, if and only if $j &lt; K$ of the previous $i-1$ elements are smaller than $x$. This gives

$$E[X_i] = \frac{1}{N^i} \sum_{x=1}^N \sum_{j=0}^{K-1} c_{j,x},$$

where $c_{j,x}$ is the number of sequences of $i-1$ elements, of which exactly $j$ are smaller than $x$.

Now, to determine $c_{j,x}$, note that there are $\binom{i-1}{j}$ possibilities for the positions of the smaller elements in the sequence. For each of the smaller elements there are $x-1$ possibilities for its value, while for the larger or equal elements there are $N-x+1$ possibilities. This yields
$c_{j,x} = \binom{i-1}{j} (x-1)^j (N-x+1)^{i-1-j}$, and thus overall (after shifting $i$ and $x$ by $1$)

$$E[X] = \sum_{i=0}^{R-1}\frac{1}{N^{i+1}} \sum_{x=0}^{N-1} \sum_{j=0}^{K-1} \binom{i}{j} x^j (N-x)^{i-j}.$$

Unfortunately, all my attempts at bringing this formula into a simpler/closed form have been unsuccessful.