What is the probability the best case occurs? (Comp Sci Type Question)

Question

I'm having trouble figuring out what's the probability the best case occurs? It's my first time bringing together probabilistic knowledge into computer science. The question goes as such.

Consider this algorithm:

random(X,Y,Z):

  print(X)
  if Y != X:
      print(Y)
  if Z != Y and Z != X:
      print(Z)

You will suppose the inputs X,Y,Z are chosen at random, uniformly and independently from the set {1,...,k}, (for some k being >=1).

I know that both best and worst case run time of the algo is 1.

Thanks.

Answer 1

Define the best case senario.

I suspect the best case is just the one print call and just two compares. That the least number of function calls.

If that is so then you want to find: the probability of choosing the same value three times from a set of $k$. For every value of Y there is $1/k$ chance that X is the same value. Likewise for values of $Z$. Since they are independent; just multiply.

$$\begin{align}\mathsf P(Y=X\cap Y=Z) & = \sum_{y=1}^k \mathsf P(Y=y)\mathsf P(X=y)\mathsf P(Z=y) \\[1ex] & = \frac 1 {k^2} \end{align}$$

If we have mutually independent discretely uniform random variables; $X,Y,Z \sim {\cal U}\{1,.. k\}$

---

Now the worst case scenario would be the other extreme. $X\neq Y$, $Z\neq Y$, and $Z\neq X$; thus ensuring all three print calls are made.

There are ${k \choose 3}3!$ ways to select 3 distinct values for X,Y,Z from a set of $k$, each having probability of $1/k^3$.

$$\begin{align}\mathsf P(Y\neq X, Y\neq Z, Z\neq X) & = \sum_{y=1}^k \mathsf P(Y=y) \sum_{\substack{x=1\\:x\neq y}}^k \mathsf P(X=x\cap X\neq Y)\mathsf P(Z\neq x\cap Z\neq y) \\[1ex] & = \frac {(k-1)(k-2)}{k^2} \\[1ex] & = {k\choose 3}\frac {3!}{k^3} \end{align}$$