最優停止理論Optimal Stopping Theory 經典祕書問題Classic ...

最優停止理論Optimal Stopping Theory 經典祕書問題Classic Secretary Problem ... 從而，當n增大時，最優的k值趨近於n/e，最佳人選被選中的概率 ... 最優停止理論OptimalStoppingTheory經典祕書問題ClassicSecretaryProblem 首頁 最新 HTML CSS JavaScript jQuery Python3 Python2 Java C C++ Go SQL 首頁 最新 Search 最優停止理論OptimalStoppingTheory經典祕書問題ClassicSecretaryProblem 2018-12-22254 在博弈論中，類似問題，有相親問題、見好就收、蘇丹嫁妝問題、挑剔的求婚者問題等。

首先通俗解下類似問題：相親問題，售房問題。

    相親問題描述如下：     假如一個非常優秀的人相親，已知追求的他的人有有限個，例如10位，並且根據個人的評價，給這10個人給予了綜合打分。

現在規定，交往中他不能腳踏兩隻船，即不能同時和兩個人交往，如果在交往之後他沒有接受這個人，那麼，以後也沒有機會再選擇這個人作為物件。

然後接著和下一個人交往。

    這個問題可以看出，無論什麼時候選擇都會面臨很多不確定性，比如無法預知是否錯過了最優秀的人選，或者在選擇後，後面會不會有更好的人選。

那麼，他隨機和這些人交往，在和第幾個人交往時，他能選擇到最優秀的人作為物件呢，即何時停止交往可以使他選擇到最優秀的人最為物件呢？     第二個例子是售房問題。

假如你要賣掉一套房子，然後有人來買你的房，每個人出的價格不都是一樣的，如果你把房子賣給第一個人，那麼後面可能會有人出價更高，你會覺得自己虧，那麼你拒絕了第一個人，然後等待第二個人來買，但是在等待的過程中，你需要為沒有賣出的這套房子繳納物業費等費用。

立即賣掉會讓你節約開銷，但是不能保證你賣掉後的淨收益最高，那麼何時停止會使你的淨收益最高呢？    類似的問題還有：投擲硬幣猜正反面的賭博，盜竊問題等等[sr1.pdf]。

下面是停止規則的一般歸納，它是通過兩個物件來定義的：    （1）一系列隨機變數X1,X2,…，它們的聯合分佈規律是已知的，    （2）一系列獎勵函式Y0,Y(X1),Y(X1,X2),…     在考慮這兩個物件時，你可以一直觀察隨機變數X1，X2…在觀察變數Xn時，你可能會選擇停止，這個時候你獲得的獎勵是函式Yn(X1,X2,X3…,Xn)，當然這個函式值也可能是負數，比如女青年相求問題，加入相親了N個人（N很大），那麼她會經歷從“剩鬥士”到“必剩客”再到“齊天大剩”的過程，想想，還是很吃虧的（不僅木有回報，並且逝去了最美麗的年華）~~你也可能是持續觀察下一次的過程，記為N趨於無窮大，那麼這時候也有一個對應的回報函式值。

現在要解決的問題是，在何時停止觀察隨機變數x，可以是我們的回報函式值最大。

    這裡給出了理想的情況下，如何求解經典祕書問題：     問題描述：要聘請一名祕書，有n人來面試，n是已知的，而且面試者的能力有排名，隨機進行面試，每個人的機會是均等的。

每次面試一人，面試官便要即時決定聘不聘他，如果當時決定不聘他，他便不會回來。

面試時總能清楚瞭解求職者的適合程度，並能和之前的每個人作比較。

問憑什麼策略，才使選得到最適合擔任祕書的人的機率最大？     採取的策略：對前r-1個人都拒絕，然後對剩下的n-r+1個人進行面試，如果任何一個面試者比之前面試的人都優秀，那麼就聘請這個人。

前r-1個人被聘請的概率為0，假設從第r個人開始面試，面試到的第k個人是最優秀的並且被選中的應聘者。

那麼 最優秀應聘者被選擇的概率為：     其中，第k個為最優秀的並且被選中的人，根據概率論的知識，可以化簡為，第k個人在最優秀的前提下被選擇。

