Probability in binary grid

B

Bmcg61

New member
Joined
Apr 7, 2022
Messages
5
In a 3 x 3 grid of black/white squares, the probability of all squares being black is 1 in 256, I believe. In a 100 x 100 grid of binary squares, what is the probability of any 3 x 3 group of squares being all black?
 
Bmcg61 said:
In a 3 x 3 grid of black/white squares, the probability of all squares being black is 1 in 256, I believe. In a 100 x 100 grid of binary squares, what is the probability of any 3 x 3 group of squares being all black?
Click to expand...
Please show us what you have tried and exactly where you are stuck.

Please follow the rules of posting in this forum, as enunciated at:


Please share your work/thoughts about this problem.
 
In a 3 x 3 grid of black/white squares, the probability of all squares being black is 1 in 256
How do you figure it out? Suppose black means a male child and white means a female child. What is the probability of having 9 male children (if you have exactly 9 children).
Do you see that this is the same? Each square has two outcomes with equal probabilities and each birth has two outcomes with equal probabilities.
 
Steven G said:
In a 3 x 3 grid of black/white squares, the probability of all squares being black is 1 in 256
How do you figure it out? Suppose black means a male child and white means a female child. What is the probability of having 9 male children (if you have exactly 9 children).
Do you see that this is the same? Each square has two outcomes with equal probabilities and each birth has two outcomes with equal probabilities.
Click to expand...
Yes I am logically aware of that. I just don't know how to mathematically answer the second part of the question. That's why I'm posting.
 
There are two chooses for each square--black or white.

If there is just one square then there is a 1 in 2 chance that it is black.
If there are two squares then there are 4 choices: ww, wb, bw and bb. Therefore there is a 1 in 4 chance that both squares are black.
What if there were exactly 3 squares? 4 squares? 5 squares? Do you see a pattern?

I know that you are posting to ultimately get the answer. The thing is that no one here will give you an answer to any question which you post. You will receive helpful hints that will lead you to the answer. Before we get to the 2nd part of the question you need to get part a correct.
 
Bmcg61 said:
In a 3 x 3 grid of black/white squares, the probability of all squares being black is 1 in 256, I believe. In a 100 x 100 grid of binary squares, what is the probability of any 3 x 3 group of squares being all black?
Click to expand...
First, you need to correct your 1/256. Can you tell us how you got that number?

Then you need to clarify the meaning of the second question. Are you asking for the probability that at least one 3x3 square, at any location within the 100x100 grid, is all black? And if there is any context to the problem (an exercise for a course in which you have covered certain topics, or some larger application in which this will be used) that can help us be sure what you need to calculate (and perhaps give us ideas, or just motivate us to try harder).

Finally, you have been shown our guidelines, which request you to show what you have tried -- even if you have no confidence about it. We want to guide you toward a solution, which should use things that you already know.

I will add that I don't yet see a good approach to the problem as I interpret it.
 
Steven G said:
There are two chooses for each square--black or white.

If there is just one square then there is a 1 in 2 chance that it is black.
If there are two squares then there are 4 choices: ww, wb, bw and bb. Therefore there is a 1 in 4 chance that both squares are black.
What if there were exactly 3 squares? 4 squares? 5 squares? Do you see a pattern?

I know that you are posting to ultimately get the answer. The thing is that no one here will give you an answer to any question which you post. You will receive helpful hints that will lead you to the answer. Before we get to the 2nd part of the question you need to get part a correct.
Click to expand...
Yes I see the answer to the first part is 9 squared. For the second part could I use the ratio between total number of squares to 9?

Dr.Peterson said:
First, you need to correct your 1/256. Can you tell us how you got that number?

Then you need to clarify the meaning of the second question. Are you asking for the probability that at least one 3x3 square, at any location within the 100x100 grid, is all black? And if there is any context to the problem (an exercise for a course in which you have covered certain topics, or some larger application in which this will be used) that can help us be sure what you need to calculate (and perhaps give us ideas, or just motivate us to try harder).

Finally, you have been shown our guidelines, which request you to show what you have tried -- even if you have no confidence about it. We want to guide you toward a solution, which should use things that you already know.

