Stochastic Variables

1. If Ω_X is a subset of the set of real numbers, then the variable is numeric; otherwise it is categorical.
2. If Ω_X is finite or countably infinite, then X is discrete.

• f_X(x) = P(X = x)

• f_X(x) = P({u ∈ Ω | X(u) = x}) = ∑_{u : X(u) = x} P(u)

• F_X(x) = P(X ≤ x)

• F_X(x) = ∑_{y ≤ x} f_X(y)

1. E[X] = ∑_{x ∈ ΩX} x ⋅ f_X(x)
2. Var[X] = ∑_{x ∈ ΩX} (x - E[X])² ⋅ f_X(x)

1. I[x] = - log₂ f_X(x)
2. H[X] = ∑_{x ∈ ΩX} I[x] = - ∑_{x ∈ ΩX} f_X(x) ⋅ log₂ f_X(x)

1. The joint probability of X and Y is given by their joint probability function f_{(X, Y)}:
   f_{(X, Y)}(x, y) = P(X = x, Y = y) = P({ (u, v) ∈ Ω_X × Ω_Y | X(u) = x, Y(v) = y })
2. The conditional probability of X given Y is given by the conditional probability function f_X|Y:
   f_X|Y(x | y) = P(X = x | Y = y) = P(X = x, Y = y) / P(Y = y)

1. Joint entropy: H[X, Y] = - ∑_{x ∈ ΩX} ∑_{y ∈ ΩY} f_{(X, Y)}(x, y) ⋅ log₂ f_{(X, Y)}(x, y)
2. Conditional entropy: H[X|Y] = - ∑_{x ∈ ΩX} ∑_{y ∈ ΩY} f_{(X, Y)}(x, y) ⋅ log₂ f_X|Y(x | y)

1. Joint probability:
   P(X₁ = x₁, ..., X_n = x_n) = P({ (u₁, ..., u_n) ∈ Ω_X1 × ... × Ω_Xn | X₁(u₁) = x₁, ..., X_n(u_n) = x_n })
2. Conditional probability:
   P(X₁ = x₁, ..., X_n = x_n | Y₁ = y₁, ..., Y_m = y_m) = P(X₁ = x₁, ..., X_n = x_n, ..., Y₁ = y₁, ..., Y_m = y_m) / P(Y₁ = y₁, ..., Y_n = y_m)

1. P(X = x|Y = y) = P(X = x) for all x, y
2. P(Y = y|X = x) = P(Y = y) for all x, y
3. H[X|Y] = H[X]
4. H[Y|X] = H[Y]

Slides for lecture 3

Suggested Reading

• Krenn, B. & Samuelsson, C. (1997) The Linguist's Guide to Statistics. Section 1.3-1.4, 2.2.
  (Concentrate on discrete variables.)
• Manning, C. D. & Schütze, H. (1999) Foundations of Statistical Natural Language Processing. MIT Press. Chapter 2.

Exercises

1. Consider the following stochastic variables and define, for each of them, a suitable domain (sample space) and range (value space):
   1. The number of syllables per word.
   2. The number of words per sentence.
   3. The lexeme of a word form.
   4. The word class (part-of-speech) of a word.
   5. The percentage of nouns in a text.
   Solution
   
   
2. Which of the variables in Exercise 1 are numerical?
   Which of them are discrete?
   Solution
   
   
3. Consider the experiment of throwing two dice and consider the stochastic variable X which maps the outcome to the sum of the two dice. We assume that the underlying experiment has a uniform probability distribution (i.e. that all outcomes are equally probable).
   1. What is the domain (sample space) of X?
   2. What is the range (value space) of X?
   3. Give the frequency function f_X.
   4. Give the distribution function F_X.
   5. Compute the expectation value E[X].
   6. Compute the variance Var[X].
   Solution
   
   
4. Consider the experiment of randomly choosing a pair of two adjacent words from a text. Let X₁ be the stochastic variable which maps the first word to its word class (part-of-speech), and let X₂ be the stochastic variable which maps the second word to its word class. Suppose we know the following probabilities:
   
   

   P(X₂ = noun) = 0.2

   P(X₂ = adjective) = 0.05

   P(X₁ = article | X₂ = noun) = 0.3

   P(X₁ = article | X₂ = adj) = 0.6

   P(X₁ = article | X₂ is neither noun nor adjective) = 0

   
   Compute the probability that
   1. the first word is an article,
   2. the second word is a noun, given that the first is an article,
   3. the second word is an adjective, given that the first is an article,
   4. the second word is a noun or an adjective, given that the first is an article.
   Solution
   
   
5. Show that the two variables in Exercise 4 are not independent.
   Solution
   
   
6. Consider the experiment of randomly choosing a word from an English text, and consider the following stochastic variables:
   
   

   X(w) = w (i.e. X maps a word to its orthographic form).

   Y(w) = 1 if w="the", 0 otherwise.

   
   Assume that f_X("the") = 0.02 (where f_X is the frequency function of the variable X). Compute
   1. the frequency function f_Y of the variable Y,
   2. the expectation value of Y,
   3. the variance of Y.
   Solution
   
   
7. Let X be the stochastic variable which gives us the sum of two dice. What is the surprise value (information value) associated with the following events?
   1. X = 2
   2. X = 7
   3. X > 10
   Solution
   
   
8. Compute the entropy of variable X in Exercise 7.
   Solution
   
   
9. Suppose the variable X has value space {x₁, ..., x_n} and let {p₁, ..., p_n} be the corresponding probabilities. The entropy H[X] is maximized when p_i=1/n (for all i). What is H[X] in this case?
   Solution
   
   
10. Consider the experiment of throwing two dice. Let X be the stochastic variable which gives 1 if the sum of the two dice is 6, and 0 otherwise. And let Y be the value of the first die. Compute
    1. H[Y]
    2. H[X|Y]
    3. H[X,Y]
    Solution
    
    
11. Consider the experiment of randomly choosing a pair of two adjacent letters from a text. Let X₁ be the stochastic variable which tells us whether the first letter is a vowel or a consonant, and let X₂ be the stochastic variable which gives the same information for the second letters. Suppose we know the following probabilities:
    
    

    P(X₁=vowel) = P(X₂=vowel) = 0.4

    P(X₂=vowel|X₁=vowel) = 0.01

    
    Compute
    1. H[X₁]
    2. H[X₂]
    3. H[X₁,X₂]
    4. H[X₁|X₂]
    5. H[X₂|X₁]
    Solution
    
    
12. The variables in Exercise 11 are obviously not independent. Show this in at least three different ways.
    Solution