Help with probability problem? (NationStates population)

[>-)]

I play this game called NationStates. Basically you create a nation, one of over a hundred thousand in 'The World'. By expressing your opinion on many controversial issues, you can change many characteristics of your nation. However, your population cannot be changed in anyway. The population of a nation is changed once a day. Besides the first 3 or so weeks, a nation will grow either 5 million, 6 million, or 7 million people per day. So while people who started near the creation of the game have a population of over 20 billion, the vast majority have less. I wondered how big my nation, which currently has a population of 610 million, would need to grow before i had a decent chance (50%+) of outpopulating someone who started, maybe 10 days ahead of me and so had around 60 million more population.

I approached the problem like this:

The first three weeks or so have a constant and determined population growth, so i ignored that for now.

On the first day (of non determined population growth), i have an equal change of getting 5 million, 6 million, or 7 million population.
If probability works, then over a long time period, i should have very close to 6 million population/day.

So on day one, i have 2/3 chance of being 1 million away from the 'average' of 6 million.
I have 1/3 chance of being 0 away from the 'average'.

So on average, after day one, i will be 2/3's million away from the average. Half chance that i will be more (than 2/3's million from 6 million population), and half chance less.

But however, because my population can't be 5.6666 million or 4.3333 million, it's really twice the chance that i will be more than less. This is only for one day, though, and since i plan calculating it for hundreds and thousands of days, i'll just ignore that fact.

On day two,
i have 1/9th chance of being 2 million away above 'average'
i have 1/9th chance of being 2 million away below 'average'
2/9th chance of being 1 million away above 'average'
2/9th chance being 1 million below 'average'
3/9th chance being 'average'

So that means i have
2/9th chance being 2 million away from 'average'
and 4/9th chance being 1 million away from 'average'
3/9th chance being 'average'

When i average this, it comes out to 8/9 million away from average.

On day three, the chances are
1,3,6,10,6,3,1
Day 4
1,4,10,16,19,16,10,4,1
Day 5
1,5,15,30,45,51,45,30,15,1

http://ptri1.tripod.com/ptreal1r.gif

So with that, the average distance from the 'average' of 6 million growth per day for days 1-5 comes out to be

2/3
8/9
10/9
104/81
350/243

Which turns out to be

162/243
216/243
270/243
312/243
350/243

And, i can't find any sequence for this.

[gmalivuk]

I interpret this to mean i will never have a chance of varying off from my 6 million/day by more than several million at most.

Why do you interpret it this way?

[>-)]

Because the average distance i'll be from my expected population of 6 million * days is only 4/3rds million. I'll have a very small chance of getting much below or above that. But the random numbers don't seem to match that expectation.

Edit: i took 3 random sequences of pi, around 300-500 digits long and i'm still 34, 9, and 5 off from the 6*number of digits where 4/3rds is expected.

[gmalivuk]

Because the average distance i'll be from my expected population of 6 million * days is only 4/3rds million. I'll have a very small chance of getting much below or above that.

Have you computed the variance of this distribution? Because that's the parameter that actually gives an indication of how far from the expected value you're likely to deviate.

But in any case, your numbers are wrong after day 2. On day 3, your chances are 1, 3, 6, 7, 6, 3, and 1. (Your sanity check should be that the total always has to be the next power of 3.) On day 4, they're 1, 4, 10, 16, 19, 16, 10, 4, 1.

[>-)]

I fixed the errors and now the first three days/points/numbers are linear. I tried taking out the first number so that there is still a curve, but still couldn't find any sequence that way.

And, do you mean finding the variance of each day?
Like Day 5 would be
1, 5, 15, 30, 45, 51, 45, 30, 15, 5, 1
which would be 37.87

or do i find the variance in the chance of possible populations? For example, on day 5
25 (million) * 1/243
26*5/243
27*15/243
28*30/243
29*45/243
30*51/243
31*45/243
32*30/243
33*15/243
34*5/243
35*1/243

which would be a variance of 6.63




I'm not exactly sure how variance will help me find what i'm looking for though.

[gmalivuk]

I just meant that variance is what will tell you how likely you are to be close or far from the mean. But that's not really relevant, because the expected difference from 6d million doesn't approach a constant as you originally thought it did.

What you have is a kind of random walk. By a similar argument to the one on that page, and treating the population changes as -1, 0, and +1 instead of 5, 6, and 7 million, we can see that the expected square of the total difference from the "origin" after n days is 2/3 n, meaning it increases without bound.

[>-)]

So, after n days, the expected difference from the "origin" is sqrt(2/3n)?
Doesn't that make the expected difference actually go down?
I tried to read the article but didn't really understand any of it.

edit: Oh did you mean 2/3*n, in which case the expected difference from "origin" is sqrt(2n/3)?

