Register to reply

Unable to find the correct combination / permutation rule for my statistics project

Share this thread:
eveellence
#1
Dec26-12, 11:23 PM
P: 7
This is NOT homework. This is a personal project I am working on.

First and foremost, THANK YOU in advance for helping me with my statistics project that I have been unable to solve on my own or through the help of my statistics book and google.

I am working on an excel spreadsheet for use with the game Eve Online. I will give you a bit of background on what this involves below:

A player owned starbase out in space allows its owner to place various defensive modules around its perimeter. These modules randomly target enemy ships on the battlefield, applying various detrimental effects to them.

INITIAL GOAL: To find average number of unique enemy ships targeted at any given time.

The spreadsheet will allow the user to input the number of enemy ships on the battlefield as well as the number of defensive modules present. It will need to use this information to fulfill my initial goal. Let me illustrate with an example:

3 Ships on battlefield 3 modules on battlefield

I have found a way I can find the total number of available combinations by the following formula: (ships on battlefield)^(modules on battlefield). My logic behind this is from viewpoint of the module: one module has t potential targets (3 in this case) and since there are m modules, you multiply each set of potential choices together (3 in this case) which is 3^3 = 27 total combinations (which agrees with my testing results of manually listing all of the combinations).

I need to find the average number of UNIQUE ships targeted on the battlefield. This means if module 1, 2 and 3 are all targeting ship 1, this only counts as 1 unique ship targeted. If module 1,2 and 3 are all targeting different ships I now have 3 unique ships targeted.

My aim (correct me if i'm wrong, or if this is a flawed approach) in finding the average number of unique ships targeted at any given time is by finding the 'expected value' of the discrete random variable. i.e., make the random variable x = ship number (in this case ship #1, ship #2 and ship#3, or more simply 1, 2 and 3). Then, multiply each possible value of x by its probability p(x), and then sum this product over all possible values of x.

So, we have 1*p(x) + 2*p(x) + 3*p(x) = E(x), or average unique ships targeted. For this illustration, I have manually found the probabilities by listing all combinations and counting the number of combinations that fulfill each state as follows (refer to screenshot for how I did this):



Total combinations available: 27
1 Unique ship targeted: 3 = 3/27 = 1/9
2 Unique ships targeted: 18 = 18/27 = 2/3
3 Unique ships targeted: 6 = 6/27 = 2/9

So, plugging these probabilities into the above equation, we have:

1*(1/9) + 2*(2/3) + 3*(2/9) = E(x) = 2.111 ships targeted on average.

This is great, however, I have yet to find (outside of manually listing all available combinations and counting the ones that fulfill my criteria) a way to find the probability for x ships targeted, of which the above formula requires to work properly. I know it will involve using combinatorial / permutation counting rules which use factorials but I have been unable to find one that fits my requirements.

I think the main difficulty of finding a suitable counting rule to isolate the number of possibilites which would result in x number of unique ships targeted arises from the modules' ability to target a ship which is already targeted by another module. For instance, if I just wanted to find all the different combinations of selecting 2 ships from the 3 available, I would use 3^2 which = 9 but as you can see above, it is actually 18 so this cant be right. Likewise, if I use N!/(N-n)! I get = 6, still not 18. I try N!/n!(N-n)! and get = 3... still not 18.

Most likely this will involve using multiple combination and / or permutation counting rules working together in a certain way to achieve my goal, however I am just not experienced enough to figure this out. Any help is much appreciated!

After we tackle this part of my goal, I will post the next goal for this project and perhaps we can take a stab at that as well :)
Phys.Org News Partner Science news on Phys.org
New type of solar concentrator desn't block the view
Researchers demonstrate ultra low-field nuclear magnetic resonance using Earth's magnetic field
Asian inventions dominate energy storage systems
mfb
#2
Dec27-12, 08:15 AM
Mentor
P: 11,815
Let S be the number of ships, and D be the number of defensive modules.

If we look at ways to distribute D shots (independent of their source) over S targets, we have a total of (D+S-1 choose S-1) different combinations (multiset counting).

How many ways are there to target exactly N ships?
We have (S choose N) ways to choose N ships to get targeted.
For each of this combination: Every targeted ship needs at least one shot (otherwise it is not targeted), so we have D-N shots to distribute as multiple hits on N ships. With the same logic as above, this gives (D-N+N-1 choose N-1) = (D-1 choose N-1) options.

