6

I am struggling a bit with this problem, I think I am somehow close but I miss something.

Let's assume we have numbers from $1$ to $30$, we pick $5$ random numbers (with repetition) and we want to know the probability to pick at least $3$ numbers in sequence.

Denominator: The total number of combinations without repetition should be $$30!/(5!*(30-5)!)$$

and with repetition: ( 5 5 6 7 8 ) is a valid sequence, this is what i am actually interested in

$$(30+5-1)!/(5!*(30-1)!)$$

Numerator: I should get the ways to pick $5$ numbers where at least $3$ are in a sequence. There are $28$ ways to pick $3$ numbers in a row, if we just would pick $3$, but with $5$ I am having the problem.

My approach is $28$ $+$ the way to pick the other $2$ numbers, that is $C(30+2-1,2)$

The flaw here I think is that I think I am counting twice some combinations.

How can I get the number of combination of picking $3$ consecutive numbers with $5$ picks?

Edit: To clarify repetition is allowed, so $5\; 5\; 6\; 7\; 8$ is a valid pick. Order is not important, so $5$ $5$ $6$ $7$ $8$ is the same as $6$ $7$ $8$ $5$ $5$.

Ultrakorne
  • 163
  • You are correct that you are counting some combinations twice... I don't have the correct answer yet, though. – 5xum Mar 03 '16 at 11:12
  • Just to be clear (since I'm unfamiliar with your notation), do we pick numbers with or without replacement. Is, ie, $5,5,6,7,8$ an allowed picked sequence? – Marc Mar 03 '16 at 11:36
  • yes 5 5 6 7 8 is an allowed picked sequence. but the order is not important, so 5 5 6 7 8 is equivalent to 6 7 8 5 5 (that's why i m not using 30^5 as the total space but the combination with repetition formula) – Ultrakorne Mar 03 '16 at 12:31
  • When you say "random", what do you mean? Is there a reason why each of your combinations-with-repetition should be equally likely? Notice that you can pick two numbers from 1 to 6 with repetition by rolling two dice and listing the outcome in increasing order. So (1,1) is one result, (1,2) is another result. But (1,2) is twice as likely to occur as (1,1). Or to put it another way, there are 21 combinations that can occur, but not one of them has probability 1/21. – David K Mar 03 '16 at 15:11
  • by random with repetition i just mean that the 5 number picked from 1 to 30 are picked at random (so each one of them has 1/30) and i can pick twice the same number. but when looking if the numbers are in a sequence of 3, i dont care about the order, so 1 10 2 23 3 are a valid sequence (1, 2 , 3) – Ultrakorne Mar 03 '16 at 15:49

3 Answers3

1

This answer looks at the situation where we draw with replacement and with order.

We draw $(x_1,\ldots,x_5)\in\{1,\ldots,30\}^5$ and are interested in $$ N = \#\left\{(x_1,\ldots,x_5)\in\{1,\ldots,30\}^5 \mid \exists i\in\{1,2,3\}\quad\text{st}\quad x_{i+2}=x_{i+1}+1 = x_{i} + 2\right\} $$ As you said we have 28 ways to pick 3 consecutive numbers from $\{1,\ldots,30\}$. Given that we have 3 consecutive numbers at a specific place we are free to choose the other two numbers as we please. So for each $i\in\{1,2,3\}$ we have $28\cdot30^2$ possible combinations that have 3 consecutive numbers on $x_i,x_{i+1},x_{i+2}$.

Now note that the total amount of combinations is less than $3\cdot28\cdot30^2$. For example $(1,2,3,4,30)$ is counted twice, since it has three consecutive numbers for $i=1$ and $i=2$. In general: we count all sequences that contain 4 consective numbers twice and all sequences that contain 5 consecutive numbers thrice. We conclude $$ N = 3\cdot28\cdot30^2 - \#\{\text{4 consecutive}\} - 2\#\{\text{5 consecutive}\} $$ By similar calculations we get \begin{align} \#\{\text{4 consecutive}\} &= 2\cdot27\cdot30 - \#\{\text{5 consecutive}\} \\ \#\{\text{5 consecutive}\} &= 26 \end{align} Therefore we get that $$ N = 3\cdot28\cdot30^2 - 2\cdot27\cdot30 + 26. $$

Marc
  • 6,861
  • interesting, i get now how to get rid of the duplicate count but i have a question, in the line N = 3 * 28 * 30^2 ... where does the 3 * comes from? I also added a clarification at the end of my question, does this change the 30^2 since the other 2 number, chosen as we please, let's say the first is 5 the second is 6, would be equivalent to have first 6 and second 5 – Ultrakorne Mar 03 '16 at 12:46
  • My answer looks at sequences that do take order into account. I will try to extend it to one where we don't care about order. – Marc Mar 03 '16 at 12:56
  • i edited with the formula to use instead of 30^5 for example, let me know if you think is correct. My last thing after this to understand i why you multiply by 3 in N=3⋅28⋅30^2 – Ultrakorne Mar 03 '16 at 12:58
  • 1
    The 3 appears, because my answer takes order into account. That means that it matters where the three consecutive numbers are placed. In a sequence of 5 numbers there are 3 ways to select 3 consecutive numbers. – Marc Mar 03 '16 at 13:06
1

This is combination with repetition, so total number of possibilities is $$ \frac{(N + r - 1)!}{r!(N-1)!} = \frac{(34)!}{5!(29)!} = 278256$$

There are 28 sequences of 3 in 30, so to pick 3 consecutive out of 5, I have 3 numbers in the sequence, plus 2 that needs to be picked out of 29 (so as to not pick the next one in the sequence) with repetition where order is not important (combination with repetition) i.e. $$ 28 * \frac{(30)!}{2!(28)!} = 28 * 435 = 12180 $$

Similarly, the number of ways of picking a sequence of 4 numbers is then $$ 27 * \frac{(29)!}{1!(28)!} = 27 * 29 = 812 $$

And finally, the number of ways of picking a sequence of 5 numbers is $$ 26 * \frac{(28)!}{0!(28)!} = 26 * 1 = 26 $$

The sets containing sequences of 3,4 and 5 consecutive numbers do not overlap, they are all different numbers, so the probability of selecting a number with at least a sequence of 3 consecutive numbers out of 5 from a set of 30 with repetition where order is not important is then $$ \frac{ 12180 + 812 + 26}{ 278256} = 0.0468 $$

strider
  • 371
  • 30^5 would count the order of the picks, 5 5 6 7 8 is equal to 6 7 8 5 5. should we use the combination with repetition instead? – Ultrakorne Mar 03 '16 at 12:35
  • I have updated my post. Multiplying by the factorial in the numerator should take care of that. – strider Mar 03 '16 at 13:22
  • I get you now Ultrkorne :), I updated my answer to remove the order from the numerator and denominator by using the combination with repetition formula – strider Mar 03 '16 at 16:35
  • cool! seems good, just a couple of questions. is it at the end a sum? should not be -812 and -26 since we are removing duplicates that were counted with combination of 3? – Ultrakorne Mar 03 '16 at 16:53
  • 1
    the sum is for p(selecting 3) + p(selecting 4) + p(selecting 5), because you want the probability of "at least" selecting 3. the ordering has already been removed. – strider Mar 03 '16 at 17:01
  • i will need some time to analyze it to fully understand, but when you say "I have 3 numbers in the sequence, plus 2 that needs to be picked out of 29 with order not important" when you pick the combination of those 2, you are actually including already combination with 4 and 5 numbers in sequence, that's why it feel strange the addition – Ultrakorne Mar 03 '16 at 17:24
  • lets say I take (1,2,3) as the first 3 numbers. the last 2 numbers are picked out of 29 so I don't pick 4, otherwise this becomes a sequence of 4 (or even maybe 5) consecutive numbers. Also, the last 2 numbers are picked out of 29 with repetition allowed but where order is not important, so I don't have duplicates in them either. so the probability of picking exactly 3 out of 5 is 12180 / 278625. – strider Mar 03 '16 at 18:18
  • the sequence of numbers with 3/5 and 4/5 and 5/5 will all be different numbers and have to be summed to get total probability – strider Mar 03 '16 at 18:29
0

Let $E_{i,k}$ denote the event that the consecutive numbers $i,\dots,i+k-1$ are picked.

Then you are interested in $P\left(\bigcup_{i=1}^{28}E_{i,3}\right)$ and applying inclusion/exclusion we find:

$$P\left(\bigcup_{i=1}^{28}E_{i,3}\right)=\sum_{1\leq i\leq28}P\left(E_{i,3}\right)-\sum_{1\leq i<j\leq28}P\left(E_{i,3}\cap E_{j,3}\right)+\sum_{1\leq i<j<k\leq28}P\left(E_{i,3}\cap E_{j,3}\cap E_{k,3}\right)$$

For the terms here that do not equal $0$ we find:

$P\left(E_{i,3}\right)=P\left(E_{1,3}\right)$ for $i=1,\dots,28$

$P\left(E_{i,3}\cap E_{i+1,3}\right)=P\left(E_{1,4}\right)$ for $i=1,\dots,27$

$P\left(E_{i,3}\cap E_{i+2,3}\right)=P\left(E_{i,3}\cap E_{i+1,3}\cap E_{i+2,3}\right)=P\left(E_{1,5}\right)$ for $i=1,\dots,26$

So it's enough to calculate $P\left(E_{1,k}\right)$ for $k=3,4,5$ and to do some counting.

drhab
  • 151,093