How to generate a distribution of k shots on n enemies

Question

I am developing a space combat game in Java as part of an ongoing effort to learn the language. In a battle, I have k ships firing their guns at a fleet of n of their nefarious enemies. Depending on how many of their enemies get hit by how many of the shots, (each ship fires one shot which hits one enemy), some will be damaged and some destroyed. I want to figure out how many enemies were hit once, how many were hit twice and so on, so that at the end I have a table that looks something like this, for 100 shots fired:

Number of hits | Number of occurences | Total shots
----------------------------------------------------
       1       |        30            |      30
       2       |        12            |      24
       3       |         4            |      12
       4       |         7            |      28
       5       |         1            |       5

Obviously, I can brute force this for small numbers of shots and enemies by randomly placing each shot on an enemy and then counting how many times each got shot at the end. This method, however, will be very impractical if I've got three million intrepid heroes firing on a swarm of ten million enemies.

Ideally, what I'd like is a way to generate a distribution of how many enemies are likely to be hit by exactly some number of shots. I could then use a random number generator to pick a point on that distribution, and then repeat this process, increasing the number of hits each time, until approximately all shots are accounted for. Is there a general statistical distribution / way of estimating approximately how many enemies get hit by how many shots?

I've been trying to work out something from the birthday problem to figure out the probability of how many birthdays are shared by exactly some number of people, but have not made any significant progress.

I will be implementing this in Java.

EDIT: I found a simplification of this that may be easier to solve: what's the distribution of probabilities that n enemies are not hit at all? I.e. whats the probability that zero are not hit, one is not hit, two are not hit, etc.

It's a similar problem, (ok, the same problem but with a simplification), but seems like it might be easier to solve, and would let me generate the full distribution in a couple of iterations.

Answer 1

Figured out a way of solving this, and finally got around to writing it up in Java. This gives an exact solution for computing the probability of m ships not being hit given k ships and n shots. It is, however, quite computationally expensive. First, a summary of what I did:

The proability is equal to the total number of ways to shoot the ships with exactly m not hit divided by the total number of ways to shoot ships.

P = m_misses / total

Total is k^n, since each shot can hit one of k ships.

To get the numerator, start with nCr(k,m). This is the number of ways of choosing m ships to not be hit. This multiplied by the number of ways of hitting k-m ships without missing any is the total probability.

     nCr(k,m)*(k-m_noMiss)
 P = ---------------------
             k^n

Now to calculate the second term in the numerator. This is the sum across all distributions of shots of how many ways there are for a certain shot distribution to happen. For example, if 2 ships are hit by 3 bullets, and each ship is hit at least once, they can be hit in the following ways:

100
010
001
110
101
011

The shot distributions are equal to the length k-m compositions of k. In this case, we would have [2,1] and [1,2], the length 2 compositions of 3.

For the first composition, [2,1], we can calculate the numbers of ways of generating this by choosing 2 out of the 3 shots to hit the first ship, and then 1 out of the remaining 1 shots to hit the second, i.e. nCr(3,2) * nCr(1,1). Note that we can simplify this to 3!/(2!*1!). This pattern applies to all shot patters, so the number of ways that a certain pattern, p, can occur can be written as n!/prodSum(j=1,k-m,p_j!), in which the notation indicates the product sum from 1 to k-m, j is an index, and p_j represents the jth term in p.

If we define P as the set of all length k-m compositions of n, the probability of m ships not being hit is then:

     nCr(k,m)*sum(p is an element of P, n!/prodSum(j=1,k-m,p_j!))
 P = --------------------------------------------------------------
                                 k^n

The notation is a bit sloppy since there's not way of putting equations of math symbols into SO, but that's the gist of it.

That being said, this method is horribly inefficient, but I can't seem to find a better one. If someone can simplify this, by all means post your method! I'm curious as to how it can be done.

And the java code for doing this:

import java.util.ArrayList;
import java.util.Arrays;
import org.apache.commons.math3.util.ArithmeticUtils;

class Prob{
    public boolean listsEqual(Integer[] integers, Integer[] rootComp){
        if(integers.length != rootComp.length){
            return false;
        }
        for (int i = 0; i < integers.length; i++){
            if(integers[i] != rootComp[i]){return false;};
        }       
        return true;
    }

    public Integer[] firstComp(int base, int length){
        Integer[] comp = new Integer[length];
        Arrays.fill(comp, 1);
        comp[0] = base - length + 1;
        return comp;        
    }

    public Integer[][] enumerateComps(int base, int length){
        //Provides all compositions of base of size length

        if(length > base){return null;};
        Integer[] rootComp = firstComp(base, length);
        ArrayList<Integer[]> compsArray = new ArrayList<Integer[]>();

        do {
            compsArray.add(rootComp);
            rootComp = makeNextComp(rootComp);
        } while(!listsEqual(compsArray.get(compsArray.size() - 1), rootComp));

        Integer[][] newArray = new Integer[compsArray.size()][length];

        int i = 0;
        for (Integer[] comp : compsArray){
            newArray[i] = comp;
            i++;
        }

        return newArray;
    }

