Блог

Массив должен быть отсортирован от высокого к низкому по его значениям.

 <?php
$items = array(
  1 => f(1),
  2 => f(2),
  3 => f(3),
  4 => f(4),
  5 => f(5),
);
?>
  

После сортировки я смотрю, какой элемент 1, 2, 3, 4, 5 является первым. Я пробую это снова, и снова, и снова.
Впоследствии

• 5 должно быть первым элементом в пять раз больше, чем 1
• 4 должно быть первым элементом в четыре раза больше, чем 1
• 3 должно быть первым элементом в три раза больше, чем 1
• 4 должно быть первым элементом в два раза больше, чем 2
• …

Одна идея заключается

 <?php
function f(key) {
  return key / random();
}
?>
  

что для 1’000’000 попыток привело к

 key | times on top | ratio with key one | expected ratio
---- -------------- -------------------- ---------------
 5  |      374'365 | 6.75               | 5
 4  |      267'863 | 4.83               | 4
 3  |      185'707 | i am so lazy ...   | 3
 2  |      116'618 |                    | 2
 1  |       55'447 | 1                  | 1
  

Для меня это выглядит странно, но, возможно

• есть простая проблема с f?
• есть лучший f?

Моя реализация:

 <?php

abstract class Test {

  private $result;

  protected abstract function f($x);

  protected function iteration() {
    $values = array(
      1 => $this->f(1),
      2 => $this->f(2),
      3 => $this->f(3),
      4 => $this->f(4),
      5 => $this->f(5),
    );

    arsort($values);

    $top = key($values);

    if (!isset($this->result[$top])) {
      $this->result[$top] = 1;
    } else {
      $this->result[$top]  ;
    }
  }

  public function run($iterations) {
    $this->result = array();
    for($i = 0; $i < $iterations; $i  ) {
      $this->iteration();
    }
    arsort($this->result);
    return $this->resu<
  }
}

class MyTest extends Test {
  protected function f($x) {
    return $x / rand();
  }
}

$test = new MyTest();
$result = $test->run(1000 * 1000);
print_r($result);
printf("Ratio of key 5 to 1, which should be 5: %fn", $result[5] / $result[1]);

?>
  

Я перепробовал миллиард раундов. Но опять же соотношение равно 6,75 — весь смысл в том, почему это не пять?

Результаты для

 <?php
class BetterRandomGeneratorTest extends Test {
  protected function f($x) {
    return $x / mt_rand();
  }
}
?>
  

являются

 Array
(
  [5] => 3742816
  [4] => 2674352
  [3] => 1861444
  [2] => 1168333
  [1] => 553055
)
Ratio of key 5 to 1: 6.767529
  

Вот простое f, которое это сделает.

 function f(key) {
  $x = 0;
  for($i = 0; $i < $key; $i  ) {
    $y = random();
    if ($x < $y) {
      $x = $y;
    }
  }
  return $x;
}
  

Это гарантированно сработает, потому что максимальным с равной вероятностью будет любое из 15 выбранных случайных чисел, и в 1/3 случаев это число будет находиться в f(5) , по сравнению с 1/15 для f(1) .

Что касается того, что было не так с вашим f , это довольно просто. Ваше решение обладает хорошей симметрией ровно в 80% случаев f(1) < f(5) . Однако f(1) имеет тенденцию быть больше, чем f(5) когда f(1) больше среднего и f(5) меньше среднего. То же самое для f(2) , f(3) и f(4) . Однако необычно, чтобы все f(2), ... f(5) были маленькими сразу. Это приводит к тому, что корреляции, которые вызывают f(1) наибольшее значение, встречаются реже, чем вы наивно думаете. Наоборот, корреляции, как правило, проявляются в пользу f(5) чаще, чем вы могли бы наивно подумать.

Если вы хотите вычислить точные вероятности каждого числа, выходящего сверху, не должно быть слишком сложно вычислить точные ответы с интеграцией. Идея заключается в том, что вы интегрируете от 0 до 1 вероятность того, что, если это было значением random() для f(i) этого f(i) , оно является максимальным. (Так, например, для 5 вы бы интегрировали, (1-x/5)(1-x/4)(1-x/3)(1-x/2) в то время как для 1 вы бы интегрировали функцию, которая равна 0, если random() больше 0.2, а в противном случае равна (1-2x)(1-3x)(1-4x)(1-5x) .) Выражения будут сложными, и соотношения не приведут к хорошим ответам.