Representing the probability as a recurrence equation

68 Views Asked by At

Introduction

Suppose that you initially have an $n$-sided die with equal probability and you throw it then you will get a certain number $1< k \leq n$ then you throw a $k$-sided die. Continue this process until you get $k=1$ then you halt. Let $T(n)$ represents the number of times we throw the die that is $n$-sided.

Question

Evaluate $T(n)$ and with what probability does it occur ?

Example

Suppose that you throw a $6$-sided die then you got a $5$ then you take a $5$-sided die and throw it. Suppose that you got $1$ then you halt.

Attempt

I thought that we can represent $T(n)$ as a recurrence relation

$$T(n) = T(k)+1$$

but that doesn't seem to help that much. Then I thought about finding the probablity as

$$Pr(T(n)) = Pr(T(n-1))+\frac{1}{n}$$

becuase it is equal probable to get $n$-sided die or otherwise then we calculate the problablity of that.

I am not sure how to proceed ! and whether it is correct or no!

1

There are 1 best solutions below

0
On

Since this seems to be a homework assignment, I'll only give you a start. I think the problem is indeed the notation. Let' change it.

Let $p_n(T)$ be the probability to throw different dies $T$ times before hitting 1, when starting from an $n$-sided die.

For the first throw which uses the $n$-sided die, each value $k = 1 \ldots n$ is equally probable, $\frac1n$. If the value is $k = 1$, the sequence ends and $T = 1$. Therefore $$ p_n(1) = \frac1n. $$

If $k > 1$, then our sequence has a minimum length of 1, and for the next throw we are in the same situation as before, but with a $k$-sided die. The probability for a sequence of length $T$ is the sum over all possibilities of the probabilities for a sequence of length $T-1$ with a $k$-sided die: $$ p_n(T) = \sum_{k=2}^n \frac1n ~ p_k(T - 1) \quad \text{for } T > 1. $$

Does this help?