I will add that I don't yet see a good approach to the problem as I interpret it.
Click to expand...
To answer your question, yes you understood what I am asking but I am so clueless I didn't know how to approach it.

Steven G said:
In a 3 x 3 grid of black/white squares, the probability of all squares being black is 1 in 256
How do you figure it out? Suppose black means a male child and white means a female child. What is the probability of having 9 male children (if you have exactly 9 children).
Do you see that this is the same? Each square has two outcomes with equal probabilities and each birth has two outcomes with equal probabilities.
Click to expand...
I thought In binary a sting of 9 1's was 256 but it's 511. The probability then is 1 in 512.

Bmcg61 said:
Yes I see the answer to the first part is 9 squared. For the second part could I use the ratio between total number of squares to 9?
Click to expand...
No it's 1 in 512.
 
Bmcg61 said:
To answer your question, yes you understood what I am asking but I am so clueless I didn't know how to approach it.
Click to expand...
Then the other parts of my request are crucial:
Dr.Peterson said:
And if there is any context to the problem (an exercise for a course in which you have covered certain topics, or some larger application in which this will be used) that can help us be sure what you need to calculate (and perhaps give us ideas, or just motivate us to try harder).
Click to expand...
What CAN you understand? And if you don't know any probability, why are you asking for this? Context is all the more important if you claim to know little enough that you might well be asking the wrong question in the first place.
 
Dr.Peterson said:
Then the other parts of my request are crucial:

What CAN you understand? And if you don't know any probability, why are you asking for this? Context is all the more important if you claim to know little enough that you might well be asking the wrong question in the first place.
Click to expand...
I did have a probability and stats course years ago. I am looking for proof of an idea so I'd rather not disclose the idea. If I am correct at this point about the 1 in 256, then on the 100 x 100 scale, is the occurrence of the 3x3 black squares near the same probability?

Ok, I figured out a way to get the answer. The probability of a 3x3 grid of binary cells will all be black is 1 in 512 because the highest number represented by a 9 digit binary number is 511. To find the probability of that black 3x3 grid appearing at any position within a larger grid, for example 9x9 is to reduce the larger grid by 2 in each dimension, for example 7x7 and multiply (49). That is the number of positions the 3x3 grid could appear in. Then take the dimensions of the larger grid and multiply (81) and find the highest number represented by a 81 digit binary number and add 1. ?
 
Bmcg61 said:
Ok, I figured out a way to get the answer. The probability of a 3x3 grid of binary cells will all be black is 1 in 512 because the highest number represented by a 9 digit binary number is 511. To find the probability of that black 3x3 grid appearing at any position within a larger grid, for example 9x9 is to reduce the larger grid by 2 in each dimension, for example 7x7 and multiply (49). That is the number of positions the 3x3 grid could appear in. Then take the dimensions of the larger grid and multiply (81) and find the highest number represented by a 81 digit binary number and add 1. ?
Click to expand...
Your logic is flawed. Consider the 4x4 grid, how many ways you can fit a 3x3 inside?
 
Bmcg61 said:
Ok, I figured out a way to get the answer. The probability of a 3x3 grid of binary cells will all be black is 1 in 512 because the highest number represented by a 9 digit binary number is 511. To find the probability of that black 3x3 grid appearing at any position within a larger grid, for example 9x9 is to reduce the larger grid by 2 in each dimension, for example 7x7 and multiply (49). That is the number of positions the 3x3 grid could appear in. Then take the dimensions of the larger grid and multiply (81) and find the highest number represented by a 81 digit binary number and add 1. ?
Click to expand...
It's a considerably more complicated problem than you seem to realize. I haven't attempted it, because I see what it involves. You can't just treat all the possible places for a 3x3 within the larger grid as independent, because they overlap; and you also would need to take into account that more than one such grid might be all black. I suspect it would take a computer program to solve this, which is why it doesn't interest me. But I could be wrong.
 
Since OP doesn't seem to know a lot about probability and this isn't a coursework question, I'll post these results from a computer program that estimates the probability (using a "Monte Carlo" method).
Code: 
grd sz   approximate prob
  10        0.0932
  20        0.3841
  24        0.5142
  40        0.8822
  60        0.9930
 100        0.9999
 
