Does Knowing One Tell You the Other?

Intuition is a poor judge of independence. Draw two cards from a shuffled deck: is "the first card is an ace" independent of "the second card is a heart"? Most people guess wrong.

outcomes is a list of equally likely outcomes, and a and b are functions that take an outcome and return True when the event happens. Write independence(outcomes, a, b) that returns a tuple (p_a, p_a_given_b, independent):

• p_a is P(A) as a tuple (numerator, denominator) in lowest terms;
• p_a_given_b is P(A | B) in the same form, or None when B never happens;
• independent is True exactly when P(A and B) = P(A) · P(B).

The setup provides three lists of outcomes to try: two_cards() (every ordered pair of two different cards from a 52-card deck; a card is a tuple (rank, suit) with rank 1 for an ace up to 13 for a king, and suit one of "clubs", "diamonds", "hearts", "spades"), two_dice() (every pair of values of two six-sided dice) and coin_flips(n) (every string of n letters "H" and "T").

Examples

Input:  outcomes = two_dice(), a = lambda r: r[0] + r[1] == 7, b = lambda r: r[0] == 3
Output: ((1, 6), (1, 6), True)
Explanation: 6 of the 36 rolls add to 7. Among the 6 rolls with a 3 first, exactly one
adds to 7. Knowing the first die changes nothing.

Input:  outcomes = two_dice(), a = lambda r: r[0] + r[1] == 7, b = lambda r: r[0] == r[1]
Output: ((1, 6), (0, 1), False)
Explanation: a double can never add to 7.

Constraints

• 1 <= len(outcomes) <= 3000
• a and b are pure functions (no randomness)

Goals

• Compute P(A) and P(A | B) exactly by counting equally likely outcomes
• Check independence with the multiplication rule P(A and B) = P(A) · P(B)
• Find out by counting, not by intuition, whether two events are independent