絕對公平？大數(shù)據(jù)破解北京機動車搖號的秘密

大數(shù)據(jù) 北京機動車搖號買車

熱情的沙漠 | 2016-07-27 12:06

【數(shù)據(jù)猿導(dǎo)讀】偶數(shù)月的26號中午11點到下午1點，手機上就會收到一條短信，不是中介和廣告，但內(nèi)容肯定是一樣的：“很遺憾，該編碼本次搖號未中簽或搖號資格已過期”。二姨媽真是比大姨媽都準(zhǔn)時!幾年過去了，在帝都辛苦擠地鐵的你，是否擁有這樣的疑問?現(xiàn)在搖號到底有多難

每兩個月一次的“二姨媽”

偶數(shù)月的26號中午11點到下午1點，沙漠君的手機上就會收到一條短信，不是中介和廣告，但內(nèi)容肯定是一樣的：“很遺憾，該編碼本次搖號未中簽或搖號資格已過期”。二姨媽真是比大姨媽都準(zhǔn)時!呵呵!

幾年過去了，在帝都辛苦擠地鐵的你，是否和沙漠君有同樣的疑問?

現(xiàn)在搖號到底有多難?

哪些人搖到了號?平均搖了幾回?

有沒有提升搖號概率的方法?

搖號算法是什么?是絕對公平的嗎?

沙漠君用真實的數(shù)據(jù)，告訴你答案。

搖到號的概率是多少?

2016到2017年，北京每年各有15萬個小汽車指標(biāo)。新能源比例達到40%，普通號只剩9萬個，一年6次，每次15000個。

但是!2016年第3次搖號，搖號池總數(shù)量是9917981!總搖號人數(shù)270.7萬!如果你搖號次數(shù)在24次之內(nèi)，那么本次搖到的概率為千分之一! 花166年搖一千次都不中的概率是37%!

每搖12次沒中簽，真的會像官方的說法，可能性增加一倍么?太天真!因為你增加，別人的也在增加。除非你是第一批參加搖號的人，否則會有更多的人比你增加更高的概率。因此，號是越來越難搖的。

五年間，搖到號的人數(shù)總共94萬人。2011年時，每隔10個人就會有一個幸運兒，幾年前買車確實比現(xiàn)在買車容易太多。看看這張圖：

2012年和2014年算是搖號黃金期，每期都有接近兩萬人搖到號，可是到了2016年，這個數(shù)字降為1.3萬。然而，下面這張圖絕對讓你哭暈!

當(dāng)然，每年增加的搖號人數(shù)基本是線性的：

從第一期的18萬，到2016年6月份的270萬，每年增加五十萬人。我們難以確定新增加的是哪些人數(shù)，按照政策，學(xué)生可能占了相當(dāng)大的比重(可參考附錄)。

那么，那些搖到號的人，總共搖了多少次呢?下面這張圖回答你：

有接近九萬人第一次就搖到號了，還有190人搖了整整51次才拿到號，這個曲線非常地光滑，幾個凸起點正好是調(diào)整中簽率的門限，非常符合數(shù)學(xué)的美感。

有14201人，51次搖號沒有一次成功。真正的幸運兒是這些人：在最近的這一期，以1/1000的概率第一次抽簽就拿到了號，一共90人。

搖號程序是否公平?

作為程序員的沙漠君，被激發(fā)了昂揚的斗志，我們來驗證一下?lián)u號程序是否公平。

通過使用沙漠君自己開發(fā)的Hawk爬蟲程序(見備注)，采集了從2011年到2016年51期每期的搖號池列表和隨機種子。同時，我還下載了它的搖號程序，用于分析其搖號算法。程序使用C#編寫，沙漠君破解它的源代碼簡直不要太容易。

為了能讓不懂程序的讀者也能理解，我用盡量簡明的語言描述其搖號方法：假設(shè)有5人搖號，每個人都有唯一的ID，1-5，用戶2,4有兩倍中簽率，用戶3有3倍中簽率，那么搖號池排列如下：

第一輪，把所有人都按次序排列，即上面的序號1-5;

第二輪，把所有中簽率大于等于2倍的按次序排列，即上面的6-8

第三輪，把大于等于三倍的按次序排列，上面只有9

現(xiàn)要求從池中隨機抽取三個序號。計算機能通過一個種子，可以生成一串看似隨機的偽隨機序列。在一般程序中，種子通常是當(dāng)前運行的時間。因每次運行時間不同，所以結(jié)果也不一同。

而搖號程序有趣的地方就在這里，種子是事先提供好的一串6位數(shù)字，一旦你知道它，那么你在搖號前就能預(yù)測哪些人被抽中。每個人的中簽倍率和ID都是確定的，因此分析6位的隨機數(shù)種子是如何產(chǎn)生的，成了解決問題的關(guān)鍵。

6位隨機種子是如何產(chǎn)生的?

沙漠君研究了首都之窗上用于公示隨機數(shù)的2013年某期的視頻。

公證人員事先從市民中選出12位代表人。主持人在魚缸中隨機抽出6個球，每個球都是一個市民代表人的號碼。之后，6個代表人會依次敲擊鍵盤，隨機產(chǎn)生出0-9的隨機數(shù)作為隨機數(shù)種子。有趣的地方就在這里!!

