2
$\begingroup$

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!

$\endgroup$
7
  • 1
    $\begingroup$ Are you trying to calculate ordered triplets or unordered triplets? $\endgroup$
    – Cathedral
    Jul 26 at 3:26
  • 1
    $\begingroup$ @ Cathedral: Thank you for your reply! I think I am interested in "unordered triplets" - i.e. (6, 74, 23) is the same as (74, 23,6). Thank you so much! $\endgroup$
    – stats_noob
    Jul 26 at 3:27
  • 5
    $\begingroup$ I think you should reword your question. As written, it sounds like "make three independent uniform draws from the first 100 integers" which is different from "draw uniformly from all unordered triples (multisets of size 3) of positive integers $\le 100$." If it is the latter you want, you also have miscalculated the denominator despite linking to the correct discussion. $\endgroup$
    – angryavian
    Jul 26 at 3:34
  • $\begingroup$ do any of you have any ideas if this question can be solved? thank you so much! $\endgroup$
    – stats_noob
    Jul 27 at 4:33
  • $\begingroup$ @stats_noob I have a way to calculate the probability that 3 random numbers sum to 50, but not using Markov Chains. I could answer if you are interested. $\endgroup$
    – Cathedral
    Jul 27 at 4:45

1 Answer 1

2
$\begingroup$

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$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.