Apparatus, and an associated method for facilitating paging of an access terminal operable in a radio communication system. A plurality of random numbers are generated. And, for each of the random numbers, a hash value is created by applying the random number to a hash function. The hash values identify bit locations of a paging message. When the paging message is formed, bit locations associated with the hash values are populated with bit values that identify whether the access terminal is being paged. And, the access terminal checks the bit values at the bit locations associated with the hash values to determine whether the access terminal is being paged.