How to prove that the expected depth of kth smallest element in a complete binary heap (min-heap) is O(logk)?

The previous answer is right, but I thought pictures might help.

The sample space (or probability space) is the set of all possible outcomes. And the individual probabilities of all these exclusive outcomes will add up to 1. For example, if there are only two mutually exclusive outcomes A and B in a particular sample space, and the chance of A is 1/4, then the chance of B has to be 3/4.

In your case, there are two outcomes: either k-1th smallest node is in the left subheap of the root or k-1th smallest is in the right subheap.

Before thinking about where we put the kth smallest node, the sample space looks like this below. The two outcomes are represented by a square and both squares are equal size (1/2 + 1/2 = 1)

But then the proposition said something like "let's assume the kth smallest node is in one of the subheaps, and let's choose left because we feel like it". There are N-1 nodes in total to choose from (N-1 because the root is not part of this selection). Below shows where we placed the kth smallest node. The overall number of nodes from which to choose the k-1th smallest, has changed (and that fact will alter the shapes in our sample space).

So now, the chance that the k-1th smallest node is in the left subheap has been reduced by (1/N-1).

And this is represented below by removing a triangle from the Black square. (It could have been any shape, but I chose a triangle). That triangle has to go somewhere, because everything has to add up to 1. Number of nodes is not relevant. We reduced the probability of one outcome by the size of that triangle, and consequently increased the probability of the other outcome by the same amount. The space looks like this now.

A probability tree is a useful ways to think about it.

First, we need 1/(N-1) because we are considering the left and right subtree of the root. Hence, as the size of the tree is N, we have N-1 nodes to be considered. Also, as mentioned, "Without loss of generality, we may assume that k-th smallest element is in the left subheap", so, the potential nodes in the left subheap are one less than the nodes in the right subheap. Therefore, the probability in the left subheap is 1/2 - 1/(N-1), and reasonably, the probability in the right subheap is 1 - the probability in the left subheap = 1 - (1/2 - 1/(N-1)) = 1/2 + 1/(N-1).