1

Consider a grid of $n$ rows and $m$ columns (in the figures that I attach, is $n = 3$ and $m = 5$, but it might be arbitrary). The grid is populated with integer numbers in the range of [1...90].

How to calculate the probability that one particular configuration will be achieved with $k$ draws?

For example, one possible configuration may be a single line:

Single line

or a double line:

Double line

How to calculate, for example, that a double line is filled with, let's say, 34 draws?

EDIT I think the problem might be reformulated in the following way:

Consider a set $A$ of $n$ numbers. Consider now another set $B$ of $m$ numbers, with $A ⊂ B$ (and consequently $n < m$).

How to calculate the probability that exactly $j$ numbers of the set $A$ will be picked up from the set $B$, with $k$ draws (without replacement)?

Luca Fagioli
  • 97

1 Answers1

2

Revised per OPs comments and revisions

If you are trying to get j of N numbers from an overall population of M>N numbers in k draws, then this is just the hypergeometric distribution where the number of successes in the population is equal to n, the total population is m, and you want to get j of the successes in k draws without replacement. Using your notation, the exact formula would be:

P(get exactly j of n $<$ m numbers|m total numbers and k draws without replacement) = $\frac{{n\choose j}{m-n \choose k-j}}{m\choose k}$

This is the probability that you would get exactly j items from your subset A in k draws.

  • The formula you provide is going to calculate the probability of getting a certain set of squares with 90 attempt, right? What if I want to determine the probability with a different number of attempt (ie 35 attempts)? – Luca Fagioli Feb 10 '14 at 17:31
  • Sorry @Eupraxis, my question was not clear. I mean, how do I calculate the probability of getting a certain set of squares within a single game, with let's say 35 extracted numbers? – Luca Fagioli Feb 10 '14 at 17:39
  • In your second equation, $p_n$ is the $P(S_n)$ in your first equation? – Luca Fagioli Feb 10 '14 at 17:52
  • exactly, probably my question was not clear enough. I will quickly make some test with your new equation and I will back to you! – Luca Fagioli Feb 10 '14 at 18:03
  • Uhm, I am trying with a set of 5 squares with 15 attempts but I get a strange result of 136. Am I doing something wrong? – Luca Fagioli Feb 10 '14 at 18:07
  • Seems nice, I will try it later (I am writing from my mobile) and back to you! – Luca Fagioli Feb 10 '14 at 18:24
  • I have tried it with $n = 5$ and $m = 33$. The equation gives out 0.005400226461109659, which is 0.5%, right? If so, the value is too low...am I doing something wrong? – Luca Fagioli Feb 10 '14 at 23:51
  • @LucaFagioli too low compared to what? What are you doing to test this value? With n=5 and m=33, you are basically trying to get 5 items from 90 by drawing 33 balls sequentially. That won't be that probable. BTW: The value you calculated is correct, so there has to be something amiss about how you are testing it. If you are drawing $m$ numbers out of 90, and trying to get a specific set of $n<m$ numbers in the set of drawn numbers, then your odds follow a hypergeometric distribution. –  Feb 11 '14 at 00:57
  • I think I understand my own doubt now. The equation gives out the probability of a set of $n$ squares with exactly $m$ draws. My test is with at most $m$ draws, so I guess we have to add to that probability also the probability of success with each draw $k$ with $k = [1...m-1]$, right? – Luca Fagioli Feb 11 '14 at 12:26
  • Something like that?

    $$P(S_n,[1...m]) = \sum_{k=1}^{m} \frac {\binom {90-n} {k-n}} {\binom {90} {k}}$$

     – Luca Fagioli Feb 11 '14 at 13:16
  • @LucaFagioli Exactly...except you need to fix the index as its not possible to get n squares in 0 to n-1 draws. The revised formula would be: $P(S_n,[n...m]) = \sum_{k=n}^{m} \frac {\binom {90-n} {k-n}} {\binom {90} {k}}$ Other than that, you are right on! Now the probabilities should match your simulations. –  Feb 11 '14 at 13:49
  • That's true! Great, thank you, thank you @Eupraxis! – Luca Fagioli Feb 11 '14 at 13:59
  • after deeper testing It seems that the formula does not return a value correspondent to reality.

    The formula, given $$k = 5$$ (5 squares) and $$m = 34$$ (34 draws), returns a value of 0.03693258326850859; testing the same situation over a million of times, it turns out that the probability is ~0.064

     – Luca Fagioli Feb 25 '14 at 15:09
  • Edit: Not ~0.064, but ~0.0064 (6,4 out of 1000). – Luca Fagioli Feb 25 '14 at 15:29
  • @LucaFagioli that is indeed strange. How are you simulating the bingo games? If you are choosing 34 items without replacement and hoping to get 5 specific numbers, then the above formula is correct, as I have just described the hypogeometric distribution. –  Feb 25 '14 at 15:36
  • 1
    @LucaFagioli BTW: I calculated the probability of getting 5 numbers in 34 draws (without replacement) from a population of 90 numbers, 5 of which are successes. I got 0.0063, in agreement with your simulation. This is what I put into Excel: =HYPGEOM.DIST(5,34,5,90,FALSE) –  Feb 25 '14 at 15:40
  • That's encouraging! But why the formula gives a different value? – Luca Fagioli Feb 25 '14 at 15:45
  • @LucaFagioli This is also what my formula returns... I think you may want to rerun your calculation. –  Feb 25 '14 at 15:47
  • @LucaFagioli Heres the formula result: m=34, k=5, so: $90-5 \choose 34-5$ = 4.48121E+22, $90 \choose 34$ = 7.07787E+24. Taking the ratio of these we get $\frac{4.48121E+22}{7.07787E+24} \approx 0.0063$ –  Feb 25 '14 at 15:50
  • Yeah, silly me. I was doing something wrong in the calculation. But according to the result, then we have to remove the summatory and just leave the hypogeometric distribution, which is by the way exactly what you stated in your answer. – Luca Fagioli Feb 25 '14 at 15:54
  • @LucaFagioli correct, you dont need the summation for the case you described in the comments, where you want the probability of getting 5 successes in at most 34 draws. What you have calculated is the probabiliy of getting 5 successs in 34 draws, which is actually more relevant to your problem anyway. The summation is for varying game lengths. The results you calculated basically tells you the probability in a single game. Now...the probabilty of winning depends on the the number of players as well, which is a different question entirely. –  Feb 25 '14 at 16:06
  • However, your approach has gone straight to the point. Thank you! – Luca Fagioli Feb 25 '14 at 17:53
  • but how this takes into count the grid size? I mean, if I have a grid of 35 like in the figure, or if I have a grid of 125, the result cannot be the same. How has this been taken into count? – Luca Fagioli Mar 03 '14 at 16:52
  • @LucaFagioli see the 90 in the formulas? this is the total number of squares. If your example, this would be 15, for 12*5, it would be 60. –  Mar 03 '14 at 17:49
  • I don't get it. To clarify, let's put it in the bingo example: if the grid (the bingo card) is 3x5 and the set of items is 90, how the formula would be? – Luca Fagioli Mar 03 '14 at 19:59
  • @LucaFagioli The formula would have n=35=15, since you are trying to get a specific set of 15 numbers out of 90 possible numbers. If you're asking if the overall size of the card matters when tyring to get a specific set of squares, the answer is no...since any square that is not part of your specified sequence is irrelevant and might as well not exist. The onlyl way it would matter is if you weren't trying to get a specific set of squres but just a specific configuration*, such as a row of 5 numbers...then card size matters. –  Mar 03 '14 at 22:20
  • In that case I wasn't clear in my question... I am searching for the probability of specific configuration, out of a set of a $NxM$ grid. How to achieve that? – Luca Fagioli Mar 04 '14 at 14:48
  • @Luca Fagioli then you replace 90 in the formula with NxM to represent the total number of possible squares being chosen among. This conversation is getting rather long so please either accept the answer or revise your post to say what you really mean. –  Mar 04 '14 at 20:53
  • I have revised my question, and added a bounty. – Luca Fagioli Mar 04 '14 at 21:23
  • @Luca Fagioli see revised post. If you have mn possible numbers and you specify a sequence of length n<=mn that you want to get within a certain number if draws then the probability is given by the hypergeometric distribution as I've already stated. All that matters is the number if possible numbers, the length if the sequence and the number if draws –  Mar 04 '14 at 23:48
  • The range of possible numbers is $[1...90]$, not $[1...n*m]$. So the probabilty that the (first) draw will land on a particular square is $1/90$, as you stated in your first (precious) answer, not $1/nm$. The grid is $n m$, but the set of numbers is 90 with $90 > (n * m)$. – Luca Fagioli Mar 05 '14 at 13:22
  • I have reformulated the problem in my question. – Luca Fagioli Mar 05 '14 at 13:46
  • @Luca Fagioli in that case my first answer us correct. Although it would seem that having a bigger card should affect your probability it in fact does not. Once you specify a particular sequence of squares on a given NxM card then the remaining squares become irrelevant. Are you actually trying to get a general configuration such as one row or one column regardless of where it is on the card? That would change the approach –  Mar 05 '14 at 13:55
  • @Luca Fagioli: Thanks for the succinct clarification. The answer to your revised poset is EXACTLT the hypogeometric distribution. See my revised post to handle your more general, revised question. –  Mar 05 '14 at 14:37
  • thanks for the update. I am testing it, but with values o $m = 90$ (the total population), $n = 15$ (the grid size), $j = 5$ (the hits I want) and $k = 34$ (the draws) the result is 33437522.257895496 – Luca Fagioli Mar 05 '14 at 15:22
  • @LucaFagioli my apologies...mistyped the denominator...i've corrected it now. –  Mar 05 '14 at 15:45
  • I think there is some problem yet. By incrementing $n$ (the population of the set A), the probability get lowered, while I think it should get higher. – Luca Fagioli Mar 05 '14 at 15:52
  • @LucaFagioli nope, no problem. If you have more possible successes, then the probability of getting exactly j successes goes down, as it becomes easier to get MORE than j. If you plot the probability as n runs between j and m, you will see that it rises to a maximum then falls. If you want the probability of getting AT LEAST j successes, then yo need to subtract the the probability of getting 0, 1,...j-1 successes from 1 to get the probability. –  Mar 05 '14 at 16:03
  • The bounty is all yours! – Luca Fagioli Mar 05 '14 at 19:44
  • @LucaFagioli glad we were able to get to a satisfactory solution! :) Since I posted before the bounty, you may need to manually award it after its time period expires. –  Mar 05 '14 at 19:46
  • I will do that, but I have to wait one hour, the site says ;) – Luca Fagioli Mar 05 '14 at 19:50
  • I am trying to following this question but would like to modify the question a bit. Now I could find the probability ($P_1$) of winning on one specific configuration based on above discussion. But if I consider more configurations on one card, I would like to find the probability of nothing winning the game. So my guess is, says we have 5 configurations, the winning probability on each conf is $P_1$, then can I say the probability not winning the game is $1-5P_1$? It seems not in agreement with the simulation – user1285419 Aug 20 '14 at 18:58