What is the average size of an island?

Question

If you have a square grid, and each square* has probability $n$ of being ground. If the other squares are water, what is the average area of an island? If $n$ is small then the average island would have an area of about $1$. With large values of $n$, the average size of islands is really big. Also diagonally touching squares don’t count as being the same island. Unless of course they connect somewhere else. *Each with an area of $1$.

Answer 1

I did an experiment with some Java code.

• I have checked all probabilities, starting from 5% in steps of 2.5% up to 100%.
• Each experiment is repeated 500 times before the average island size is calculated.
• The size of the "sea" is $50\times50$

Here are the results:

$$ \begin{array}{l|l} \text{Probability} & \text{Average Island Size} \\ 0.050000 & 1.108420 \\ 0.075000 & 1.171769 \\ 0.100000 & 1.239889 \\ 0.125000 & 1.322296 \\ 0.150000 & 1.409073 \\ 0.175000 & 1.509786 \\ 0.200000 & 1.627313 \\ 0.225000 & 1.756252 \\ 0.250000 & 1.904399 \\ 0.275000 & 2.080445 \\ 0.300000 & 2.295080 \\ 0.325000 & 2.528017 \\ 0.350000 & 2.823988 \\ 0.375000 & 3.180992 \\ 0.400000 & 3.618721 \\ 0.425000 & 4.142728 \\ 0.450000 & 4.827669 \\ 0.475000 & 5.725215 \\ 0.500000 & 6.911376 \\ 0.525000 & 8.596760 \\ 0.550000 & 10.841804 \\ 0.575000 & 14.148635 \\ 0.600000 & 18.840807 \\ 0.625000 & 26.346250 \\ 0.650000 & 35.965670 \\ 0.675000 & 50.930806 \\ 0.700000 & 73.566788 \\ 0.725000 & 106.523051 \\ 0.750000 & 161.343357 \\ 0.775000 & 242.921195 \\ 0.800000 & 383.797845 \\ 0.825000 & 613.803805 \\ 0.850000 & 1026.555037 \\ 0.875000 & 1425.019748 \\ 0.900000 & 1789.621500 \\ 0.925000 & 2132.510333 \\ 0.950000 & 2316.020000 \\ 0.975000 & 2427.573000 \\ 1.000000 & 2500.000000 \end{array} $$

It seems that the average size of the island starts to grow rapidly for $p\gt0.65$.

And here is the code if you want to check it for correctness:

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;

public class IslandMap {
    public static final int SEA_SIZE = 100;
    public static final int NUM_EXPERIMENTS = 500;
    public static final double PROBABILITY_INCREMENT_PCT = 2.5;
    public static final double START_PROBABILITY_PCT = 5.0; 

    private static Random rnd = new Random(System.currentTimeMillis());
    private List<Island> islands;
    private double probability;

    public static void main(String[] args) {
        System.out.println("Probability,AvgSize"); 
        for (double prob = START_PROBABILITY_PCT; prob <= 100D; prob += PROBABILITY_INCREMENT_PCT) {
            Stats stats = new Stats();
            for (int i = 0; i < NUM_EXPERIMENTS; i++) {
                IslandMap map = new IslandMap(prob / 100D);
                map.createIslands();
                while (map.mergeIslands()) {
                    // NOP
                }
                double[] results = map.getStats();
                stats.accum(results);
            }
            String msg = String.format("%f,%f", prob / 100D, stats.getAvgAvg());
            System.out.println(msg);
        }
    }

    IslandMap(double probability) {
        this.probability = probability;
    }

    List<Island> createIslands() {
        islands = new LinkedList<Island>();
        for (int i = 0; i < SEA_SIZE; i++) {
            for (int j = 0; j < SEA_SIZE; j++) {
                if (rnd.nextDouble() <= probability) {
                    Square s = new Square(i, j);
                    islands.add(new Island(s));
                }
            }
        }
        return islands;
    }

    boolean contains(Square s) {
        for (Island island : islands) {
            if (island.contains(s)) {
                return true;
            }
        }
        return false;
    }

    boolean mergeIslands() {
        boolean changed = false;
        int i = 0;
        while (i < islands.size() - 1) {
            int j = i + 1;
            while (j < islands.size()) {
                boolean joined = islands.get(i).merge(islands.get(j));
                if (joined) {
                    changed = true;
                    islands.remove(j);
                } else {
                    j++;
                }
            }
            i++;
        }
        return changed;
    }

    double[] getStats() {
        int minSize = SEA_SIZE * SEA_SIZE;
        int maxSize = 0;
        int totalSize = 0;
        for (Island island : islands) {
            minSize = Math.min(minSize, island.size());
            maxSize = Math.max(maxSize, island.size());
            totalSize += island.size();
        }
        double avgSize = (double) totalSize / (double) islands.size();
        double[] result = new double[] { minSize, maxSize, avgSize };
        return result;
    }

}

class Island {
    private List<Square> squares = new ArrayList<Square>();

    Island(Square s) {
        squares.add(s);
    }

    boolean contains(Square s) {
        return squares.contains(s);
    }

    boolean merge(Island island) {
        for (Square s1 : squares) {
            for (Square s2 : island.squares) {
                if ((s1.x == s2.x && Math.abs(s1.y - s2.y) == 1) || (s1.y == s2.y && Math.abs(s1.x - s2.x) == 1)) {
                    squares.addAll(island.squares);
                    return true;
                }
            }
        }
        return false;
    }

    int size() {
        return squares.size();
    }

    @Override
    public String toString() {
        StringBuffer b = new StringBuffer("");
        b.append("SIZE: ").append(size());
        for (Square s : squares) {
            b.append(": (").append(s.x).append(",").append(s.y).append(") ");
        }
        return b.toString();
    }

}

class Square {
    int x, y;

    Square(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public boolean equals(Object obj) {
        // TODO Auto-generated method stub
        Square s = (Square) obj;
        return x == s.x && y == s.y;
    }
}

class Stats {
    private double[] stats = new double[3];
    private int count;

    void accum(double[] stats) {
        this.stats[0] += stats[0];
        this.stats[1] += stats[1];
        this.stats[2] += stats[2];
        count++;
    }

    double getAvgMin() {
        return stats[0] / count;
    }

    double getAvgMax() {
        return stats[1] / count;
    }

    double getAvgAvg() {
        return stats[2] / count;
    }
}

I'm currently running the same simulation for the sea of size $100\times100$. It will take much, much more time but I still expect to get the curve of the same shape.