Закон Бенфорда или цифры не равны

Закон первой цифры или закон Бенфорда описывает вероятность появления первой значащей цифры в распределениях величин, взятых из реальной жизни.

В общем, в любых числовых множествах, которые могут расти экспоненциально, от данных об удельной теплоёмкости химических соединений до перечня номеров домов на улицах вашего города, единица будет встречаться чаще двойки, двойка чаще тройки и т.д., общая формула вероятности быть первой цифрой для десятичной системы счисления выглядит как P(d) = log 10 (1 + 1/d), d = 1,2,...,9.

При этом распределение зависит только от системы счисления, но не от единиц измерения.

Проверим это великое утверждение на первых 1000 членах ряда Фибоначчи.

Полученные результаты наглядно демонстрируют правоту Бенфорда:

Последнее найденное число: 2.68638e+208
         Найдено                 Ожидалось
1 :            30.1 %                      30.1 %
2 :            17.7 %                      17.6 %
3 :            12.5 %                      12.5 %
4 :             9.5 %                      9.69 %
5 :               8 %                      7.92 %
6 :             6.7 %                      6.69 %
7 :             5.6 %                       5.8 %
8 :             5.3 %                      5.12 %
9 :             4.5 %                      4.58 %
Сумма :            99.9 %                       100 %

а ниже прилагается листинг консольной программки, проверенной в Visual Studio 2015. Существенно увеличить объём выборки помешает потенциальное переполнение (см. "последнее найденное число").

#include <clocale>
#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <sstream>
#include <string>
#include <cstdlib>
#include <cmath>
#include <map>
using namespace std;

class NextNum {
public:
 NextNum(double & a, double & b) : first(a), second(b) { }
 double operator( )() {
  double result = first + second;
  first = second;
  second = result;
  return result;
 }
private:
 double first;
 double second;
};

void findFrequencies(const vector<double> & fibos, map<int, int> &numberfrequencies) {
 for (double bignumber : fibos) {
  ostringstream os;
  os << bignumber;
  int firstdigit = atoi(os.str().substr(0, 1).c_str());
  auto result = numberfrequencies.insert(make_pair(firstdigit, 1));
  if (!result.second)
   numberfrequencies[firstdigit]++;
 }
}

int main() {
 setlocale (LC_ALL,".1251"); //русская кодовая страница 1251
 const int volume = 1000; //объем выборки, возможно переполнение!
 vector <double> fibo (volume);
 fibo[0] = 0;
 fibo[1] = 1;
 double a = 0, b = 1; //a и b передаются по ссылке и меняются
 generate_n (fibo.begin() + 2, volume - 2, NextNum(a, b));
 cout << "Последнее найденное число: " << fibo[volume-1] << endl;
 map <int, int> frequencies;
 findFrequencies (fibo, frequencies);
 cout << setw(16) << "Найдено" << setw(26) << "Ожидалось" << endl;
 double sum1 = 0, sum2 = 0;
 for (int i = 1; i < 10; i++) {
  double found = static_cast<double>(frequencies[i]) / volume; //найденное по выборке
  sum1 += found * 100;
  double expected = log10(1 + 1 / static_cast<double>(i)); //теоретическое значение
  cout << i << " :" << setw(16) << right << found * 100 << " %";
  sum2 += expected * 100;
  cout.precision(3);
  cout << setw(26) << right << expected * 100 << " %" << endl;
 }
 cout << "Сумма :" << setw(16) << sum1 << " %";
 cout.precision(3);
 cout << setw(26) << right << sum2 << " %" << endl;
 cin.get();
 return 0;
}

04.09.2019, 22:47 [1564 просмотра]