161-A3.2

From Microlab Classes
Jump to navigation Jump to search

The submission bin for this exercise can be found here.

The items below are arranged from easiest to hardest. When writing proofs, take care not to rely on figures and work with the available definitions and properties to produce a logical sequence of statements. To get full credit, justify all steps concisely. Note that although it is possible to write correct, lengthy proofs, the exercises below are guaranteed to have concise solutions so that they all fit in one A4-sized sheet of paper.

I strongly encourage everyone to make partial submissions per item, preferably starting from Item 1, so that you can confirm if you are on the right track, or if there are significant faults/fallacies in your work.

Exercises (10 points)

  1. (3 points) Let be independent and uniformly distributed random variables over the common alphabet , and define a third random variable as , where is the XOR operation. Show that the three random variables are pairwise independent, but not mutually independent.
  2. (3 points) Show that if is not a deterministic random variable, then is strictly positive. Hint: What can we say about the probabilities if a random variable is non-deterministic?
  3. (2 points) Show that if , then . Hint: Use Bayes' theorem.
  4. (2 points) For , show that if forms a Markov chain, then also forms a Markov chain.