Suppose I want to randomly select 3 integers between 1 and 100 with replacement – for example (34, 93, 3) or (2,89,2). I want to know the probability that these 3 numbers will sum to some specified number, e.g. 50.
Since the probability of obtaining any combination of 3 numbers is equal – I know that this problem takes the general form of : Probability = number of valid ways / number of total ways.
From this post (Number of ways of choosing $m$ objects with replacement from $n$ objects), I know that the number of total ways that 3 numbers with replacement (out of 100) can be picked is : 100!/((3!) * (97!)) = 161700 ways
However, I am not sure how to calculate the total number of "valid" ways in which 3 random integers between 1-100 can sum to 50.
Had this been a simpler problem, e.g. 3 random integers (with replacement) between 1 and 10 must sum to 7 – I could have manually enumerated all "valid" ways.
But in this problem, is there some standard formula that can be used to calculate the number of "valid" ways that 3 random integers between 1 and 100 can sum to 50?
The first thought I had was to attempt to calculate this number using Markov Chains. Additionally, a Markov Chain would also allow me to find out the average number of times I would need to keep picking 3 random numbers until they summed to 100 ("mean time to absorption") – but this Markov Chain would have so many states, I would have no idea how to write the transition matrix for such a Markov Chain.
Can someone please show me how to calculate these numbers (i.e. the probability that 3 random numbers with replacement sum to 50, and the number of times 3 random numbers need to be selected with replacement until the first triplet sums to 50) – preferably using Markov Chains?
Thanks!
Best Answer
We can first find the number of ways of choosing $x,y,z \in \mathbb Z^+$ such that $x+y+z=50$. We evaluate this using the star-bar approach to get
$$\text{No. of ways}= {50-1\choose 3-1}={49\choose2}=1176$$
These are ordered triplets, and we can now convert them to unordered triplets.
Of these $1176$ ways, we have $24\cdot \frac {3!}{2!}=72$ in which 2 of $x,y,z$ are the same (the $24$ comes from the fact that repetition is only possible for integers between $1$ and $24$, if we go any higher we will exceed $50$ as our sum). We cannot have all 3 being the same because $50$ is not divisible by $3$.
Thus, we now have $1176-72=1104$ ordered triplets in which all 3 of $x,y,z$ are different. We simply divide by $3!$ to get $184$ unordered triplets where all 3 of $x,y,z$ are different. In total we now have $184+24=208$ unordered triplets.
The number of ways of choosing 3 unordered integers from between $1$ and $100$ with replacement is $${100+3-1\choose3}={102\choose3}=171700$$
The required probability is now
$$P(\text{sum}=50)=\frac {208}{171700}\approx0.00121$$