Probability problem

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Probability problem

Postby Goahead52 » Wed Feb 22, 2017 4:04 pm UTC

Hi,

We have a squared grid 10x10.
We color randomly 50 squares in red and the remaining in blue.
We define a relation of ownership as follows :
A square A(i,j) (red or blue) is owned by the blue player if the number of the adjacent squares (orthogonally and diagonally) colored in blue surrounding A(i,j) is > to the squares colored in red. If the numbers are equal no one own that square A(i,j). Otherwise the red player owns that square.

There are 100 squares on the grid. Let us call :

B the squares owned by the blue player
R the squares owned by the red player
and N the number of squares not owned by any of the players
D=abs(R-B)

Can we find a closed formula for the law distribution of P(D=k) where k>=0 ?

Thank you for any clue

Tub
Posts: 300
Joined: Wed Jul 27, 2011 3:13 pm UTC

Re: Probability problem

Postby Tub » Thu Feb 23, 2017 9:46 am UTC

Can you clarify the ownership formula? Does the cell's own colour count, or only the colours of the neighbours? How does it work on the corners, do the neighbours "wrap around", or do the corner cells simply have fewer neighbours?

Am symmetry argument says that P(B=k) = P(R=k), but any further insight seems to be a combinatorial nightmare. Having exactly 50 red and 50 blue cells looks much harder than throwing a coin for each cell, because your cell colors stop being independent, making it much less likely to find a nice closed form.

Unfortunately, there's around 10^29 possibilities (a bit less if you exploit symmetries), which is too much for brute forcing.

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Probability problem

Postby Goahead52 » Thu Feb 23, 2017 12:47 pm UTC

Tub wrote:Can you clarify the ownership formula? Does the cell's own colour count, or only the colours of the neighbours? How does it work on the corners, do the neighbours "wrap around", or do the corner cells simply have fewer neighbours?

Am symmetry argument says that P(B=k) = P(R=k), but any further insight seems to be a combinatorial nightmare. Having exactly 50 red and 50 blue cells looks much harder than throwing a coin for each cell, because your cell colors stop being independent, making it much less likely to find a nice closed form.

Unfortunately, there's around 10^29 possibilities (a bit less if you exploit symmetries), which is too much for brute forcing.


Only the colors of the neighbors count.
On the corners the edges are considered like occupied squares : the square in the corner up left is surrounded by 3 squares hence one of the players owns it.
Squares have 3, 5 or 8 neighbors.
Maybe simulation could give some results. A close formula using generating function (?)

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Probability problem

Postby Goahead52 » Thu Feb 23, 2017 11:07 pm UTC

There is maybe a way to find some pattern if we start by a grid 2x2 (2 blue 2 red) then 4x4 (8 blue, 8 red) and 2nX2n with n>4.
In 2x2 which easy to analyze B=2, R=2, N=0,D=0 for all the configurations.
Is this method going to lead to some close formula? I do not know for now.

lorb
Posts: 404
Joined: Wed Nov 10, 2010 10:34 am UTC
Location: Austria

Re: Probability problem

Postby lorb » Sat Feb 25, 2017 7:55 am UTC

Tub wrote:Am symmetry argument says that P(B=k) = P(R=k), but any further insight seems to be a combinatorial nightmare. Having exactly 50 red and 50 blue cells looks much harder than throwing a coin for each cell, because your cell colors stop being independent, making it much less likely to find a nice closed form.


It's also rather easy to see that 64 is an upper bound for N. In general for a nxm grid N can never exceed (n-2)(m-2) and can always be 0.

-- edit: had D, where it should be N
Last edited by lorb on Thu Mar 02, 2017 7:38 pm UTC, edited 1 time in total.
Please be gracious in judging my english. (I am not a native speaker/writer.)
http://decodedarfur.org/

DavidSh
Posts: 64
Joined: Thu Feb 25, 2016 6:09 pm UTC

Re: Probability problem

Postby DavidSh » Sat Feb 25, 2017 3:36 pm UTC

Perhaps Goahead52 can clarify the values of B, R, and N for the following situation, because I don't think it follows lorb's bound.

Code: Select all

RRRR
BBBB
BBBB
RRRR

