It is true that prime numbers do become rare as the numbers get large. The celebrated Prime Number Theorem says that the probability for a large number of size around N to be prime is about 1/(ln N). (Here, (ln N) is the logarithm of N in base e.) Indeed, as N gets larger, the probability of a number about that size being prime gets smaller. The proof of this theorem is very complicated, but the interested mathematician can find it here.
Yet as the room numbers get large, there are more possible rooms to go to. A number of size N has about (log2 N) digits in binary, where log2 is the logarithm in base 2. Since we can also move to a room with one more digit, there are (1 + log2 N) possible rooms to check whether they are prime. Yet changing the rightmost digit will certainly fail, (it would produce an even number) so we should only check log2 N digits. We would then expect about (log2 N/ ln N) new prime rooms. This simplifies to 1.442695 regardless of the value of N. So on the average, each room would lead to 1.442695 rooms (including the room we came from), regardless of the size of the room number. The increase in the digits of the numbers exactly cancels the effect of the prime number theorem, so the scarcity of large primes doesn't affect the structure of the maze!
Yet this is not the whole story. As long as we don't foolishly change the last binary digit to a 0, the new room number will be odd, doubling its chances on being prime. However, since we are adding or subtracting a power of 2 from a large prime, the new number cannot have the same remainder when dividing by 3. There will actually be a 50% chance of the new room number being a multiple of 3, as opposed to the 33% chance for a "random" number. (Try it!) Likewise, there will be a 75% chance of the new number not being a multiple of 5 instead of the expected 80% chance. If we make similar corrections for each prime, we find that the expected number of new primes stemming from a given room is
1.442695 (2).(3/4).(15/16).(35/36).....(p(p-2)/(p-1)2)...
After the 2, each number in this product is of the form p(p-2)/(p-1)2 for some prime p. As we multiply more and more terms, this product comes closer and closer to the number 1.9048. This indicates that branches in the maze are much more common than dead ends.
We can varify this experimentally, using the first million primes. Here is a table showing the average number of primes stemming from a prime, broken down in groups of 100,000.
Average # of branches Variance
---------------------+------------------------+-------------
First 100,000 primes | 1.95673 | 1.676374471
Next 100,000 primes | 1.95750 | 1.722630976
Next 100,000 primes | 1.93754 | 1.709355842
Next 100,000 primes | 1.97810 | 1.788598276
Next 100,000 primes | 1.93713 | 1.701794381
Next 100,000 primes | 1.94280 | 1.715985320
Next 100,000 primes | 1.98318 | 1.773514823
Next 100,000 primes | 1.95375 | 1.792708865
Next 100,000 primes | 1.93480 | 1.710206062
Next 100,000 primes | 1.92491 | 1.704008532
---------------------+------------------------+-------------
First million primes | 1.950644 | 1.729825715
As we can see from this table, the average number of branches remains roughly
constant thoughout the maze. If we let d=the average number of branches for
all primes, it seems as though our first estimate 1.9048 is a
tad low. Nonetheless, we can see that d is at least 1.9048.
Is this number large enough so that the maze will probably keep going on forever? Yes, in fact all that was nessecary was to show that d > 1. For large, random graphs with n vertices and m edges connecting the vertices, a classical result shows that there will be almost certainly one large component connecting most of the vertices as long as m > n/2. By "almost certainly", we mean that the probability aproaches 1 as n gets larger and larger. Since m=n/2 corresponds to d=1, we are well over this critical value in the prime maze. Thus, it is almost certain that the maze goes on forever.