Katkat
Back

Solve Dice Probability and Matrix Questions

Hudson River TradingData Scientist · Technical Screen
MediumData ScientistTechnical ScreenMachine Learning

Last updated

This problem tests probability distributions over modular arithmetic and the identification of properties of doubly stochastic matrices.

Part 1: Modular Dice Sums

Suppose you roll two fair 6-sided dice, D1 and D2, independently. Let S = D1 + D2 be the sum of the outcomes. Calculate the probability that S is congruent to 0 modulo 3. Provide the probability distribution of S mod 3.

Part 2: Doubly Stochastic Matrices

A square matrix M is called 'doubly stochastic' if all entries are non-negative and every row and every column sums to 1.

  1. Prove that if M is a doubly stochastic matrix, then 1 is an eigenvalue of M.
  2. Consider a 2x2 matrix M = [[a, b], [c, d]]. If M is doubly stochastic, express the determinant of M in terms of 'a'. Show that for any 2x2 doubly stochastic matrix, the determinant must be in the range [-1, 1].

Examples

  • For Part 1, if we rolled one 6-sided die, the distribution of (D1 mod 3) would be: P(0)=2/6 (for outcomes 3, 6), P(1)=2/6 (for 1, 4), P(2)=2/6 (for 2, 5).
  • For Part 2, a matrix like [[0.5, 0.5], [0.5, 0.5]] has a determinant of 0 and is doubly stochastic.

Hints

Hint 1

For Part 1, calculate the total number of outcomes (36) and count how many pairs (D1, D2) satisfy (D1 + D2) % 3 == 0.

Hint 2

For Part 2.1, consider multiplying M by a column vector of all ones and observe the result.

Hint 3

For Part 2.2, use the fact that rows must sum to 1 to write 'b', 'c', and 'd' solely in terms of 'a'.

Follow-up questions

  • How does the distribution of S mod 3 change if the dice are weighted?
  • What can you say about the eigenvalues of a doubly stochastic matrix if all its entries are strictly positive?
  • If we raise a doubly stochastic matrix to a large power, what does the matrix converge to?