FRIHOST • FORUMS • SEARCH • FAQ • TOS • BLOGS • DIRECTORY
You are invited to Log in or Register a Frihost Account!

Probability Problem

   Frihost Forum Index -> Science -> Basics
 


ninjakannon
Despite taking further mathematics, I appear to have completely forgotten statistics. In doing some work (for myself) I have come upon a problem that I haven't managed to solve, despite much though.

So here it is. We have an x by x grid/table of cells (like a chess board). Each cell initially contains a 0. I sequentially apply an operation f a number of times n. The operation f randomly selects a cell and switches its value; if it's a 0 it becomes 1 and vice versa. The same cell can be changed multiple times, back and forth between 0 and 1.

I would like to know, in terms of x and n, what the probability is of a given cell having a different value from its starting value (a 1, in this example) after the n applications of f.

Any help would be much appreciated! Thank you.
ocalhoun
ninjakannon wrote:
Despite taking further mathematics, I appear to have completely forgotten statistics. In doing some work (for myself) I have come upon a problem that I haven't managed to solve, despite much though.

So here it is. We have an x by x grid/table of cells (like a chess board). Each cell initially contains a 0. I sequentially apply an operation f a number of times n. The operation f randomly selects a cell and switches its value; if it's a 0 it becomes 1 and vice versa. The same cell can be changed multiple times, back and forth between 0 and 1.

I would like to know, in terms of x and n, what the probability is of a given cell having a different value from its starting value (a 1, in this example) after the n applications of f.

Any help would be much appreciated! Thank you.


Well, I can see that the probability of a 1 will start at 0% and gradually work towards 50%, but will never reach 50%, because of the bias introduced by starting with all 0's.
probability=1/(x*x) -changing one cell to a 1.
probability=(.5n)/(x^2) -changing a random, untouched cell to a random value, but won't work if n>x^2, and assumes that cells won't be changed twice.
IF(n<x^2) THEN(probability=(.5n)/(x^2)) ELSE (probability=.5) -had to introduce algorithm, but it is correct, except that it assumes cells won't be changed twice until after n=x^2

*edit*
I tried... I really did.
But I failed also. Trying to find out the likelihood that the next cell changed will be one that hasn't been changed before is too tricky for me! In order to determine it, it seems like you have to already know it: the likelihood of changing and untouched cell depends on how many cells have been touched, and how many cells have been touched depends on the likelihood of changing an unchanged cell!

Here's what I got though, I suppose it might help you a little.
The likelihood that a random cell will be one that is already changed (prototype version):(x^2)-n)/(x^2)
-will result in a ratio of unchanged cells over total cells. This equation works for n=0 and n=1, but does not work for n>1. I keep thinking that it has to have some kind of self-reference in order to work, perhaps an algorithm that runs through it n times...

*edit again*
I thought of making an experiment to help understand it.
Make a program that actually performed this, several times over, going from n=0 to n=2(x^2), first with x=1, and proceeding up through the x values. For each value of x, it would run many times, and compile a graph of the results. The ratio would be on one axis, 'n' on the other axis. For each value of x, it would give us a curve describing the likelihood of choosing an unchanged square. From a single value of x, you could perhaps devise an equation to match that curve.
With x=1, you'd have 1/1 dropping instantly to 0/1
With x=2, you'd have 1/1 curving towards 0/1, steepest at first, then gradually leveling off, never becoming a straight line, never reaching 0/1.
With x=100, the curve would start less steep than x=2, but still steepest at first, then leveling off.

If all these graphs were set together along a third axis, 'x', it would give you a 3 dimensional curve! A better mathematician than me could figure out an equation that describes that 3 dimensional curve, and that equation would be the key.
ninjakannon
Thank you so much for spending time over this, I like your enthusiasm over it. What you've said has spurred me down different thought paths and I've noticed a few interesting things as a result, but like you haven't found an answer either.

I can't see exactly how you've got some of your formulae. Obviously, 1/(x^2) is the probability of changing one cell. And I think I understand (.5n)/(x^2). However,

Quote:
The likelihood that a random cell will be one that is already changed (prototype version)Sadx^2)-n)/(x^2)

Are you sure?

I got a completely different formula: sum from r=1 to r=n ( (1/x^2)^r )
They could be equivalent, or I made a hideous error.

