# Thread: Drawing black tiles! Tough one

1. ## Drawing black tiles! Tough one

Hello everyone.

-Consider that there is a chess like board with 8 * 8 tiles. All the tiles are white!!!

-There is a magic dice which rolls 95% of the time white and 5% of the time black.

-I use this dice only once for every of the 8*8=64 tiles.

-After passing from all the tiles there might be a chance that some tiles changed their color from white to black.

-I would like to find what is the chance after having used this dice after each one to be at least one black square created!

-This is the hard part. I Would like to see one black square somewhere. So this is not I think and i.i.d problem. A black square might be created in A1,A2,B1,B2 or in A2,A3,B2,B3 and so on. I do not know how to try to think for these type of problem.

I would like to have this calculated fro my thesis but as I am not a mathematician student there is almost no support from my department.

Best Regards
Alex.

2. Originally Posted by dervast
Hello everyone.

-Consider that there is a chess like board with 8 * 8 tiles. All the tiles are white!!!

-There is a magic dice which rolls 95% of the time white and 5% of the time black.

-I use this dice only once for every of the 8*8=64 tiles.

-After passing from all the tiles there might be a chance that some tiles changed their color from white to black.

-I would like to find what is the chance after having used this dice after each one to be at least one black square created!

-This is the hard part. I Would like to see one black square somewhere. So this is not I think and i.i.d problem. A black square might be created in A1,A2,B1,B2 or in A2,A3,B2,B3 and so on. I do not know how to try to think for these type of problem.

I would like to have this calculated fro my thesis but as I am not a mathematician student there is almost no support from my department.

Best Regards
Alex.
What is "i.i.d problem"?

The probability that at least one square is black is 1 minus the probability that they are all white. So it's $\displaystyle 1 - (0.95)^{64} \approx 0.9625$.

The location(s) of the black square(s) is unpredictable, since the die rolls are random.

3. Originally Posted by undefined
What is "i.i.d problem"?

The probability that at least one square is black is 1 minus the probability that they are all white. So it's $\displaystyle 1 - (0.95)^{64} \approx 0.9625$.

The location(s) of the black square(s) is unpredictable, since the die rolls are random.
Well, i.i.d is idependent and identically distributed random variables.
Independent and identically-distributed random variables - Wikipedia, the free encyclopedia

The thing is that yes it is easy to find what is the chance to having one,two,three tiles turned from white to black.
In my case I want my tiles to form a specific square thus I want the chance after having a tile turned from black to white to also have the next one to be drawn black.

This is easy. but having a square means that I also need to roll two blacks squares above the already two other existing... which is hard to find. These tiles then are not i.i.d as the chance of creating a square depends from the spatial structure:

If I have two concurrent tiles turned black .. then a square can be created by also having black tiles above or underneath the already two tiles thus this is getting more complex.Also consider that are two tiles drawn black at the left border.. then a square can only be turned black if there are two black tiles at the right side of them.

I would like to thank you for your contribution.

Best Regards
Alex

4. Originally Posted by dervast
Well, i.i.d is idependent and identically distributed random variables.
Independent and identically-distributed random variables - Wikipedia, the free encyclopedia

The thing is that yes it is easy to find what is the chance to having one,two,three tiles turned from white to black.
In my case I want my tiles to form a specific square thus I want the chance after having a tile turned from black to white to also have the next one to be drawn black.

This is easy. but having a square means that I also need to roll two blacks squares above the already two other existing... which is hard to find. These tiles then are not i.i.d as the chance of creating a square depends from the spatial structure:

If I have two concurrent tiles turned black .. then a square can be created by also having black tiles above or underneath the already two tiles thus this is getting more complex.Also consider that are two tiles drawn black at the left border.. then a square can only be turned black if there are two black tiles at the right side of them.

I would like to thank you for your contribution.

Best Regards
Alex
I have a better picture of what you're after now, but your writing is still unclear. Do we want the probability that at least one 2x2 black square is formed? Also, what if we have for example A1, A2, B1, B2, B3 all black -- does that count? Or does a 2x2 black square have to be surrounded by white squares?

In general when I write "square" I mean 1x1 square unless another side length is explicitly mentioned.

The probability of getting exactly four black squares arranged in a 2x2 square is:

(probability of getting exactly four black squares) * (probability of getting a 2x2 square arrangement given that exactly four black squares were drawn)

This is $\displaystyle (0.05)^4(0.95)^{60} \cdot \displaystyle \frac{49}{\binom{64}{4}}$

Do you see why?

Then suppose A1, A2, B1, B2, B3 does count, and we want to find the probability that at least one 2x2 black square is formed. I've thought about this a bit and it seems tricky.. I might solve it, but I don't want to solve it if it's not what you're after. Please clarify what probability you want.

5. Originally Posted by undefined

