Home | Blog | Wiki | About

Probability

Jane Stree Real numbers: P1

Puzzle:

• You are dogsitting for 5 nights.
• Dog will wake you up each night with probability 2/3
• What's the probablity of you being able to sleep for at least 2 full nights without being woken up by the dog?

Solution

• Each night prob of waking up is 2/3
• Each night is an independent event
• 5 nights

P(>=2) = 1 - [P(==0) + P(==1)]

P(==0) means you didn't get even a single night's full sleep. ie, dog woke you up on 5 days.

P(==1) means you were able to sleep well on one day, but the dog woke you up on the other 4 days.

P(==0) = 5C5 * (2/3)⁵

Number of sleepless nights = 5 days
5 days can be chosen in 5C5 ways

--

P(==1) = 5C4 * (2/3)⁴ * (1/3)

Number of sleepless nights = 4 days
5 days can be chosen in 5C4 ways

Therefore,

P(>=2) = 1 - [P(==0) + P(==1)]
       = 1 - [(2/3)⁵ + 5*(1/3)*(2/3)⁴]
       = 0.54

Info

Generally,

• P(A ∩ B) = P(A) + P(B) - P(A ∪ B)
• P(A ∪ B) = P(A) + P(B) - P(A ∩ B)

Independent events:

• P(A ∩ B) = P(A) * P(B)
• P(A ∪ B) = P(A) + P(B)

Dependent events:

• P(A ∩ B) = P(A)*P(B/A)
• P(A ∪ B) = P(A) + P(B) - P(A ∩ B)

Independent events and disjoint events are not same

• Disjoint events: Events that cannot happen together
  • Eg: A single die showing 1 and 2 at the same time
  • Eg: A coin being head and tail at once
• Independent events: Events occurring independent of each other
  • When 2 coins are flipped together, result of each coin is independent of the other.
  • In a chess game, each move is dependent on the previous moves.

If two events are disjoint, they are dependent unless one of the event is of zero probability.

---

A coin fip and a die roll simultaneously:

• Coin flip and die roll are independent events
• Result of coin flip has no effect on result of die roll

Example:

  P(coin=H ∧ die=1)  
= P(coin=H)* P(die=1)
=    1/2   *  1/6
=    1/12

---

  P(die=3 ∨ die=5)  
= P(die=3)+ (die=5)  
= 1/6     + 1/6
= 1/3

—

Probability of event union for non-disjoint events:

P(A ∪ B) = P(A) + P(B) - P(A ∩ B)

P(coin=H) and P(die=1) in our example are not disjoint events.

∵ Coin can be head while die shows 1.

  P(coin=H ∨ die=1)  
= P(coin=H) + P(die=1) - P(coin=H ∧ die=1)
= P(coin=H) + P(die=1) - [P(coin=H) * P(die=1)]
=    (1/2)  + (1/6)    -  (1/2)*(1/6)
=        (4/6)         -  (1/12)
=    7/12

Could also be done like: 

  P(coin=H ∨ die=1)  
= 1 - P(¬(coin=H ∨ die=1))
= 1 - P(¬(coin=H) ∧ ¬(die=1))
= 1 - [P(¬(coin=H)) * P(¬(die=1))]
= 1 - [1 - P(coin=H)] * [1 - P(die=1)]
= 1 - [1 - (1/2)] * [1 - (1/6)]
= 1 - [1/2] * [5/6]
= 1 - [5/12]
= 7/12

---

P(A ∧ ¬A) = 0

Dependent events.

  P(A ∩ ¬A)
= P(A) * P(¬A/A) 
= P(A) * 0
= 0

—

P(A ∨ ¬A) = 1

Dependent events.

  P(A ∪ ¬A)
= P(A) + P(¬A) - P(A ∩ ¬A)  
= x + (1-x) - 0
= 1

HMMT 2023: Q1

Puzzle:

Four people are playing rock-paper-scissors. They each play one of the three options (rock, paper, or scissors) independently at random, with equal probability of each choice. Compute the probability that someone beats everyone else.

---

Solution:

    Scissor

  ∧       ∨ 

Stone  <  Paper

Observe that:

• Move doesn't matter.
• A particular move can be beaten by only a specific move

—

• Let player 1 choose a particular move => 1/3

• The other 3 players have to choose the same move and there is only one such move => (1/3)³

• There are 4 players and player-1 can start with one of 3 possible moves

P = 4*3 * (1/3 * (1/3)³)
  = 12/81 = 4/27

—

Related:

• https://old.reddit.com/r/learnmath/comments/199d063/question_when_you_play_rockpaperscissors_with_3/
• https://math.stackexchange.com/questions/3998809/probability-that-you-win-in-rock-scissors-paper-with-3-players
• https://math.stackexchange.com/questions/3144669/probability-of-one-person-winning-in-a-four-way-game-of-rock-paper-scissors

Jane Stree Real numbers: P2

Puzzle

• 6 cars parked in a row
• Prob that a car is taxi (independently) is 1/2
• What is the prob that there are 3 consecutive taxis among the 6 cars?

Solution

4.1 of Green book: Coin toss game

Puzzle:

• A has n+1 coins
• B has n coins
• All coins are fair
• When all coins are tossed, whats the probability that A has more heads than B?

Solution:

Combinatronics

Number of trailing zeros in n!

General forumla:

 ∞   │ n │
 Σ   │───│
i=1  │ 5ⁱ│
     └   ┘

—

Example: 100!

  100/5 + 100/5² + 100/5³ + ....
= 20 + 4
= 24

So, there are 24 trailing zeros in 100!

—

An easier way: Keep dividing recursively to get the numbers and sum up.

100/5 = 20
 20/5 = 4
  4/5 = 0
      ─────
        24

ie, f(n) = n/5 + f(n/5)

—

Consider 25!.

25/4 is 5

• ∵ 5, 10, 15, 20, 25
• But not that 25 has actually two 5
• 5, 10, 15, 20, 5*5
• So need to consider all powers of 5

Likewise 4 consists of two 2s too. But we needn't care in this case, because number of 5s will always be lesser than that of 2s.

See:

• https://math.stackexchange.com/questions/1806642/find-the-number-of-trailing-zeros-in-n
• https://math.stackexchange.com/questions/286947/number-of-zero-digits-in-factorials
• https://math.stackexchange.com/questions/975539/how-do-you-find-the-number-of-multiples-of-a-given-range-of-numbers

Minimum cut

See:

• https://www.geeksforgeeks.org/puzzle-31-minimum-cut-puzzle/

Facts

• Number of leaves in a complete binary tree of height H: 2^H