To me, it looks like the red cells all have one more blue neighbor than red neighbors and the blue cells all have two more blue neighbors than red neighbors. This would give B=16, R=0, N=0, D=16.

Did I misinterpret the rules?

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Probability problem

Postby Goahead52 » Sat Feb 25, 2017 3:46 pm UTC

DavidSh wrote:Perhaps Goahead52 can clarify the values of B, R, and N for the following situation, because I don't think it follows lorb's bound.

Code: Select all

RRRR
BBBB
BBBB
RRRR

To me, it looks like the red cells all have one more blue neighbor than red neighbors and the blue cells all have two more blue neighbors than red neighbors. This would give B=16, R=0, N=0, D=16.

Did I misinterpret the rules?


No. Your results :
"B=16, R=0, N=0, D=16"
are right.

You understood well the rules.

lorb
Posts: 404
Joined: Wed Nov 10, 2010 10:34 am UTC
Location: Austria

Re: Probability problem

Postby lorb » Thu Mar 02, 2017 7:39 pm UTC

DavidSh wrote:Perhaps Goahead52 can clarify the values of B, R, and N for the following situation, because I don't think it follows lorb's bound.


That is because I wrote D where it should have said N. :/
Please be gracious in judging my english. (I am not a native speaker/writer.)
http://decodedarfur.org/

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Probability problem

Postby Goahead52 » Fri Mar 03, 2017 7:15 pm UTC

lorb wrote:
DavidSh wrote:Perhaps Goahead52 can clarify the values of B, R, and N for the following situation, because I don't think it follows lorb's bound.


That is because I wrote D where it should have said N. :/


Do you mean that for 10x10 grid that the value D could not reach 100 ?
I`m working on configuration such as D=100. I did not finished yet.

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 25740
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: Probability problem

Postby gmalivuk » Fri Mar 03, 2017 7:18 pm UTC

No, writing D was the mistake. N cannot be 100 because the edges and corners are always owned by someone.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Probability problem

Postby Goahead52 » Fri Mar 03, 2017 8:23 pm UTC

gmalivuk wrote:No, writing D was the mistake. N cannot be 100 because the edges and corners are always owned by someone.


In grid 4x4 a blue player (or the red player) could own all the squares. Look at the solution given above by DavidSh.
Why not in 10x10?

User avatar
WibblyWobbly
Can't Get No
Posts: 506
Joined: Fri Apr 05, 2013 1:03 pm UTC

Re: Probability problem

Postby WibblyWobbly » Fri Mar 03, 2017 8:53 pm UTC

Goahead52 wrote:
gmalivuk wrote:No, writing D was the mistake. N cannot be 100 because the edges and corners are always owned by someone.


In grid 4x4 a blue player (or the red player) could own all the squares. Look at the solution given above by DavidSh.
Why not in 10x10?

It's quite possible you can have all squares in a 10x10 grid owned by one player. What you can't have is more than 64 of the squares be unowned. Boundary squares must always be owned in a game in which all grid squares are initially assigned a color.

Now, if you don't assign colors to all 100 squares at the beginning, edge squares could become unowned. Not sure how that would affect the limit on N, though.

For the original idea of the upper bound on N: this is apparently true in higher dimensions as well, isn't it? Boundary squares/cubes/hypercubes will always have an odd number of neighbors?

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 25740
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: Probability problem

Postby gmalivuk » Fri Mar 03, 2017 9:11 pm UTC

Goahead52 wrote:
gmalivuk wrote:No, writing D was the mistake. N cannot be 100 because the edges and corners are always owned by someone.


In grid 4x4 a blue player (or the red player) could own all the squares. Look at the solution given above by DavidSh.
Why not in 10x10?
Why not what?

N cannot be 100. I wasn't saying anything about D, and lorb admitted a mistake, so also wasn't intentionally saying anything about D.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Probability problem

Postby Goahead52 » Fri Mar 03, 2017 9:24 pm UTC

The upper bound of N is obvious.
I`m interested by the values of D and their probability.
Until now if you put aside the simulation (which is easy to do for someone who is programmer) it is hard if not impossible to have a close formula for those values.


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 5 guests