# A so-called random variable not being well-defined

Consider this algorithm:

 RANDOMIZED-SELECT(A, p, r, i)
1 if p == r
2  return A[p]
3 q = RANDOMIZED-PARTITION(A, p, r)
4 k = q - p + 1
5 if i == k // the pivot value is the answer
6  return A[q]
7 elseif i < k
8  return RANDOMIZED-SELECT(A, p, q - 1, i)
9 else return RANDOMIZED-SELECT(A, q + 1, r, i - k)


The book CLRS claims that if we set $$T(n)$$ to be the running time of the algorithm on an input $$A$$ of size $$n$$, then $$T$$ is a random variable. However, I think it's not since if we define $$\Omega$$ to be the set of all inputs of all sizes $$n$$ and set $$\mathcal{F}$$ as $$\mathcal{P}(\Omega)$$ and let $$T$$ to be a function from $$\Omega$$ to $$\mathbb{R}$$, if $$n = m$$ then it doesn't follow that $$T(n) = T(m)$$ since the algorithm might have different running times on arbitrary inputs of the same size. Also note that the algorithm is randomized. So why does it say that $$T$$ is a random variable?

I'm not sure I understand your counterargument but look at it like this:

For given $$n$$ define $$\Omega_n$$ to be all inputs of size $$n$$ and $$\mathcal{F_n} = \mathcal{P}(\Omega_n)$$.

Let $$(T_{n})_{n\in\mathbb{N}}$$ be a sequence of functions:

$$T_{n} : \Omega_n \rightarrow \mathbb{R}$$

Clearly $$\forall t,n. \{\omega \mid T_{n}( \omega) \leq t \} \in \mathcal{F_n}$$, which shows that $$\forall n. T_{n}$$ is a random variable on $$\Omega_n$$.

• Of course we don't need the $T(n, \omega)$ part. Actually, we need to show for any $A$ it's true that $T_{n}^{-1} (A) \in \mathcal{F}_{n}$ which is obvious but the argument is true.
Our input is specific, but the input maybe have different permutations, so we can't claim that $$T$$ is a function that map set of all inputs to $$\mathbb{R}$$. But i think, it's true that we look at $$T$$ as a function that map a input to a permutation, formally, let $$X$$ be the input of size $$n$$, and denote $$\mathfrak S_n$$ be the group of the permutations of $$X$$ : $$T:X\to \mathfrak S_n.$$ So $$T$$ is a random variable that map input $$X$$ of size $$n$$ to $$\mathfrak S_n$$.
• Since $T$ must be the running time I think we can't define it that way. However, if we compose this function with another function mapping each element of $S_{n}$ to its running time and consider the sequence of such composed functions, then it's something.