((x^2)-n)/(x^2) = 1 - n / x^2 = 1 - nx^-2. That reminds me of binomial expansions, it's the first 2 terms of the expansion of (1 - x^-2)^n, isn't it? I can't see how that would equate to my formula, so I've probably made a mistake.


Your mention of drawing a graph also got me thinking. I've made a program that calculates the number of routes there are after n applications of f (this being x^(2n)) and also the number of these that end with the first number (top-left in the grid) being a 1. The probability that, after the n operations, a given cell has changed its value is then this latter value divided by x^(2n).

If I were to plot a graph of x-axis: total possibilities to y-axis: number of routes ending with 1 in first cell, I could attempt to find the equation of the curve. The derivative of that would be an equation for the probability, would it not?
ocalhoun
ninjakannon wrote:

I got a completely different formula: sum from r=1 to r=n ( (1/x^2)^r )
They could be equivalent, or I made a hideous error.

No, I'm quite sure that my formula is the one with the hideous error, in that case.
It only works for n=1 and n=0... And completely fails for any other value of n. Seems to me, that's evidence for a hideous error.
It may, however, give you fresh ideas for how to pursue the problem.

Attempting to explain (x^2)-n)/(x^2):
x^2=total number of cells.
(x^2)-n=number of cells minus number of changed cells.
So, it is (total number of cells - changed cells)/(total number of cells), which gives you the ratio of unchanged cells to total cells.

I had made quite a few modifications of that, some much more complicated, but none of them gave better results than that one. Most of the variations dealt with replacing 'n' with an equation that didn't assume one cell would be changed for every repetition. Problem is, the likelihood of changing an unchanged cell depends on the ratio of unchanged cells to total cells... so you have to solve this equation before you can solve it. :?

You need the services of a master mathematician, and I, alas, am a mere amateur.

*edit*
I just realized that your stipulation of making an x by x grid of squares needlessly complicates making formulas.
Until you find a formula, just find the answer with a system that has x number of cells. The x number of cells, 'x' can be replaced with an x by x grid, 'x^2' after the equation is figured out, making the equations easier to work with in the meantime.
nilsmo
ninjakannon wrote:
We have an x by x grid/table of cells (like a chess board). Each cell initially contains a 0. I sequentially apply an operation f a number of times n. The operation f randomly selects a cell and switches its value; if it's a 0 it becomes 1 and vice versa. The same cell can be changed multiple times, back and forth between 0 and 1.

I would like to know, in terms of x and n, what the probability is of a given cell having a different value from its starting value (a 1, in this example) after the n applications of f.


Thanks for the clear problem statement.

Each application of f has a p = 1/x^2 chance of changing the given cell.

After n applications of f, the chance a given cell is changed A times is (A choose n) p^A (1-p)^(n-A). This follows a binomial distribution, with each application of f being a Bernoulli event, so that's maybe what you were referring to when you mentioned statistics. Smile

So if you have say 3 applications of f you get the probability of the cell changing value as:
(3 choose 1) p^1 (1-p)^2 + (3 choose 2) p^2 (1-p)^1

(Notice this is every other term of the binomial expansion of (p + (1-p))^n))

Unfortunately the binomial distribution ain't pretty (and combinations can't really be simplified when there are crazy coefficients) so I don't think you can get a simple answer. You'll just have to add up the terms manually or (most likely) using a computer program.
ninjakannon
That is why I mentioned statistics, nilsmo! I even looked at the binomial distribution, but couldn't figure out how it related to the problem.

I see and understand what you've done here, thank you very much for your clear explanation!

The probability that a single cell has a different value from its starting value is simply the probability that A is odd, giving us the probability r that a cell has changed its value:

r = 0
for (A = 1; A <= n; n += 2) {
r += (A choose n) p^A (1-p)^(n-A)
}


Sorry it took me so long to reply, I've just started university!
Related topics

Math learning
The Monty Hall Paradox
Math Problem
Homework problem
Problem with Subdomains
Strange Fire fox problem
Logout problem (Cookie?)
How to solve this problem? Thanks
I have a problem....Mozilla Firefox
post nuke problem
anyone had this phpBB problem?
phpbb problem....
Problem with my password
Pictures problem...
database problem
same problem over here...
Reply to topic    Frihost Forum Index -> Science -> Basics

FRIHOST HOME | FAQ | TOS | ABOUT US | CONTACT US | SITE MAP
© 2005-2007 Frihost, forums powered by phpBB.