Probability Problems 04

Last updated on Aug 14, 2023 Interview

Table of Contents

Consecutive two heads after kth

Suppose you repeatedly toss a fair coin until you get two heads in a row. What is the probability that you stop on the $10^{\text {th }}$ toss?

Remember a similar question that asks no consecutive two heads in 10 coin tosses, where we ended up with a Fibonnaci Sequence. Suppose we denote $F(n)$ be the number of valid coin tosses sequences of length $n$, $F(1)=2$, $F(2)=3$, and every valid sequence can be obtained by either adding `T` or `HT` in the originla sequence. So we have a relationship that $F(n)=F(n-1)+F(n-2)$.

Here, we want the probability that the sequence exactly ends at 10th tosses. So this equally means that the coin tosses have to be ended by $THH$. What about the previous 7 tosses? They are just $F(7)$, any possible sequences that doesn’t have $HH$.

$F(7)=34$. So the probability is $34/2^{10}=17/512$.

Waiting for a larger number

In what follows all number are uniformly distributed on $[0,1]$. Start with a number $S_{0}$ and then keep on generating the sequence $S_{1}, S_{2}, \ldots$ until, for some $N, S_{N}>S_{0}$ for the first time. What is the expected value $E(N)$ of that $N$ ?

There is a very clever solution for this. Due to the symmetry, equally likely that you are waiting for a number that first becomes smaller than $S_{0}$. Suppose $S_0=x$, then a number has $x$ probability to be smaller than it and the probabilty of the first success follows a geometric distribution. We expect $1/x$ steps. Using the law of total probabilty, $E(A)=\int{E(A|x)dx}=\int{\frac{1}{x}dx}$, and $x\in(0,1)$, so this integral doesn't converge. Thats why thie expected value is infinity.

Waiting for all six outcomes

On average, how many times do you need to roll a die before all six different numbers show up?

This is just a simple variable of the coupon collection problems in Green Book.

The first time you roll a die, you are guaranteed to receive a different number.

Then the second time, only probabilty of $5/6$ to get with an expected number of $6/5$.

Overall, you have $6\times(1+\frac{1}{5}+\frac{1}{4}+…++\frac{1}{6})$ expected number of times to get all the outcomes.

Waiting for an Ace

After a thorough shuffle of a card deck of 52 cards, you deal cards from the top of the deck. How long - on average - will you have to wait for an ace?

Again, this is a typical green book problem variation. The four aces separate the cards into 5 piles. Each of the other 48 cards have equal probability to be in any of the piles. So, we expect $48/5$ cards to be in the first pile before we see the first ace.

Waiting for multiple heads

Flipping a coin, a heads comes up with the probability of $p$, $01. What is the expected number of flips before getting three heads for the first time?

2. What is the expected number of flips before getting four heads for the first time?

Think about this as three independent games, why? Because after you get a single head, the games is like brand-new, and you are just waiting for another single head for the first time.

Thus, for a single head, you expect $1/p$ tosses due to the geometric distribution. So for $m$ tosses, you expect $m/p$ number of tosses.

No consecutive n heads

You already know the how to solve the probabilty of no consecutive two heads in 10 coin tosses (a Fibonacci sequence)? How about no consecutive three heads, or $n$ heads in general?

def possiblesequence(n: int, k:int):
    res = list()
    def backtrack(idx, comb):
        if len(comb) == n:
            res.append("".join(comb))
        if len(comb) > n:
            return
        backtrack(idx + 1, comb + ["H"])
        backtrack(idx + 1, comb + ["T"])
        
    backtrack(0, [])
    
    count = 0
    for seq in res:
        if "H"*k not in seq:
            count += 1
    print("Toss a coin {0} times:".format(n))
    print("No Consequtive {0} heads : {1}".format(k, count))
    print("Total Possibilities: {0}".format(2**n))
    # return count

Uniform Sum Smaller than t

What is the probability that sum of $n$ i.i.d uniforms sum is smaller to $t$?

Prove by induction the more general result: If $0 \leq t \leq 1$, then $$ P\left(S_n \leq t\right)=\frac{t^n}{n !}, $$ where $S_n$ denotes the sum $X_1+\cdots+X_n$. The base case $n=1$ is clear. If holds for $n$, then calculate for $0 \leq t \leq 1$ : $$ P\left(S_{n+1} \leq t\right)=\int_0^1 P\left(S_n+x \leq t\right) f(x) d x \stackrel{(1)}{=} \int_0^t \frac{(t-x)^n}{n !} d x=\frac{t^{n+1}}{(n+1) !} $$