    public double getProb(int k, int n, int m){
        //k = # of bins
        //n = number of objects
        //m = number of empty bins

        //First generate list of length k-m compositions of n

        if((n < (k-m)) || (m >= k)){
            return 0;
        }

        int[] comp = new int[n-1];

        Arrays.fill(comp, 1);

        comp[0] = n - (k-m) + 1;

        //Comp is now the first 
        Integer[][] L = enumerateComps(n, k-m);

        double num = 0;
        double den = Math.pow(k, n);
        double prodSum;
        int remainder;

        for(Integer[] thisComp : L){
            remainder = n;
            prodSum = 1;
            for(Integer thisVal : thisComp){
                prodSum = prodSum * ArithmeticUtils.binomialCoefficient(remainder, thisVal);

                remainder -= thisVal;
            }

            num += prodSum;
        }

        return num * ArithmeticUtils.binomialCoefficient(k, m) / den;
    }

    public Integer[] makeNextComp(Integer[] rootComp){
        Integer[] comp = rootComp.clone();

        int i = comp.length - 1;
        int lastVal = comp[i];
        i--;

        for(; i >=0 ; i--){
            if (comp[i] != 1){
                //Subtract 1 from comp[i]
                comp[i] -= 1;
                i++;
                comp[i] = lastVal + 1;
                i++;
                for(;i < comp.length; i++){
                    comp[i] = 1;
                };
                return comp;                
            }
        }
        return comp;
    }
}


public class numbersTest {
    public static void main(String[] args){
        //System.out.println(ArithmeticUtils.binomialCoefficient(100,50));
        Prob getProbs = new Prob();

        Integer k = 10; //ships
        Integer n = 10; //shots
        Integer m = 4; //unscathed

        double myProb = getProbs.getProb(k,n,m);

        System.out.printf("Probability of %s ships,  %s hits, and %s unscathed: %s",k,n,m,myProb);
    }
}

Answer 2

I'm assuming that each shot has probability h to hit any bad ship. If h = 0, all shots will miss. If h = 1, all shots will hit something.

Now, let's say you shoot b bullets. The expected value of ships hit is simply Hs = h * b, but these are not unique ships hit.

So we have a list of ships that is Hs long. The chance of any specific enemy ship being hit given N enemy ships is 1/N. Therefore, the chance to be in the first k slots but no the other slots is

(1/N)^k * (1-1/N)^(Hs-k)  

Note that this is Marko Topolnik's answer. The problem is that this is a specific ship being in the FIRST k slots, as opposed to being in any combination of k slots. We must modify this by taking into the account the number of combinations of k slots in Hs total slots:

(Hs choose k) * (1/N)^k * (1-1/N)^(Hs-k)

Now we have the chance of a specific ship being in k slots. Well, now we need to consider the entire fleet of N ships:

(Hs choose k) * (1/N)^k * (1-1/N)^(Hs-k) * N

This expression represents the expected number of ships being hit k times within an N sized fleet that was hit with Hs shots in a uniform distribution.

Numerical Sanity Check:

Let's say two bullets hit (Hs=2) and we have two enemy ships (N=2). Assign each ship a binary ID, and let's enumerate the possible hit lists.

00 (ship 0 hit twice)
01
10
11

The number of ships hit once is:

(2 choose 1) * (1/2)^1 * (1-1/2)^(2-1) * 2 = 1

The number of ships hit twice is:

(2 choose 2) * (1/2)^2 * (1-1/2)^(2-2) * 2 = 0.5

To complete the sanity check, we need to make sure our total number of hits equals Hs. Every ship hit twice takes 2 bullets, and every ship hit once takes one bullet:

1*1 + 0.5*2 = 2 == Hs  **TRUE**

One more quick example with Hs=3 and N=2:

(3 choose 1) * (1/2)^1 * (1-1/2)^(3-1) * 2
3 * 0.5 * 0.25 * 2 = 0.75

(3 choose 2) * (1/2)^2 * (1-1/2)^(3-2) * 2
3 * 0.5^2 * 0.5 * 2 = 0.75

(3 choose 3) * (1/2)^3 * (1-1/2)^(3-3) * 2
1 * 0.5^3 * 1 * 2 = 0.25

0.75 + 0.75*2 + 0.25*3 = 3 == Hs  **TRUE**

Answer 3

If you have S ships and fire A shots at them, each individual ship's number of hits will follow a binominal distribution where p = 1/S and n = A:

http://en.wikipedia.org/wiki/Binomial_distribution

You can query this distribution and ask:

• How likely is it for a ship to be hit 0 times?
• How likely is it for a ship to be hit 1 time?
• How likely is it for a ship to be hit 2 times?
• How likely is it for a ship to be hit (max health) or more times? (Hint: Just subtract 1.0 from everything below)

and multiply these by the number of ships, S, to get the number of ships that you expect to be hit 0, 1, 2, 3, etc times. However, as this is an expectation not a randomly rolled result, battles will go exactly the same way every time.

If you have a low number of ships yet high number of shots, you can roll the binominal distribution once per ship. OR if you have a low number of shots yet high number of ships, you can randomly place each shot. I haven't yet thought of a cool way to get the random distribution (or a random approximation thereof) of high number of shots AND high number of shots, but it would be awesome to find out one :)

Answer 4

You should take a look at multinomial distribution, constraining it to the case where all p_i are equal to 1/k (be careful to note that the Wikipedia article swaps the meaning of your k and n).

---

Previous attempt at answer

Maybe an approach like the following will be fruitful:

1. the probability that a particular ship is hit by a particular shot is 1/n;
2. the probability that a given ship is hit exactly once after k shots: h₁ = 1/n (1-1/n)^k-1;
3. as above, but exactly twice: h₂ = (1/n)² (1-1/n)^k-2, and so on;
4. expected number of ships hit exactly once: n h₁ and so on.