Putting everything together, for ##D \geq N \leq S##, we have
$$P(N)_{D,S}=\frac{{S \choose N}{D-1 \choose N-1}}{{D+S-1 \choose S-1}} = \frac{N! (S-N)! (N-1)! (D-N)! (D+S-1)!}{S! (D-1)! (S-1)! D!} = \frac{{D \choose N}{S-1 \choose N-1}}{{D+S-1 \choose S}}$$
Two different ways to write it, but nothing to simplify.


Edit: Ah, right. If you just care about the expectation value, awkward's approach is better.
awkward
#3
Dec27-12, 08:17 AM
P: 327
Hi eveellence,

OK, if I understand your question correctly, there are m modules (shooters) and t ships (targets), each module selects a single ship independently and at random, and you want to know the expected number of distinct ships selected as targets.

Let
[tex] X_i = \begin{cases} 1 &\text{if ship i is selected as a target}\\ 0 &\text{otherwise.} \end{cases} [/tex]
for [itex]i = 1, 2, 3, \dots t[/itex]

A ship is not selected as a target if all the modules select other ships. So
[tex]\Pr(X_i = 0) = \left(1 - \frac{1}{t} \right)^m[/tex]
and
[tex]\Pr(X_i = 1) = 1- \left(1 - \frac{1}{t} \right)^m[/tex]
so
[tex]E(X_i) = 1- \left(1 - \frac{1}{t} \right)^m[/tex]

Then the expected number of distinct ships selected as targets is
[tex]E(\sum_{i=1}^t X_i) = \sum_{i=1}^t E(X_i) = t \left[ 1- \left(1 - \frac{1}{t} \right)^m \right] [/tex]

Here we have used the theorem that E(X+Y) = E(X) + E(Y). It's important to realize that this theorem holds even if X and Y are not independent. That's good for us here, because the [itex]X_i[/itex]'s are not independent.

eveellence
#4
Dec30-12, 07:06 PM
P: 7
Unable to find the correct combination / permutation rule for my statistics project

Quote Quote by awkward View Post
Then the expected number of distinct ships selected as targets is
[tex]E(\sum_{i=1}^t X_i) = \sum_{i=1}^t E(X_i) = t \left[ 1- \left(1 - \frac{1}{t} \right)^m \right] [/tex]
WOW. This is exactly what I needed, thank you so much! Such a simple and elegant solution too! I wish there was a way I could +1 you :) Also, thank you to mfb for helping as well! I am sorry I haven't had time until now to thank you all for your much appreciated help with this one, I was out of town. In a little bit i'll post the next hurdle that is in front of me for this project.
eveellence
#5
Dec30-12, 11:29 PM
P: 7
Ok, now for the next hurdle in my project. Now that I know the average expected number of distinct ships that will be targeted, I now need to look deeper into how a specific type of module on the battlefield will affect its

targeted ship. In order for you to understand this a bit better, lets briefly discus the module in question.

It is the Electronic Counter Measures, or ECM module. Its purpose is to 'jam' the targeted ship, preventing the ship from locking any target (and thus disabling the ship from its ability to do damage). The mechanics are

as follows:

1) It takes roughly 15s for the module to acquire target lock on an enemy ship. Call this t = lock time.

2) After locking, it performs 4 jamming attempt cycles, each 7.5s in length. If successful, the target is 'jammed' for 7.5s in duration. After the 4 cycles are performed, it automatically switches to a new, randomly acquired

target, as described in the original post. The probability calculation for a successful, or unsuccessful jam cycle on the module's target is found by dividing the jam strength of the module by the sensor strength of the

ship. This is where it gets interesting. For a 'racial' jammer (meaning the module has an increased chance against its target) the jam strength is 45. For a 'non-racial' jammer, the jam strength is 15.

So, for instance, for a racial jammer vs a ship of sensor strength 90, we have 45/90 = 50% chance of jam. Likewise, for non-racial vs. the same ship we have 15/90 = a ~ 16.67% chance for jam.

My overall goal here is to use the equation given by awkward above to find total number of distinct ships targeted, then find the % of time those ships are jammed, which will give me a total % of ships that, on average, are effectively removed from the battlefield given a certain number of racial jammers, non-racial jammers and enemy ships present.