Uniforms Sum Greater than 1

Choose a random number between 0 and 1 and record its value. Do this again and add the second number to the first number. Keep doing this until the sum of the numbers exceeds 1 . What's the expected value of the number of random numbers needed to accomplish this?

Reference: https://math.stackexchange.com/questions/111314/choose-a-random-number-between-0-and-1-and-record-its-value-keep-doing-it-u

Draw numbers until get 0

$N$ is a positive number. I randomly pick a number, $K$, from $[0, N-1]$. If $K=0$, the process ends, otherwise we keep picking a number from $[0, K-1]$ until we pick 0. What is the expected number of picks to end the game?

The answer is $1+\frac{1}{2}+\frac{1}{3}+\dots+\frac{1}{N}$. Can be proved using recursion.

Variance of the first n natural numbers

The mean is simple, which is$\frac{n+1}{2}$. While the variance you need to mean for squared sum.

$$ \begin{gathered} \operatorname{Var}(Y)=\frac{1}{n} \cdot\left(\sum_{i=1}^n i^2\right)-\left(\frac{1}{n} \cdot\left(\sum_{i=1}^n i\right)\right)^2 \\ \operatorname{Var}(Y)=\frac{1}{n} \cdot \frac{n \cdot(n+1) \cdot(2 n+1)}{6}-\frac{(n+1)^2}{4} \end{gathered} $$

Which you can then simplified as $\frac{n^2-1}{12}$.

Seen both marbles at least once

You have a bag with five different colored marbles in it; red, green, blue, orange, and purple. Each marble has an equal chance of being drawn from the bag and a marble is replaced after each draw.
After four draws from the bag what is the probability that you have seen both the red and green marbles at least once?

def f():
    res = list()
    def backtrack(idx, comb):
        if idx == 4:
            res.append(comb)
            return
        else:
            for i in range(1, 6):
                backtrack(idx + 1, comb + str(i))
    backtrack(0, "")
    return res
    
a = f()
count = 0
for s in a:
    if list(s).count('1') >= 1 and list(s).count('2') >= 1:
        count += 1
print(count)
print(count / 5**4)

Total outcomes is $5^4=625$. Consider outcomes that have no green, or no red marbles, which is $2\times4^4=512$ outcomes. But these two cases have overlap outcomes when neither of the colors are included (that is when the four draws are all from the other three colors), thus we need to add back $3^4$ outcomes.

Overall, we have $5^4-2\times4^4+3^4=194$ outcomes meet our criteria.

Combination of coins

Suppose that you have five coins in your pocket. These coins are either nickels, dimes, quarters, or dollar coins.
How many different combinations of these coins (not their values) can you make?

This is a classical problem of "indistinguishable" items into "distinguishable" boxes. Say we have $n$ such items, and $r$ boxes. Consider these items are in a line, and we are using $r-1$ delimitators to separate them into $r$ groups, and each group will belong to one box. Thus, this is to choose $r-1$ delimitators in a total of $n+r-1$ positions. So the answer should be $n+r-1$ choose $r-1$.

In this case, we have $5+4-1=8$ choose $4-1=3$, which is $56$.

Number of Paths I

You are at the top left corner of a $4\times 3$ square grids. You can only go down or right. How many paths can you choose to get the bottom right corner?

Not matter the sequence of steps, you need $7$ steps in total. And of these steps, you need $3$ steps down and $4$ steps to the right. This is just a combination problem where you can choose $3/4$ from $7$ spots. Thus the answer is $7$ choose $3$.

Number of Paths II

Imagine an $n \times n$ grid, we start on one corner of the grid in square $A$, and need to reach the opposite corner to square $B$. The rules are, you can only move to an adjacent square, you can't move diagonally and you must pass every square exactly once. How many possible routes are there in an $n \times n$ grid?

There is no closed form formula for this, see answers here.

But there are two things to notice:

when $n=3$, the answer is $2$.
When $n$ is even, then the answer is $0$. Why? Think about the black and white checkboard argument where adjunct squares always have different colors. The colors on opposite corners are the same. But to pass every square only once, you have to take $n^2-1$ steps, which is odd. So you must end up with an opposite color. That’s why you can never reach the opposite corner.

Number Sequence

$3,2,6,6,12,12,?$

Take a rest, I know this is a boring problem. If you notice the first few prime numbers are $2,3,5,7,11,13$, and add $+1$ for odd terms and $-1$ to the even terms then you get the answer. The next should be $18$.

Probability