Bmcg61 said:
4. And I think my logic is correct if unconventional.
Click to expand...
That part of your logic is valid, and fairly standard:
Bmcg61 said:
The probability of a 3x3 grid of binary cells will all be black is 1 in 512 because the highest number represented by a 9 digit binary number is 511. To find the probability of that black 3x3 grid appearing at any position within a larger grid, for example 9x9 is to reduce the larger grid by 2 in each dimension, for example 7x7 and multiply (49). That is the number of positions the 3x3 grid could appear in. Then take the dimensions of the larger grid and multiply (81) and find the highest number represented by a 81 digit binary number and add 1. ?
Click to expand...
What you are doing there is counting the places where the upper left corner (say) of the 3x3 could be. That's correct.

It's the rest that won't work. (You didn't go as far as to calculate a probability, though, so I can't comment on any specifics.)

By the way, rather than talk about binary numbers, a better way to talk about the 1/512 is simply that the probability is 1/2^9; the probability of being black is 1/2 for each of 9 places. For the 9x9 grid (your 81-bit number), the probability of being all black would be 1/2^81 = 1/2,417,851,639,229,258,349,412,352. The hard part of the bigger problem (at least one all-black 3x3 square within the 9x9) is that the various cases interact extensively, rather than being independent.

What you should do to see if your thinking is valid is to calculate, by whatever method, the probability for a small number, say 5x5 or 10x10, and compare to Cubist's estimate (and maybe even to an actual count). If it matches, we can (perhaps) trust it for larger numbers.
Cubist said:
I'll post these results from a computer program that estimates the probability (using a "Monte Carlo" method).
Code: 
grd sz   approximate prob
  10        0.0932
  20        0.3841
  24        0.5142
  40        0.8822
  60        0.9930
 100        0.9999
Click to expand...
Could you do this for numbers less than 10 as well?
 
Dr.Peterson said:
Could you do this for numbers less than 10 as well?
Click to expand...
Of course. I ran the simulation 3 times to give us an idea of how accurate the approximations are. (Every approximation is derived from looking at 100,000,000 randomly generated grids). Obviously the first row ought to be close to 1/512 = 0.001953125

Code: 
grd sz
  3      0.00195482    0.00194870    0.00194628
  4      0.00681897    0.00682789    0.00681497
  5      0.01453846    0.01454713    0.01454525
  6      0.02505871    0.02509244    0.02509684
  7      0.03837807    0.03837315    0.03835422
  8      0.05423647    0.05422556    0.05429420
  9      0.07256465    0.07258471    0.07258415
 10      0.09325770    0.09322808    0.09326883

I can probably write some code to give exact answers for grid sizes 4 and 5 (and maybe 6 but the runtime would probably become very large).
 
For the 4x4 grid the exact answer is 447 / 2^(4*4) = 447 / 65536 ≈ 0.0068206787
Code: 
WAYS TO HAVE ONE 3x3 SUB-GRID
=============================

# # # a
# # # a
# # # a
b b b c

The 3 "a" must contain at least one "white" to avoid adding any more black 3x3 subgrids (2^3 - 1 = 7 ways to do this).
The same with the 3 "b". The 1 "c" can be any value (2 ways). There are 4 rotations
7*7*2*4 = 392 ways


WAYS TO HAVE TWO 3x3 SUB-GRIDS
==============================

# # # #
# # # #
# # # #
c a a c

The 2 "a" must contain at least one "white". There are (2^2 - 1) = 3 ways to do this.
The 2 "c" can be any value (2^2 = 4 ways). There are 4 rotations
3*4*4 = 48 ways

# # # 0
# # # #
# # # #
0 # # #

There are 2 rotations of the above

WAYS TO HAVE THREE 3x3 SUB-GRIDS
================================

# # # #
# # # #
# # # #
# # # 0

There are 4 rotations


WAYS TO HAVE FOUR 3x3 SUB-GRIDS
===============================

# # # #
# # # #
# # # #
# # # #

One way


TOTAL WAYS
==========
392 + 48 + 2 + 4 + 1 = 447

I also wrote a program to get the exact answers for 5 and 6 (by pure brute force)...
5 488256/33554432 ≈ 0.0145511627
6 1725483008/68719476736 ≈ 0.0251090825
 
You must log in or register to reply here.
Top