[gmalivuk]

edit: Oh did you mean 2/3*n

Yes.

in which case the expected difference from "origin" is sqrt(2n/3)?

On that order, anyway. As in the simpler case, there's probably a constant term on top of that, but it doesn't change the fact that the expected distance grows without bound.

[>-)]

Edit: Do you mind showing me how you got this thingy of sqrt(2n/3)?

Also, can you define what you mean by 'expected'?

[gorcee]

Edit: Do you mind showing me how you got this thingy of sqrt(2n/3)?

Also, can you define what you mean by 'expected'?

"Expected" in the context of probability typically means "average" or "mean".

What's important to remember is that the "expected" or "average" value does not necessarily mean that you can actually ever get this value. For instance, what's the average value of a fair die roll?

E(X) = 1/6*1+1/6*2+1/6*3+1/6*4+1/6*5+1/6*6 = 1/6*(1+2+3+4+5+6) = 1/6*(21) = 3.5

Obviously, you can never roll a die and get a 3.5. But if you roll a die a whole bunch of times, your average value is going to be 3.5. (Note: this is why in craps, when you roll two dice, a 2*3.5 = 7 clears the table for the house any time after a point is established. This is also why it's considered "bad luck" to say the word "seven" at a craps table -- usually when a 7 comes up, people lose money!).

[gmalivuk]

Edit: Do you mind showing me how you got this thingy of sqrt(2n/3)?

For each step (of -1, 0, or +1 with equal probability), the average of the squares of the results is 2/3 (2/3 chance to be 1, 1/3 chance to be 0). So after n independent steps, the average of the square of the total is the total of the average square result, or (2/3)n.

[Dobblesworth]

The Overlord of 3.99 billion strong populace of The 1337 Skillz of Phwakattack salutes your small and prosperous nation!

A good chance of population overtake can occur if your rival allows their nation to fall inactive. Gameplay is suspended and the nation is deleted (but can be resurrected at any time as the memory remains), in which time your nation can continue growth past it.

[>-)]

With the sqrt(2n/3) thingy, i can't really figure out the chances of a smaller nation overtaking a bigger nation at any time.
I tried something like this.
If nation A has n million population more than nation B,
then there is a 1/2 chance of nation A's population decreasing randomly compared to the expected amount
and a 1/2 chance of nation B's population increasing randomly compared to the expected amount.
So there is a 1/4th chance that nation A's population will go down as nation B's population goes up (relative to the expected amount).

When sqrt(2d/3)=1/2n, where d=days and n is the original difference in population between nation A and B, then there is a 50% chance that nations B's population will be above/below nation A's.

However, because there is a 1/4th chance that nation A's population will go down as nation B's population goes up (relative to the expected amount), i've only really calculated the amount of days before i have a 1/8th chance.

There's also the possibility of both our populations going up/down and one increasing/decreasing relative to the expected amount faster than the others, but i haven't calculated this because it seems unlikely that this will add up perfectly to the 50% chance that i want.

[mfb]

After n days, you get a probability distribution for both A and Bs population. To calculate the probability that A>B, you have to integrate over these distributions (double integral). However, you can treat the difference itself as random variable and calculate this distribution, which reduces the problem to a single integral.

To get the distribution, it is the easiest way to approximate it as a gaussian distribution with fixed mean value (the initial difference) and a variance given by 4/3 n. The probability that A>B is then given by the integral over this distribution from 0 to infinity (or from -infinity to 0, depending on the definition).

The probability will approach 50% (which means that a fixed initial difference does not matter much in the long run), but never exceed this value (as one player always has the initial advantage).

[>-)]

Ok, could you explain why the distribution is gaussian and has a variance of 4/3n?



also, in that formula above, what should a, b, and c equal and where does the variance of 4/3rds fit in?

[mfb]

>> could you explain why the distribution is gaussian
Central limit theorem

>> and has a variance of 4/3n?
The variance of a difference of two independent variables (here: the two populations) is the sum of the individual variances.

a=\frac{1}{c \sqrt{2 \pi} }

b is the initial difference between two populations. c^2 = 4/3 n is the variance.

[>-)]

So is this distribution of the population of each nation, or of both of them combined, or something else?

[mfb]

With 4/3n, it is the distribution of the difference.

The distribution of the population of a single state after n days (ignoring the first 3 weeks) is approximately

f(x)=\sqrt{\frac{3}{4 \pi n}} \exp\left(-\frac {3}{4n}(x-6n)^2\right)

[>-)]

by 'exp', do you mean e^(everything in the parentheses)

[gmalivuk]

Yes.

[>-)]

Ok.

So i plugged in n as 120 (days) into this formula