So, my question here is this: How should I treat the two different types of ecm modules (racial, and non-racial) present in my calculations? Here are the different ways I see of doing this below, I am writing the complete equation which will accomplish my overall goal as stated above.
t = 10 = quantity of enemy targets
r = 10 = quantity of racial jamming modules
n = 10 = quantity of non-racial jamming modules
jr = 45 = jamming strength of racial jammer module
jn = 15 = jamming strength of non-racial jammer module
s = 90 = sensor strength of enemy ships
c = total cycle time (30 seconds in this case [7.5*4 = 30])
l = 15 = lock time (time for module to acquire target lock on enemy ship)

A) Treat the two ecm module types as the same for targeting purposes, but different in terms of probability of successful jam (by averaging the total jam strength across all the modules). For example:

[tex]\text{percent of ships jammed =}\left [ 1-\left ( 1-\frac{1}{t} \right )^{r+n} \right ]\frac{c\left (j_{r}r+j_{n}n \right )100}{s\left (r+n \right )\left ( c+l \right )}\text{ ---------->}\left [ 1-\left ( 1-\frac{1}{10} \right )^{10+10} \right ]\frac{30\left (45 \cdot10 +15 \cdot 10 \right )100}{90\left (10+10 \right )\left ( 30+15 \right )} \text{ = 19.52%}[/tex]

So, this tells me that 19.52% of all enemy ships will effectively be removed from the field (on average) with the presence of 10 enemy ships, 10 racial jammers, and 10 non-racial jammers.

*EDIT* I examined the above equation further and it was flawed. It was not factoring in the overlap of modules that were targeting more than one target. For instance, with 20 enemy ships, 40 racial and 40 non racial jammers, the equation tells me only 21.86% of ships would be jammed, which is obviously flawed since it should be much higher than that.

My logic in fixing this is as follows: Re-write the formula so it divides the total number of modules by number of distinct ships targeted, returning an average number of modules per targeted ship. This is then multiplied by the % of time each module can jam a target for (with the product limited to 100%), which results in (I believe) a much more accurate result.

Here is the modified equation below, followed by the simplified one:


[tex]\text{percent of ships jammed =}\left [ 1-\left ( 1-\frac{1}{t} \right )^{r+n} \right ]\cdot y[/tex]
[tex]y= \frac{c\left (j_{r}r+j_{n}n \right )100}{s\left (r+n \right )\left ( c+l \right )}\cdot
\frac{r+n}{t\left [ 1-\left ( 1-\frac{1}{t} \right )^{r+n} \right ]}[/tex]
[tex]\left \{ y|y\leq 1 \right \}[/tex]

I realize that the above equation simplifies to:

[tex]\frac{c\left ( j_{r}r+j_{n}n \right )100}{s\cdot t\left ( c+l \right )}[/tex] However, I must limit the above described y to 1 or less in order for everything to work properly. If you guys have any ideas on how to clean this up, or even if my logic is wrong let me know :)




The weaknesses in this method I see are:

1) I treat the 4 individual cycle times of 7.5 seconds each as a continuous time length. Correct me if i'm wrong, but I don't think this will affect the number i'm looking for at all.

2) I'm averaging the differences of jamming module strengths ( 45 vs. 15) across all of the jamming modules. I have a feeling this isn't the right way of doing this, so I will list the other idea I have below. *EDIT* I have since modeled the differences between the averaging method and individual method and it doesn't look like they are any different from each other, in providing the average % of ships effectively removed from the field, but please share your thoughts on this, I may not be looking at it correctly.



B) Treat the two ecm module types as completely separate for targeting and jam probability calculation. The main issue I see here is that the initial equation given by awkward for the effective number of distinct ships targeted will have to be changed somehow. This is because now there will be two groups of modules targeting the same ships.

What do you suggest the best way of going about this is? Thanks again for all your help!
mfb
#6
Dec31-12, 09:51 AM
Mentor
P: 11,815
You cannot add the modules like that I think. Use awkward's method for each individual step in the cycle instead:

The probability that a non-racial jammer not jams a ship in a specific attempt is ##(1-\frac{j_n}{st})##. The probability that any jammer jams a ship in a specific round is $$P=1-\left(1-\frac{j_n}{st}\right)^n \left(1-\frac{j_r}{st}\right)^r$$
50% of the time, no ship can be jammed - averaged over the full 30s-cycle, the ship has a jamming probability of ##P \frac{c-l}{c}=\frac{P}{2}##, which is the final result.
eveellence
#7
Jan2-13, 01:16 AM
P: 7
Quote Quote by mfb View Post
You cannot add the modules like that I think. Use awkward's method for each individual step in the cycle instead:

The probability that a non-racial jammer not jams a ship in a specific attempt is ##(1-\frac{j_n}{st})##. The probability that any jammer jams a ship in a specific round is $$P=1-\left(1-\frac{j_n}{st}\right)^n \left(1-\frac{j_r}{st}\right)^r$$
50% of the time, no ship can be jammed - averaged over the full 30s-cycle, the ship has a jamming probability of ##P \frac{c-l}{c}=\frac{P}{2}##, which is the final result.
Hi mfb, thanks for the reply! However, I am confused. Take for instance; the example of 10 enemy ships (t), with sensor strength 90 (s), 10 non-racial jammers present (n), with jamming strength 15 (jn), 10 racial jammers (r), with jamming strength 45 (jr). When these numbers are plugged in as follows: ##P=1-\left(1-\frac{15}{900}\right)^{10} \left(1-\frac{45}{900}\right)^{10}= 0## the result is zero % chance of jamming a ship? That can't be right.

Also, as far as 50% of the time, no ships can be jammed, well that is only if lock time is 15s (l). Lock time is variable depending on certain circumstances. It can be as high as 20 or as low as 12. So, how do you suggest working the ##P \frac{c-l}{c}=\frac{P}{2}## into the other equation above you gave?
mfb
#8
Jan2-13, 07:54 AM
Mentor
P: 11,815
I get ~49% with your values: WolframAlpha query

Is the lock time synchronized for all jammers? Is it predictable?
If yes/yes, just adjust c and l. If yes/no, take the average. If no/whatever, how does it work?
eveellence
#9
Jan2-13, 06:14 PM
P: 7
Quote Quote by mfb View Post
I get ~49% with your values: WolframAlpha query

Is the lock time synchronized for all jammers? Is it predictable?
If yes/yes, just adjust c and l. If yes/no, take the average. If no/whatever, how does it work?
I see it now, yes I get P = ~.49389 as well, my order of operations were off. You stated that P = 'The probability that any jammer jams a ship in a specific round'. Am I understanding correctly that P = the % of ships jammed in a specific round? For instance, in this instance since 10 ships are on the field, effectively 10*.49389 = 4.9389 ships jammed (on average)?

Lock time is not synchronized for all jammers, they all operate independently. It depends on the ship size (signature size) and the 'signature resolution' of the specific jammer's targeting system. I wont complicate things by listing those equations, but usually for these class of ships it comes out to being around 17-18s, however on much smaller ships it can be as high as 37s.

I see you listed: ##P \frac{c-l}{c}=\frac{P}{2}## So, does this mean that I take my P result above and multiply it by ##\frac{c-l}{c}##? If I did that, I would come up with (in this case) .49389 / 2 = ~.2469 which just doesn't seem right, seems too low.

For instance, using a lower number of ships and modules, say 3 ships and 3 racial modules, 0 non-racial modules, so that we can logically reason it out manually, I plug in the numbers and come out with P= .4213 and divide that by 2 = ~.21065 as the proportion of ships on the field jammed. This can't possibly be correct, as seen through the following reasoning:

Using awkward's equation, we find that there would be, on average, ##3 \left[ 1- \left(1 - \frac{1}{3} \right)^3 \right]= 2.11## distinct ships targeted. Lets just round it off to 2. Lets say jammer #1 is on ship A and jammer #2 is on ship B. Each jammer jams its targeted ship for: ##\frac{c\left (j_{r}r\right )}{s\left (r\right )\left ( c+l \right )}= \frac{30\left (45\cdot 3\right )}{90\left (3\right )\left ( 30+15 \right )}= \frac{1}{3}## of the time. Thus far, we have ##\frac{1}{3}+\frac{1}{3}=\frac{2}{3}## jammed out of a total of ##\frac{9}{3}## which gives us: ##\frac{2}{3}\cdot \frac{3}{9}= \frac{2}{9}= 22.22 \text { percent}## jammed. Note that we haven't even considered jammer #3, which will no doubt add significantly to the total % of ships jammed. This is why the ~.21065, cannot possibly be correct for 3 ships and 3 racial jammers.

