<?php

    class RandomKeyMultiple {
    	private $pool = array();
		private $max_range;
 
    	function __construct( $source ) {
			// build the look-up array
    		foreach ( $source as $key => $value ) {
    			for ( $i = 0; $i < $value; $i++ ) {
    				$this->pool[] = $key;
    			}
    		}
    		$this->max_range = count($this->pool) - 1;
    	}
 
    	function get_random_key() {
    		$x = mt_rand(0, $this->max_range);
 
    		return $this->pool[$x];		
    	}
    }
 
    class RandomKey {
    	private $steps = array();
    	private $last_key;
    	private $max_range;
 
    	function __construct( $source ) {
    		// sort in ascending order to partially avoid numerical issues
    		asort($source);  
    		
    		// calculate the partial sums. Considering OP's array:
    		//
    		//   1300 ---->       0
    		//  30000 ---->    1300
    		// 190000 ---->   31300
    		// 265000 ---->  221300  endind with $partial = 486300
    		//
    		$partial = 0;
    		$temp = 0;
    		foreach ( $source as $k => &$v ) {
                $temp = $v;
    			$v = $partial;
        		$partial += $temp;
    		}

    		// scale the steps to cover the entire mt_rand() range
    		$factor = mt_getrandmax() / $partial;
    		foreach ( $source as $k => &$v ) {
    		    $v *= $factor;
    		}
    		
    		// Having the most probably outcomes first, minimizes the look-up of
    		// the correct index
    		$this->steps = array_reverse($source);

    		// remove last element (don't needed during checks) but save the key
    		end($this->steps);
    		$this->last_key = key($this->steps);
    		array_pop($this->steps);
    	}
 
    	function get_random_key() {
     		$x = mt_rand();
 
            foreach ( $this->steps as $key => $value ) {
    			if ( $x > $value ) {
    				return $key;
    			}
    		}
    		return $this->last_key;		
    	}
    	
    }
    
    // ***********  test section *************
    
    function number_right( $num, $size ) {
    	return str_pad(number_format($num), $size, ' ', STR_PAD_LEFT);
    }

    function percentage_right( $num, $decimals, $size ) {
    	return str_pad(number_format(100 * $num, 3), $size, ' ', STR_PAD_LEFT);
    }

    
    function test_randomness( $test, $original, $iterations ) {
     
        $sum = 0;
        foreach ( $original as $k => $v ) {
            $buckets[$k] = 0;
            $sum += $v;
        }
    	
        $start = microtime(true);
    	for ( $i = 0; $i < $iterations; $i++ ) {
    		$buckets[$test->get_random_key()]++;
    	}
    	$stop = microtime(true);
    	$duration = $stop - $start;
    	arsort($buckets);
    	echo "Distribution of ", number_format($iterations),
    		 " samples (generated in ", number_format($duration,5), " seconds):\n",
    		 "======================================================\n",
    		 "    key              occurences     (%)   (expected %) \n",
    		 "------------------------------------------------------\n";
    	foreach ( $buckets as $i => $num ) {
    		echo "    " , str_pad($i . ": ", 16), 
    			 number_right($num, 10),
    			 percentage_right($num / $iterations, 3, 11),
    		     percentage_right($original[$i] / $sum, 3, 10), "\n";
    	}
    	echo "------------------------------------------------------\n";
    }
     
    function test_steps( $arr, $name, $rep ) {
        echo "\nTesting steps method with $name array.\n";
        $test = new RandomKey($arr);
        test_randomness($test, $arr, $rep);
    }
    
    function test_reps( $arr, $name, $rep ) {
        echo "\nTesting repetitions method with $name array.\n";
        $test = new RandomKeyMultiple($arr);
        test_randomness($test, $arr, $rep);
    }
    
    $repetitions = 500000;

    $coin = array(     
    	 'head' => 1,    
    	 'tails' => 1    
    );
    test_reps($coin, "coins", $repetitions);

    $dice = array(     // results of throwing two dices
    	 '2' => 1,      // 1 + 1
    	 '3' => 2,      // 1 + 2 or 2 + 1
    	 '4' => 3,      // 1 + 3 or 2 + 2 or 3 + 1 
    	 '5' => 4,      // 1 + 4 or 2 + 3 or 3 + 2 or 4 + 1
    	 '6' => 5,      // 1 + 5 or 2 + 4 or 3 + 3 or 4 + 2 or 5 + 1
    	 '7' => 6,      // ...
    	 '8' => 5,
    	 '9' => 4,
    	'10' => 3,
    	'11' => 2,
    	'12' => 1
    );
    test_reps($dice, "dice", $repetitions);

    $arr2 = array(
      '0' => 265000, // Area
      '1' => 190000,
      '2' => 30000,
      '3' => 1300
    );
    test_reps($arr2, "OP's", $repetitions);

    $arr = array(
      '0' => 265000, // Area
      '1' => 190000,
      '2' => 30000,
      '3' => 1300
    );
    test_steps($arr, "OP's", $repetitions);
 
    $population = array(
    	"Washington" => 658.893,  // thousands
      	"New York" => 8406,
      	"Chicago" => 2719,
      	"Pasadena" => 139.731,
      	"Seattle" => 652.405
    );
    test_steps($population, "population", $repetitions);

?>