f(x)=\sqrt{\frac{3}{4 \pi n}} \exp\left(-\frac {3}{4n}(x-6n)^2\right)

and got the normal curve.

The expected amount from the expected value of 720 is sqrt(2n/3), or sqrt(80). However, there seems to be about a 63% chance of being within sqrt(80) of the expected value and only about 37% of being outside.

[gmalivuk]

There's no reason to expect the median and the mean to be the same.

[>-)]

Which one is the mean and which one is the median?

[gmalivuk]

The mean is expected value. The median is the value where 50% of results fall to either side.

[>-)]

1st attachment is what i meant about the expected value being off what i expected, because i don't really understand what you mean about the median.

2nd one, does it make sense?

[gmalivuk]

Those curves look approximately correct, yeah. And both of those bell curves will continue to widen as time goes on, to the point where they almost entirely overlap.

[>-)]

Since the probability of a newer nation overtaking a larger one must always be less than 50%, won't they overlap halfway at most?
But then two nations starting at the same time would have 100% chance of being larger than the other, which makes no sense?

So is the probability of a nation overtaking another one 1/2 the area of the interlap?

[gmalivuk]

I think so, yeah. After all, if two nations had exactly identical probability distributions, there'd be 100% overlap but still only a 50% chance of nation A being bigger than nation B, because by symmetry the other 50% of the time we'd expect B to be bigger than A.

(Note that being able to simply divide that area by two is only because they are independent distributions with identical variance, only differing in expected value. If one was more spread out than the other, or a different shape entirely, you wouldn't get away with anything that simple.)

[>-)]

So a nation with a population of 900 million and a nation with a population of 950 million have a different shape? So i can't divide by two? What do i divide by then

[gmalivuk]

No, the way your problem works, they have the same shape (as long as you're comparing both nations the same number of days in the future, at least). I was just commenting that, in general, it's not as simple as it is in this case.

[mfb]

Are you sure that it is a simple division by 2 for the normal distribution? That would still be a remarkable formula, which is far from obvious.
If there is a simple connection, I would expect something like a quadratic dependence.

[gmalivuk]

Are you sure that it is a simple division by 2 for the normal distribution?

Nope. Hence the "I think so". I didn't actually do any math to back it up, it just seemed reasonable at first glance.

[>-)]

To calculate the area of the overlapping region would this be correct. ('b' is the population of smaller nation and 'a' is the population of larger nation)

((int sqrt(3/(4*pi*a))*e^(-3/(4*a)(x-6a)^2) from -infinity to sqrt(3/(4*pi*a))*e^(-3/(4*a)(x-6a)^2)=sqrt(3/(4*pi*b))*e^(-3/(4*b)(x-6b)^2))+(int sqrt(3/(4*pi*b))*e^(-3/(4*b)(x-6b)^2) from sqrt(3/(4*pi*a))*e^(-3/(4*a)(x-6a)^2)=sqrt(3/(4*pi*b))*e^(-3/(4*b)(x-6b)^2) to infinity))

(divided by 2 in the end to get the chance).

[mfb]

You don't expect anyone to read this, do you?

The probability that nation 1 is smaller than 2 is

P=\int_{-\infty}^{+\infty} dx G(x,\mu_1,\sigma_1) \int_x^{+\infty} dy G(y,\mu_2,\sigma_2)

with

G(x,\mu,\sigma)=\frac{1}{\sigma \sqrt{2 \pi}} \exp\left(\frac{(x-\mu)^2}{2 \sigma^2}\right)

where \mu_1=6n_1 and \sigma_1=\frac{2}{3}n_1 are the mean and standard deviation for nation 1 after n₁ days (equivalent for nation 2) and \exp(x)=e^x.

[>-)]

I don't see what you did there.

the integral of an equation from a to b, would be the area of the equation between it and the x-axis from x=a to x=b?

So if i split the triangle shaped region in two, to calculate the area of the left side is

int (

\sqrt{\frac{3}{4 \pi a}} \exp\left(-\frac {3}{4b}(x-6a)^2\right)

dx)
from -infinity to the intersection of the two distributions

and the area of right is

int (

\sqrt{\frac{3}{4 \pi b}} \exp\left(-\frac {3}{4b}(x-6b)^2\right)

dx)
from the intersection of the two distributions to infinity

and the intersection of the two distributions is
sqrt(3/(4*pi*a))*e^(-3/(4*a)(x-6a)^2)=sqrt(3/(4*pi*b))*e^(-3/(4*b)(x-6b)^2)
or
the two equations at the bottom of
http://www.wolframalpha.com/input/?i=sq ... %29%5E2%29

[gmalivuk]

By the way, you should stop using sqrt(2n/3) as though it's exact, because

in which case the expected difference from "origin" is sqrt(2n/3)?