With the third jammer added to our logical evaluation: ##\frac{3}{3}\cdot \frac{3}{9}= \frac{1}{3}= 33.33 \text { percent}## So, it should be fair to expect somewhere around 27-33% of ships on field to be jammed with 3 ships present, and 3 racial jammers.

Using the equation I proposed in my previous post, it comes out with: $$\text{percent ships jammed =}\left [ 1-\left ( 1-\frac{1}{t} \right )^{r+n} \right ]\cdot
\frac{c\left (j_{r}r+j_{n}n \right )100}{s\left (r+n \right )\left ( c+l \right )}\cdot
\frac{r+n}{t\left [ 1-\left ( 1-\frac{1}{t} \right )^{r+n} \right ]}\rightarrow \left [ 1-\left ( 1-\frac{1}{3} \right )^{3} \right ]\cdot
\frac{30\left (45\cdot 3 \right )100}{90\left (3 \right )\left ( 45 \right )}\cdot
\frac{3}{3\left [ 1-\left ( 1-\frac{1}{3} \right )^{3} \right ]}= 33.32\text{ percent}$$

It just seems like the logical reasoning makes sense with my above formula, or maybe i'm just still missing something?

As always, THANKS so much for your help thus far!
mfb
#10
Jan3-13, 09:37 AM
Mentor
P: 11,815
Quote Quote by eveellence View Post
I see it now, yes I get P = ~.49389 as well, my order of operations were off. You stated that P = 'The probability that any jammer jams a ship in a specific round'. Am I understanding correctly that P = the % of ships jammed in a specific round? For instance, in this instance since 10 ships are on the field, effectively 10*.49389 = 4.9389 ships jammed (on average)?
Right, but if lock time is not in sync we have to include this in the formula for the jammers.

$$P=1-\left(1-\frac{j_n(c-l)}{cst}\right)^n \left(1-\frac{j_r(c-l)}{cst}\right)^r$$

This assumes that for every moment in the battle, a fraction of (c-l)/c of the jammers tried to jam a ship in the last 7.5 seconds.


Considering your example with 3 ships and 3 jammers: Their chance to jam a ship is just 1/2, and they try to do so just 1/2 of the time. Even if they target 3 different ships, they can just maintain a fraction of 25% jammed ships (on average). If you remove one jammer from the analysis and assume that the other two target two different ships, this drops to 2/3*25% =~ 16%.

My old formula gives 21%, this is below 25% and takes into account that two or more jammers could try to jam the same target.
With independent locking times and the new formula, this increases to 23%.


With the third jammer added to our logical evaluation: ##\frac{3}{3}\cdot \frac{3}{9}= \frac{1}{3}= 33.33 \text { percent}## So, it should be fair to expect somewhere around 27-33% of ships on field to be jammed with 3 ships present, and 3 racial jammers.
If it would work like that, you would get 100% jamming with 9 jammers. Do you expect this?
Do you expect 111% with 10 jammers? ;)
eveellence
#11
Jan3-13, 07:25 PM
P: 7
Quote Quote by mfb View Post
Right, but if lock time is not in sync we have to include this in the formula for the jammers.

$$P=1-\left(1-\frac{j_n(c-l)}{cst}\right)^n \left(1-\frac{j_r(c-l)}{cst}\right)^r$$
Ok, I think I am starting to understand what you are saying, mfb. Please look at the screenshot below and let me know if I am seeing your thoughts correctly-

As you can see, the numbers I got are a few % off from what your equation provides, but this is probably because I rounded the first instance to 2 ships instead of 2.111, and the second instance to 3 ships instead of 2.92, is it not?

*EDIT* It looks like these illustrations I made and posted as screenshots are following the 'synced' viewpoint, but in actuality, the time 'holes' of un-jammable time, namely during (l) or lock time, will gradually be filled in, the more jamming modules are added. This is because while one jammer is acquiring target lock on a ship, another jammer could already be jamming that ship, thus filling that 'hole' of un-jammable time. I hope that makes sense.

Another question- for the equation you gave:

