Problem 2697. Probability of winning single-elimination tournament

Created by Paul Berglund

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Find the probability that the p^{th} player will win a single-elimination tournament with 2^n players where M(i,j)=probability that player i will beat player j in a head-to-head matchup. In the first round player 1 plays player 2, player 3 plays player 4 and so on. (In each round each surviving competitor plays his surviving \"next door neighbor\" in the bracket.)</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>See also problem</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"2254\"><w:r><w:t>2254</w:t></w:r></w:hyperlink><w:r><w:t>.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Trivial example :</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>if</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[M = [ NaN 0.7 ; 0.3 NaN ]]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>then</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[winprob(M,1)=0.7]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>and</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[winprob(M,2)=0.3]]></w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

Solve

Solution Stats

36 Solutions
6 Solvers

Last Solution submitted on Jul 04, 2021

Last 200 Solutions

Problem Comments

2 Comments

2 Comments

Jon on 1 Dec 2014

Could you make your test cases consistent on using either 0 or NaN on the diagonal?

Paul Berglund on 2 Dec 2014

OK, I made it consistently use NaN.

Problem Recent Solvers6

Problem Tags

tournament

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Problem 2697. Probability of winning single-elimination tournament

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers6

Suggested Problems

More from this Author3

Problem Tags

Community Treasure Hunt

Problem 2697. Probability of winning single-elimination tournament

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers6

Suggested Problems

More from this Author3

Problem Tags

Community Treasure Hunt

Players