(probability of getting exactly four black squares) * (probability of getting a 2x2 square arrangement given that exactly four black squares were drawn)

This is $\displaystyle (0.05)^4(0.95)^{60} \cdot \displaystyle \frac{49}{\binom{64}{4}}$
Without saying anything regarding the original question (which I don't really understand), are you sure the above isn't suppose to be just

$\displaystyle (0.05)^4(0.95)^{60}\cdot 49$

The reason I mention it is because the probability that ONLY four black squares are chosen is $\displaystyle {\binom{64}{4}} \cdot (0.05)^4(0.95)^{60}$

While the probability of getting a 2x2 square arrangement given that exactly four black squares were drawn is the following;

$\displaystyle \frac{49}{\binom{64}{4}}$

6. Originally Posted by jamix
Without saying anything regarding the original question (which I don't really understand), are you sure the above isn't suppose to be just

$\displaystyle (0.05)^4(0.95)^{60}\cdot 49$

The reason I mention it is because the probability that ONLY four black squares are chosen is $\displaystyle {\binom{64}{4}} \cdot (0.05)^4(0.95)^{60}$

While the probability of getting a 2x2 square arrangement given that exactly four black squares were drawn is the following;

$\displaystyle \frac{49}{\binom{64}{4}}$
Ah, you're right! I forgot that order matters. (Equivalently, I forgot to use the binomial distribution.) Good catch.

7. At first let's all use this chess board as reference http://www.webster.uk.net/HobbiesAnd...oard_blank.gif
Just to mention here that in this problem the chess board starts with all the tiles painted white.

Do we want the probability that at least one 2x2 black square is formed?
Yes plz
Also, what if we have for example A1, A2, B1, B2, B3 all black -- does that count?
Yes it does count. There is a square formed let alone what its neighbors are.

In general when I write "square" I mean 1x1 square unless another side length is explicitly mentioned.
We agree in this definition

The probability of getting exactly four black squares arranged in a 2x2 square is:

(probability of getting exactly four black squares) * (probability of getting a 2x2 square arrangement given that exactly four black squares were drawn)

This is $\displaystyle (0.05)^4(0.95)^{60} \cdot \displaystyle \frac{49}{\binom{64}{4}}$

Do you see why?
No I do not see why. Unfortunately for me there is some spatial dependence in this problem and I do not know hot to handle it. This game begins with the chess board being all painted white.
I am using my "magical" dice and I roll once for each tile filling row by row. I start from
A1 then i go to B1,C1,...H1 then I roll for second row
A2 then i go to B2,C2,...H2..
..
A8 then i go to B8,C8...H8.

Let's say that my fist black roll comes in tile D4 which I paint black then I have to find what is the possibility of E4 to be black and then what is the possibility of D5,E5 to be black all together.

Then suppose A1, A2, B1, B2, B3 does count, and we want to find the probability that at least one 2x2 black square is formed. I've thought about this a bit and it seems tricky.. I might solve it, but I don't want to solve it if it's not what you're after. Please clarify what probability you want.
I am after finding that at least one square is formed let alone the neighbors. This might be a little confusing as a A1,A2,A3,B1,B2,B3 is a square (or it is two square).

8. Originally Posted by dervast
No I do not see why. Unfortunately for me there is some spatial dependence in this problem and I do not know hot to handle it.
Well as jamix pointed out, I meant to write

$\displaystyle (0.05)^4(0.95)^{60}\cdot 49$

but made a mistake along the way. The idea is that if you're given that exactly 4 squares are black, then any arrangement of the black squares is equally likely. There are $\displaystyle \binom{64}{4}$ arrangements, and only $\displaystyle 49$ of them result in a 2x2 square, which leads to the above expression.

BEGIN EDIT

I've uncovered a flaw in the reasoning below. For two 2x2 squares, we would also have to consider non-overlapping arrangements like A1,A2,B1,B2,D1,D2,E1,E2. Well I'll have to think about it some more then.

END EDIT

As for your original problem, I think it can be solved as follows. We use the principle of inclusion-exclusion. The probability of getting A1,A2,B1,B2 black regardless of all others is $\displaystyle (0.05)^4$. There are 49 of these 2x2 squares, so take $\displaystyle 49\cdot(0.05)^4$. But we're not done yet because we counted duplicates. Now the probability of getting A1,A2,A3,B1,B2,B3 is $\displaystyle (0.05)^6$. Considering just the rectangles with these dimensions and this orientation, we have $\displaystyle 6\cdot7$ of them, giving $\displaystyle 42\cdot(0.05)^6$. Next, consider that the probability of getting A1,A2,B1,B2,C1,C2 is the same; combining all this, we arrive at the intermediate result

$\displaystyle 49\cdot(0.05)^4-84 \cdot(0.05)^6$

Then we would proceed to calculate the probability of getting arrangements leading to three 2x2 squares, using a "+" instead of a "-" for the next term, etc., all the way to 49.

It's possible there is some mistake in my reasoning, although at the moment everything seems sound. To counteract the possibility of a mistake, I would write a Monte Carlo and see how close the results were. If they were quite close, then it would increase my confidence that I didn't make a mistake. Another option is to try out the idea on smaller boards (e.g., 4x4) and see if the results make sense.

I'm assuming you want an exact answer. Because if you're just after an approximation, then you can use Monte Carlo, which will give you more precision the longer you run it, but if you need a lot of precision then this could take a prohibitively long time.

9. While an exact answer is worked towards, here is Java code for a Monte Carlo:

Code:
import java.util.Random;

public class ChessBlackSquare22 {
static Random g=new Random();

public static void main(String[] args) {
monteCarlo();
}

static void monteCarlo() {
int i,j;
long s=0,t,t1=time();
boolean b,c[][];
for(t=0;;t++) {
if(t>0&&(t%500000)==0) System.out.println("Trials: "+t+
", Probability: "+(s/(double)t)+", Elapsed:"+((time()-t1)/1000.0));
b=false;
c=new boolean[8][8];
for(i=0;i<8;i++)
for(j=0;j<8;j++)
if(g.nextInt(20)==0) c[i][j]=true;
for(i=0;i<7;i++)
for(j=0;j<7;j++)
if(c[i][j]&&c[i][j+1]&&c[i+1][j]&&c[i+1][j+1]) {
b=true;
break;
}
if(b) s++;
}
}

static long time() {
return System.currentTimeMillis();
}
}
I have an idea to optimise the code a bit that I don't feel like implementing just this second, but in a relatively short time I've already got almost 10^9 trials, so I'm not sure how worthwhile it would be.

The answer seems to be somewhere in the range [0.000305, 0.000308].

10. Originally Posted by undefined
There are $\displaystyle \binom{64}{4}$ arrangements, and only $\displaystyle 49$ of them result in a 2x2 square, which leads to the above expression.
Exactly there are 49 such arrangements. Really did u measure them in the chess board or you calculated somehow?

I've uncovered a flaw in the reasoning below. For two 2x2 squares, we would also have to consider non-overlapping arrangements like A1,A2,B1,B2,D1,D2,E1,E2. Well I'll have to think about it some more then.
Yeah that is true and this is the hard part of this problem!

As for your original problem, I think it can be solved as follows. We use the principle of inclusion-exclusion. The probability of getting A1,A2,B1,B2 black regardless of all others is $\displaystyle (0.05)^4$. There are 49 of these 2x2 squares, so take $\displaystyle 49\cdot(0.05)^4$. But we're not done yet because we counted duplicates. Now the probability of getting A1,A2,A3,B1,B2,B3 is $\displaystyle (0.05)^6$. Considering just the rectangles with these dimensions and this orientation, we have $\displaystyle 6\cdot7$ of them, giving $\displaystyle 42\cdot(0.05)^6$. Next, consider that the probability of getting A1,A2,B1,B2,C1,C2 is the same; combining all this, we arrive at the intermediate result

$\displaystyle 49\cdot(0.05)^4-84 \cdot(0.05)^6$

Then we would proceed to calculate the probability of getting arrangements leading to three 2x2 squares, using a "+" instead of a "-" for the next term, etc., all the way to 49.

It's possible there is some mistake in my reasoning, although at the moment everything seems sound. To counteract the possibility of a mistake, I would write a Monte Carlo and see how close the results were. If they were quite close, then it would increase my confidence that I didn't make a mistake. Another option is to try out the idea on smaller boards (e.g., 4x4) and see if the results make sense.

I'm assuming you want an exact answer. Because if you're just after an approximation, then you can use Monte Carlo, which will give you more precision the longer you run it, but if you need a lot of precision then this could take a prohibitively long time.
I think I got all your reasoning which is nearly tough to be calculated.. I am trying to build up understanding as my problem is much harder. I have a 100*100 population with white tiles and the percentages as described above and I want to apply the same technique for having at least one black square created. This is sort of biological simulator that I want to show after how many centuries (1 turn == 1 year) this square can be formed (which is the requirement for something new to happen).If I got it right using the normal procedure will be impossible to find this probability as it will take ages to be calculated. Of course if I know what is the possibility of having one square formed then it is easy to find exactly how many centuries I need.

Thus it is the time to use monte-carlo but bad for me I have not ever heard this term and thus I need fast to build up understanding. Could you please help me concerning that by giving me some links to study and trying to modify your code to apply into my case?

I would like to thank you in advance . Best Regards
Alex

11. Originally Posted by dervast
Exactly there are 49 such arrangements. Really did u measure them in the chess board or you calculated somehow?
Yeah that is true and this is the hard part of this problem!

I think I got all your reasoning which is nearly tough to be calculated.. I am trying to build up understanding as my problem is much harder. I have a 100*100 population with white tiles and the percentages as described above and I want to apply the same technique for having at least one black square created. This is sort of biological simulator that I want to show after how many centuries (1 turn == 1 year) this square can be formed (which is the requirement for something new to happen).If I got it right using the normal procedure will be impossible to find this probability as it will take ages to be calculated. Of course if I know what is the possibility of having one square formed then it is easy to find exactly how many centuries I need.

Thus it is the time to use monte-carlo but bad for me I have not ever heard this term and thus I need fast to build up understanding. Could you please help me concerning that by giving me some links to study and trying to modify your code to apply into my case?

I would like to thank you in advance . Best Regards
Alex
My goal is to be helpful rather than critical, but your lack of attention to detail causes me some distress. You claimed to agree earlier that a "square" would generally mean a 1x1 square unless another dimension is specifically mentioned. You seem never to be using this convention. As a result, I have to constantly guess what you mean to say. In addition, the scenario you described for your *actual problem* seems not to follow directly from the problem you posted here originally. The problem you posted here originally applies to your 100x100 problem *only if* the 100x100 board gets wiped clean (all of the tiles are again white) from one year to the next, provided no 2x2 black square appears. But the way you worded it leads me to believe this is not the case. (Again, I have to guess your meaning.) So after 1 year, if there are black tiles on the board that do not get wiped clean, this will increase the probability that a 2x2 black square appears the second year compared with the first.

Anyway, Monte Carlo means you run simulations using (pseudo-)random number generation. Here is a Wikipedia article on it. Monte Carlo can take a very long time to calculate to a given precision, but an exact method will often run quickly. It can still be useful to do Monte Carlo to confirm the answer gotten by an exact method, or if no exact solution can be found. Often Monte Carlo is very easy to program. The one I wrote above took very little time to write, maybe 10-15 minutes.

I got 49 from considering the location of (for example) the top-left square of the 2x2 square. There are 49 (that is, 7x7) ways to place the top-left square on an 8x8 board.

Please let me know how you'd like this discussion to proceed. Please reconsider whether this 8x8 problem translates properly to your 100x100 problem. There does not seem much use putting a lot of effort into solving a problem that you *think* is a subproblem of your actual problem, if it isn't really a subproblem.

Ask me if there's anything I said that you'd like explained further.

12. Originally Posted by undefined
Please let me know how you'd like this discussion to proceed. Please reconsider whether this 8x8 problem translates properly to your 100x100 problem.

Ask me if there's anything I said that you'd like explained further.
Hello again
I would like to apologize for any inconvenience caused.In my scenario the 8*8 problem translates properly to 100*100 problem. I assume that the populations are regenerated after every round which is like running the same game from the beginning.

This is my first scenario which is the easiest. Well even this is too hard to be replied. In a latter scenario I would like to think for death and reborn rates (ie. Every year 10% of the population dies and 10% is getting recreated) which will be more like reality. But I do not want to attack both problems together. Let's try to solve the first easy version of this game which is starting every year from the beginning.

I would like to thank you in advance.
Best Regards
Alex

13. Originally Posted by dervast
Hello again
I would like to apologize for any inconvenience caused.In my scenario the 8*8 problem translates properly to 100*100 problem. I assume that the populations are regenerated after every round which is like running the same game from the beginning.

This is my first scenario which is the easiest. Well even this is too hard to be replied. In a latter scenario I would like to think for death and reborn rates (ie. Every year 10% of the population dies and 10% is getting recreated) which will be more like reality. But I do not want to attack both problems together. Let's try to solve the first easy version of this game which is starting every year from the beginning.

I would like to thank you in advance.
Best Regards
Alex
Okay, it was hard to know. I'll keep thinking about an exact/quick/simple solution if possible, and hopefully if I don't think of something, someone else will.

14. Just an update: Still thinking about the exact solution and nothing to report yet, but my Monte Carlo is currently at 43 * 10^9 trials and the answer appears to be in the range [0.0003057, 0.0003060], but I haven't done the work to find 99% confidence interval so that's just an estimate.

15. Originally Posted by undefined
Just an update: Still thinking about the exact solution and nothing to report yet, but my Monte Carlo is currently at 43 * 10^9 trials and the answer appears to be in the range [0.0003057, 0.0003060], but I haven't done the work to find 99% confidence interval so that's just an estimate.
I would like to thank you in advance for your help and support.
I think at first we should try to chance your reasoning a little just for the 100*100 area scenario. I will start studying now and I ll try to post back later on this evening. I would like to thank you in advance for your help.
Best Regards
Alex

Page 1 of 2 12 Last