On that order, anyway. As in the simpler case, there's probably a constant term on top of that, but it doesn't change the fact that the expected distance grows without bound.

I only provided that specific number as an argument that the expected distance grows without bound. It isn't correct to use in precise calculations. But in general, the expected value of the square of something is *not* the square of the expected value of that thing. In fact, the difference between these two values is the variance, which is definitely not zero in this case.

Here's a detailed proof that the expected value of the square of the distance is 2n/3, mostly to satisfy myself that it's true since I'm not confident of my original explanation:

Spoiler:

After n steps, there are 3^n equally likely distinct possible paths (made up of sequences of -1, 0, and +1). A path p has final position f(p) (note that many different paths can have the same final position, because the sequence -1 0 +1 ends at the same place as +1 -1 0, and so on).

Let S(n) be the sum of all the f(p)^2 after n steps. Then after n+1 steps, each element x^2 (where x is one of the f(p)s) in this sum is replaced by (x-1)^2+x^2+(x+1)^2, because each path can be continued by subtracting 1, staying the same, or adding 1. This is 3x^2+2, and since it's true for all paths, the sum after n+1 steps is 3*S(n)+2*3^n (since there's a 2 added for each of the 3^n paths included in S(n).) If S(n) = 2n*3^(n-1), then
$$S(n+1)=3(2n3^{n-1})+2(3^n)=2n3^n+2(3^n)=2(n+1)3^n$$

Because it's clearly true for n=0 that S(0) = 0 = 2*0*3^(0-1), it is true by induction that the sum of the squares of the endpoints of all possible paths after n steps is \(2n3^{n-1}\). Then the expected value is this divided by 3^n, to get 2n/3.

So yes, the expected value of the square of the distance after n steps is 2n/3, but this does *not* mean that the expected value of the distance itself is sqrt(2n/3).

[mfb]

@>-): Forget about the triangle. It does not have a useful meaning.
For each point in one distribution, you need the area of the other distribution larger (or smaller) than the corresponding value.

Here's a detailed proof that the expected value of the square of the distance is 2n/3

Which is the variance, and therefore everything is fine. The expected absolute difference from the mean value is not used anywhere.

[gmalivuk]

But it is the value @>-) wanted in the first posts.

[>-)]

Yes, i want the probability that a smaller nation that starts 'n' days earlier or has 'm' million less people than a larger/older nation will catch up and over take the larger/older nation after 'x' days. If the first curve shows the distribution of the possible populations the smaller nation could have, and it's total area is one; the second curve shows the distribution of the possible populations the larger nation could have, and it's total area is also one, then doesn't the area of the triangle in between show the area of the younger nation having a larger population than the older one? Except divided by two or something.

[gmalivuk]

Yes, i want the probability that a smaller nation that starts 'n' days earlier or has 'm' million less people than a larger/older nation will catch up and over take the larger/older nation after 'x' days.

In that case, there's no reason to worry about the expected absolute difference, like you asked about in the first post. It is indeed sufficient to note that the variance after x days is (2/3)x, because the distribution approaches Gaussian and so knowing the mean and variance is sufficient to give you tons of useful information about it.

If the first curve shows the distribution of the possible populations the smaller nation could have, and it's total area is one; the second curve shows the distribution of the possible populations the larger nation could have, and it's total area is also one, then doesn't the area of the triangle in between show the area of the younger nation having a larger population than the older one? Except divided by two or something.

No. As mfb said before, it's more complicated than that.

Suppose you have two nations, and the distributions of population after n days are A and B, where A has mean a and B has mean b and both have variance (2/3)n. Assume A is the distribution for the one that starts out smaller (and so a < b). If n is reasonably large, A and B are approximately normally distributed, and by asking whether the smaller nation overtakes the larger we ask when A > B or, equivalently, when A - B is positive. The difference in their populations, C = A - B, is also normally distributed, with mean a - b and variance (4/3) n (because in general xA + yB will have mean xa + yb and variance x^2(variance of A) + y^2(variance of b) for all real numbers x and y). Integrate this new distribution from 0 to infinity to find the probability of the smaller nation overtaking the larger one after n days.

For example, assume a = 100 and b = 110 and n = 21, so the variance of A and B are both 14. Then the likelihood of the smaller nation overtaking the larger one after these 3 weeks is the integral from 0 to infinity of the normal distribution with mean a - b = -10 and variance 28, or about 2.94%

The triangle where the distributions overlap is symmetrical, so if we want half of it, we can just integrate one of the distributions from the peak of the triangle (which happens halfway between a and b) to infinity or -infinity, depending on which one we pick. So, in this case, half the area of overlap is the integral from 105 to infinity of distribution A, or about 9.07%.