l*3
发帖数: 2279 | | n*****l
发帖数: 152 | 2 随机方法的基本习题。
【在 l*3 的大作中提到】
: 求破, 谢!
| l*3
发帖数: 2279 | 3 求指点!
【在 n*****l 的大作中提到】
: 随机方法的基本习题。
| n*****l
发帖数: 152 | | l*3
发帖数: 2279 | 5 谢谢. 但是我想了好久还是没知道怎么用. 可否具体些?...
比如我的概率空间是什么? 然后我要考查的随机变量是啥?
【在 n*****l 的大作中提到】
: Hint: 每种颜色有两种可能。
| y**k
发帖数: 222 | 6 就是点集因二分国分价两个X和Y。然后颜色也随机让他们取X和Y属性。对每个顶点，如
果其颜色属性全为另一个点集，则该点取值1，否则0。
所有点的值之和期望值小于1 | l*3
发帖数: 2279 | 7 经过各位大神的指点终于明白了.. (智商捉急, 叨扰各位了).
是不是这个意思?:
先定个规则: 对于一个固定的颜色, 让他以1/2的概率只允许被X中的点染色, 以1/2的
概率只允许被Y中的点染色.
那么, 如果X和Y中每个点对应的颜色集中存在可被允许染的颜色, 那就会成功染色. 反
之就存在至少一个点, 使得该点对应的颜色集都是不能拿来染该点的.
对于每个固定的点, 其颜色都不被允许的概率是小于等于0.5^(log_2 (n) + 1) = 1/(
2n)
所以存在一个点使得其对应色集中的色都不被允许的概率是小于等于n*1/(2n)=1/2的.
所以存在成功染色的事件.
------
如上无误吧? 再次谢过!
【在 y**k 的大作中提到】
: 就是点集因二分国分价两个X和Y。然后颜色也随机让他们取X和Y属性。对每个顶点，如
: 果其颜色属性全为另一个点集，则该点取值1，否则0。
: 所有点的值之和期望值小于1
|
|