$$P=1-\left(1-\frac{j_n(c-l)}{cst}\right)^n \left(1-\frac{j_r(c-l)}{cst}\right)^r$$

I'll re-write it a little differently, which will help me ask my question:

$$P=1-\left(1-\frac{j_n}{s}\cdot \frac{\left(c-l \right )}{c}\cdot \frac{1}{t}\right)^n\left(1-\frac{j_r}{s}\cdot \frac{\left(c-l \right )}{c}\cdot \frac{1}{t}\right)^r$$

The part that defines the probability for a jammer to jam its target, namely the ##\frac{j_n}{s}## and ##\frac{j_r}{s}## parts, shouldn't these be limited to a maximum of 1? For instance, if jr = 45 and s = 25, then it would be 180% chance of jam, which doesn't make sense for over a 100% chance. Yet, when I plug those values into your formula for, say for instance the 3 ships and 3 racial jammers, 3 non racial jammers, I get a different P depending on the ship sensor strength (s) that I enter. For instance, I get P = .42 when s = 45 (this would be ##\frac{j_r}{s}\rightarrow \frac{45}{45}= 1##, yet I get P = .66 when s = 25 (##\frac{j_r}{s}\rightarrow \frac{45}{25}= 1.8##. I don't think P should change once jammer strength ##\geq## ship sensor strength, what do you think? Maybe i'm overlooking something as usual :P

Here are the screenshots for ship sensor strength of 45 (click here)

And the screenshots for ship sensor strength of 25 (click here)

Most of the time, ship sensor strength will actually be below the jamming strength of the module, so the probability of a jam will actually be 100% as long as the jamming module is targeting the ship. Should your formula be modified in any way to account for this? I am assuming that if ship sensor strength < jamming module strength, the new P will simply depend upon locking time and number of distinct ships targeted. Am I right?

Thanks again for your help and your patience as I try to wrap my mind around this!
mfb
#12
Jan4-13, 08:15 AM
Mentor
P: 11,815
Wait, we used two different cycle times here. I used 30s for the total cycle (which is wrong), I should have used c+l there instead.

Fixed, unsynched jammers:
$$P=1-\left(1-\frac{j_nc}{(c+l)st}\right)^n \left(1-\frac{j_rc}{(c+l)st}\right)^r$$
29.6% in your first example, 65% in your second.

Fixed, synched jammers:
$$P=\frac{c}{c+l}\left(1-\left(1-\frac{j_n}{st}\right)^n \left(1-\frac{j_r}{st}\right)^r\right)$$
28.1% in your first example, 53.7% in your second.

3 jammers for each ship is the ideal case - you don't have that every time. Consider (1,3,5) jammers, for example, where the jamming probability is significantly lower.

j/s should be limited by 1, right. If j can exceed s, include that limit there.
If different approaching ships have a different sensor strength, this formula can be evaluated for each individual ship type with the corresponding sensor strength.
eveellence
#13
Jan4-13, 04:38 PM
P: 7
Quote Quote by mfb View Post
Wait, we used two different cycle times here. I used 30s for the total cycle (which is wrong), I should have used c+l there instead.

Fixed, unsynched jammers:
$$P=1-\left(1-\frac{j_nc}{(c+l)st}\right)^n \left(1-\frac{j_rc}{(c+l)st}\right)^r$$
Excellent work, mfb! Yes, this seems to fix the issue that I was experiencing where as lock time approaches 30s, P approaches zero.

So if I understand correctly, after applying the appropriate limits, I should write the equation this way: $$P=1-\left(1-j_1\cdot \frac{c}{(c+1)t} \right )^n\left(1-j_2\cdot \frac{c}{(c+1)t} \right )^r\text{ }j_1= \frac{j_n}{s}\text{, }j_2= \frac{j_r}{s}\text{ }\left \{ j_1|j_1\leq 1 \right \}\text{,}\left \{ j_2|j_2\leq 1 \right \}$$

Thanks again mfb! +100


Register to reply

Related Discussions
Permutation and combination Calculus & Beyond Homework 4
Permutation and Combination Calculus & Beyond Homework 5
Permutation or combination Precalculus Mathematics Homework 2
Combination and Permutation Precalculus Mathematics Homework 6
Committee combination math problem Introductory Physics Homework 2