patternMinor
Summation of a Random Variable
Viewed 0 times
summationrandomvariable
Problem
I'm having trouble grokking Cormen's Algorithms book on pg. 120. The context is the hiring problem (as it is called in the book). Here is the part that is tripping me up:
"Let X be the random variable whose value equals the number of times we hire a new office assistant."
and later on:
"...we let $X_i$ be the indicator random variable associated with the event in which the $i$th candidate is hired ... [so that] $X = X_1 + X_2 + \ldots + X_n$"
In particular, Cormen defines $X_i$ as follows:
$$
X_i =
\begin{cases}
1 & \text{if candidate $i$ is hired} \\
0 & \text{otherwise}
\end{cases}
$$
Question: Why does $X = X_1 + X_2 + \ldots + X_n$?
First, this equation only makes sense if $X$ and each of the $X_i$ have the same domain. Here I'm assuming the domain of $X$ is $\{1,2, \ldots , n\}$ (i.e., each number representing the number of assistants hired).
That implies that the domain of each $X_i$ must be $\{1,2, \ldots , n\}$. Then it seems that, i.e., $X_2$ will satisfy $X_2(2) = 1$ and be $0$ everywhere else.
But if that's the case, then $X_1 + \ldots + X_n$ will satisfy $X(i) = 1$ for all $i \in \{1, \ldots , 6\}$, which means that $X \ne X_1 + \ldots + X_n$ (since, for example, $X(2) = 2$). What am I missing?
EDIT: The more I think about it, the more I'm convinced that my misunderstanding lies with the way $X$ itself is defined. Is it true that i.e. $X(2) = 2$?
"Let X be the random variable whose value equals the number of times we hire a new office assistant."
and later on:
"...we let $X_i$ be the indicator random variable associated with the event in which the $i$th candidate is hired ... [so that] $X = X_1 + X_2 + \ldots + X_n$"
In particular, Cormen defines $X_i$ as follows:
$$
X_i =
\begin{cases}
1 & \text{if candidate $i$ is hired} \\
0 & \text{otherwise}
\end{cases}
$$
Question: Why does $X = X_1 + X_2 + \ldots + X_n$?
First, this equation only makes sense if $X$ and each of the $X_i$ have the same domain. Here I'm assuming the domain of $X$ is $\{1,2, \ldots , n\}$ (i.e., each number representing the number of assistants hired).
That implies that the domain of each $X_i$ must be $\{1,2, \ldots , n\}$. Then it seems that, i.e., $X_2$ will satisfy $X_2(2) = 1$ and be $0$ everywhere else.
But if that's the case, then $X_1 + \ldots + X_n$ will satisfy $X(i) = 1$ for all $i \in \{1, \ldots , 6\}$, which means that $X \ne X_1 + \ldots + X_n$ (since, for example, $X(2) = 2$). What am I missing?
EDIT: The more I think about it, the more I'm convinced that my misunderstanding lies with the way $X$ itself is defined. Is it true that i.e. $X(2) = 2$?
Solution
Your outcomes are not the number of candidates but rather which candidates were hired: $\Omega = \{0,1\}^n$. Then you have $X_i(a_1, \dots, a_n) = a_i$ and $X(a_1, \dots, a_n) = \sum\limits_{i=1}^n X_i(a_1, \dots, a_n) = \sum\limits_{i=1}^n a_i$.
Context
StackExchange Computer Science Q#55708, answer score: 5
Revisions (0)
No revisions yet.