请输入您要查询的字词:

 

单词 ExampleOfAProbabilisticProof
释义

example of a probabilistic proof


Our example is the existence of k-paradoxical tournaments. The proof hinges upon the following basic probabilistic inequality, for any events A and B,

P(AB)P(A)+P(B)
Theorem 1.

For every k, there exists a k-paradoxical tournament.

Proof.

We will construct a tournament T on n vertices. We will show that for n large enough, a k-paradoxical tournament must exist. The probability spaceMathworldPlanetmath in question is all possible directions of the arrows of T, where each arrow can point in either direction with probability 1/2, independently of any other arrow.

We say that a set K of k vertices is arrowed by a vertex v0 outside the set if every arrow between v0 to wiK points from v0 to wi, for i=1,,k. Consider a fixed set K of k vertices and a fixed vertex v0 outside K. Thus, there are k arrows from v0 to K, and only one arrangement of these arrows permits K to be arrowed by v0, thus

P(K is arrowed by v0)=12k.

The complementary event, is therefore,

P(K is not arrowed by v0)=1-12k.

By independence, and because there are n-k vertices outside of K,

P(K is not arrowed by any vertex)=(1-12k)n-k.(1)

Lastly, since there are (nk) sets of cardinality k in T, we employ the inequality mentioned above to obtain that for the union of all events of the form in equation (1)

P(Some set of k vertices is not arrowed by any vertex)(nk)(1-12k)n-k.

If the probability of this last event is less than 1 for some n, then there must exist a k-paradoxical tournament of n vertices. Indeed there is such an n, since

(nk)(1-12k)n-k=1k!n(n-1)(n-k+1)(1-12k)n-k
<1k!nk(1-12k)n-k

Therefore, regarding k as fixed while n tends to infinity, the right-hand-side above tends to zero. In particular, for some n it is less than 1, and the result follows.∎

随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 17:28:00