使用概率分布对数组进行排序

Question

数组应按其值从高到低排序。

<?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->result;
  }
}

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: %f\n", $result[5] / $result[1]);

?>

---

我已经尝试了十亿轮。但比率还是 6.75 - 重点是：为什么不是 5？

---

结果

<?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

Answer 1

这是一个简单的 f 可以做到这一点。

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

这是保证有效的，因为最大值同样可能是所选的 15 个随机数中的任何一个，并且该数字出现在 f(5) 中的时间为 1/3，而对于f(1)。

至于你的f出了什么问题，很简单。您的解决方案具有良好的对称性，恰好 80% 的时间 f(1) f(1) < f(5)。然而，当 f(1) 大于平均值时，f(1) 往往大于 f(5) em> f(5) 小于平均值。 f(2)、f(3) 和 f(4) 也是如此。然而，所有 f(2), ... f(5) 同时变小的情况并不常见。这会导致相关性导致 f(1) 成为最大的频率比您天真的想象的要少。反之亦然，相关性往往比您天真的想象的更倾向于 f(5)。

如果您想计算每个数字出现在顶部的确切概率，那么通过积分计算准确的答案应该不会太难。这个想法是，您将概率从 0 积分到 1，如果这是 f(i) 的 random() 值，则 f(i) 是最大值。 （因此，例如，对于 5，您需要集成 (1-x/5)(1-x/4)(1-x/3)(1-x/2)，而对于 1，您需要集成如果 random() 大于 0.2，则对函数进行积分，该函数为 0，否则为 (1-2x)(1-3x)(1-4x)(1-5x)< /code>.) 表达式将是复杂，并且比率不会得出很好的答案。