因為最優秀的人只有一個，所以它的概率為1/n，同時也就意味著，在前k-1中，最優秀到人在r-1個人中。

    既然是最優秀的，那麼，最優秀應聘者被選擇的概率大於他前後應聘者被選中的概率，所以有，     得到r一般表示式，現在要找到最優解，等價於找到滿足下列條件最小的r值：    TheuniversityofAlabamainHuntsville對上述表示式部分n值求解結果如下：    觀察可知結果在逐漸變小，Alabama大學對錶達式中不同n值與P的關係作圖，詳見連結：  http://www.math.uah.edu/stat/urn/Secretary.html     這裡通過表示式一樣可以近似得出與Alabama大學描述相同的結果，解答過程如下：    當n趨於無窮大，調和數列求和可以近似化簡， 如果作者瞭解微積分到話，求解過程會更易懂，應用微積分的解法如下： 令n趨近無窮大，把x表示為k/n的極限，令t為i/n,上述公式可近似為如下積分： 令P(x)對x的導數為0，解出x，我們得到最優的x等於1/e.從而，當n增大時，最優的k值趨近於n/e，最佳人選被選中的概率為1/e=0.368. 所以，經典祕書問題得出面試中應聘到最優面試者的概率是0.368，通俗所，100個人來面試，第36個人或者第37個人是最優應聘者的概率是最大的。

    個人覺得這是博弈論中一個問題的理想化解決方法，實際中是否如此呢？結果當然是不一定了。

因為我們都知道，被拒絕的求職者有一定機率能被叫回來;面試官面對應聘者可能有一定個人情感在其中；最終被選中的應聘者選可能會多於一人等等。

   但是這個結果是否有用呢？結果是肯定的，至少如果有一天你去面試一個崗位，面試官可能會出一道類似的智力題讓你回答。

比如我同學告訴，有面試官會問應聘者：如果給你一個硬幣，你至少拋多少次，才會出現連續三次出現反面的情況呢？再比如，如果現在拋硬幣七次，出現的都是正面，那麼再拋一次硬幣，是出現正面的概率大，還是出現反面的概率大呢？（這兩個問題作為懸念留個讀者吧）    最優停止理論OptimalStoppingTheory，在經濟學、金融領域使用非常廣泛，例如美式期權在股票交易中看漲看跌，執行期權，基本都使用停止理論來求解。

國內外非常多的論文中使用了最優停止理論，但是限於金融方面，所以我不曾拜讀這些文章；後面會給大家介紹這個理論在網際網路領域的應用，敬請期待~ 相關文章 最優停止理論OptimalStoppingTheory經典祕書問題ClassicSecretaryProblem AnIntuitiveGuidetoOptimalTransport|最優傳輸理論 LMS、NLMS最優步長理論分析與Speex回聲消除可能的改進想法 深入淺出資料分析：最優化-用Excel求解一個線性規劃問題 (優秀漢諾塔演算法)對漢諾塔經典遞迴問題的理解與講解（部分引用大神程式碼，附連結。

） 經典Top-K問題最優解決辦法以及C++程式碼實現 【SSH2框架（理論篇）】--SSH2Vs經典三層 Unity在協程內部停止協程自身後代碼執行問題 經典面試問題:TopK之----海量資料找出現次數最多或，不重複的。

php2019最新面試理論之精選 5本最佳的Java面向物件理論和設計模式的書籍 2018最新--軍事理論課答案（中國國防史） 《JVM調優實戰-理論篇》 《請停止無效的社交》第一章七問七答讀後感作文2300字 [android進階篇]MVP模式優化，防止記憶體洩漏和空指標問題 分類導航 HTML/CSS HTML教程 HTML5教程 CSS教程 CSS3教程 JavaScript JavaScript教程 jQuery教程 Node.js教程 服務端 Python教程 Python3教程 Linux教程 Docker教程 Ruby教程 Java教程 JSP教程 C教程 C++教程 Perl教程 Go教程 PHP教程 正則表達式 資料庫 SQL教程 MySQL教程 PostgreSQL教程 SQLite教程 MongoDB教程 Redis教程 Memcached教程 行動端 IOS教程 Swift教程 Advertisement 三度辭典 Copyright©2016-2021IT閱讀  Itread01.comAllRightsReserved. 0.001291036605835