主持人說，請每一位代表搖出號碼，我一幀幀地分析了視頻，從市民代表在鍵盤上的操作位置來猜測，點擊的多半是是回車鍵，但代表按鍵盤都是背對攝影機的。你可以簡單理解為，每按一次回車，電腦產(chǎn)生出一個新的0-9的數(shù)字，總計6個。

網(wǎng)站提供了隨機產(chǎn)生搖號號碼的程序，卻沒有提供隨機產(chǎn)生六位種子的程序。這個隨機數(shù)種子本身，會不會事先保存，一定能保證隨機嗎??？聪旅孢@張圖：

如果你感興趣的話，可以去參考本文的附錄，附錄詳細地給出了如何從申請編碼入手，探索搖號系統(tǒng)的可能破綻。但能不能探索出來就不知道了。

那我們該怎么辦?

一種方法是購買新能源汽車，中簽率約為12分之一。開著新能源，六環(huán)可能都出不去就沒電了(>_<)。

按照非官方說法，搖號政策可能在未來退出，并引入家庭單位搖號和征收擁堵費。但發(fā)出去的車牌不會回收，而一旦放開限購會導(dǎo)致瘋狂購車，因為擁堵費太貴，大家塞滿小區(qū)就是不出門：先把坑占上。這肯定也不是政府愿意看到的。至于之前傳言的24次搖號沒中者自動分配一個號碼，我都不想告訴你24次以上沒搖中的人有多少!傳謠也要講基本法啊。

通過以上分析，解決了沙漠君之前的疑惑，這套系統(tǒng)設(shè)計是符合規(guī)范的，抽簽是隨機和公平的。各位親愛的讀者，安心搖號，洗洗睡吧~/(ㄒoㄒ)。以后多綠色出行，為首都交通做出貢獻。

備注和源代碼

1.數(shù)據(jù)來源

來自bjhjyd.com，截至2016年6月?lián)u號人數(shù)共計4394613人。但目前不確定學(xué)生是否能搖號。

對北京來說600萬輛是一個紅線，而北京作為全國示范，更愿意用行政而非經(jīng)濟手段來限制機動車數(shù)量，以表現(xiàn)公平。我國人口已經(jīng)進入負增長，50年以后人口嚴重老齡化，我們老了之后開車可能會容易一些。

幾年前可以網(wǎng)上查到每個中簽人的名字，還有下面的新聞：

2. 假如系統(tǒng)真的有破綻呢?

(本段僅作為思想實驗，開腦洞而已，請任何人不要對號入座。水表在門外，謝謝!)

通過控制種子，可以保證特定號碼中簽。但這樣可能沒法讓所有要中簽的都中簽，策略是插入一些無效號。無效號能將特定的號碼擠到對應(yīng)必中的位置。

因為我們也無法判斷參與抽簽的每個號碼都是有效的。而且你注意到了嗎?2016年，每次搖號應(yīng)該有15000個，但每次搖中的數(shù)量都差了一百多個，剩下的哪里去了?

通常計算機產(chǎn)生無效號，都是在短時間內(nèi)集中產(chǎn)生的。如果能發(fā)現(xiàn)給每個用戶分配編碼的規(guī)則，就能反推用戶的基本信息和注冊時間，如果在統(tǒng)計上發(fā)現(xiàn)異常，就能找到這些無效號碼，進而搜索隨機種子。

沙漠君盯著這些長度都是13位的號碼，統(tǒng)計了每一位上0-9字符出現(xiàn)的頻率，發(fā)現(xiàn)它們都是等概率出現(xiàn)的。說明編碼是按照某種隨機算法生成的。什么工具的隨機算法產(chǎn)生的字符長度是13位呢?我花了五六個小時破解這個邏輯：

我通過搖號程序簽名，發(fā)現(xiàn)開發(fā)這套系統(tǒng)的公司叫taiji。我通過該公司網(wǎng)站的招聘信息和項目介紹，了解了驗證軟件是2014年1月6號下午開發(fā)開發(fā)，用了一個半月開發(fā)完，后臺語言多半是C#。

據(jù)我猜測，每次會從后臺隨機產(chǎn)生不在數(shù)據(jù)庫里的一個13位的隨機數(shù)，作為新申請人的編碼ID。理論上說，如果其系統(tǒng)用的是C#默認的隨機生成器，那么就能通過暴力搜索的方法，找出每個編碼生成的時間，也就是號碼注冊的時間，當(dāng)然，這種計算的復(fù)雜度非常高，靠一己之力是很難完成的。

但我相信，以上這些推測都是瞎扯，這套系統(tǒng)一定是公平而完美的。

3.Hawk數(shù)據(jù)抓取工具

這是筆者耗時四年開發(fā)的數(shù)據(jù)抓取軟件，目前已經(jīng)開源，詳情可參考沙漠之鷹的歷史文章《如何從互聯(lián)網(wǎng)抓取海量數(shù)據(jù)》。

4.生成真實搖號數(shù)據(jù)源代碼