随机

最近看了很多nonblocking算法,它们都有一个特点,很多之前需要上锁的地方,现在被一个while(true)包起来。总体来说,对于冲突的发生概率,始终持一个很乐观的态度。乐观背后的含义就是说我不强求每次执行都能得到我想要的结果,大部分时候它都能,以非常低的概率,它会失败,此时重试一遍就好。很多随机化算法的目的在于打破对称性,所以有时候一个简单的随机的sleep就能让吞吐量上升很多。我在想随机化算法在并行编程中应该能找到很多很有趣的应用场景。

昨天晚上快睡觉的时候看了一会儿Parrondo悖论,蛮有意思的,在这分享一下。大家都知道,老虎机这样的东西,通俗来说你玩的越多,你输的越多。那么有没有可能交替的玩两个对我来说是“输”的游戏,但是实际会产生一个“赢”的结果?

假设我是一个玩家,

先看Game1:掷硬币。正面向上就赢一块钱,反面向上就输一块钱。可惜这个硬币并非制造的那么完美的硬币,它的质量分布略微有些不均等,所以导致它正面向上的概率是 0.49,反面向上的概率是0.51。很明显,这是一个对我不利的游戏。我不玩。

于是庄家为我设计了Game2: 现在换成了两个硬币。硬币b和c。如果从开始玩到现在,我赢得的钱数是3的倍数,那么扔硬币b,否则扔硬币c。其中硬币b以0.09的概率出现正面,硬币c以0.74的概率出现正面。表面上来看,我赢的概率是\(\frac{1}{3}*0.09+\frac{2}{3}*0.74=\frac{157}{300} \gt \frac{1}{2}\),实际上不能假定”我赢的的钱数是3的倍数”这个事件出现的概率是\(\frac{1}{3}\),因为这是一个结果,而不是一个独立的基本事件。实际上这个概率的计算过程非常非常复杂,实际上算出来结果是小于\(\frac{1}{2}\).

有意思的是,如果把这两个Game组合起来得到Game3:拿一个硬币d,它是均匀的,所以正面向上的概率是50%。每次先扔硬币d,假如它正面向上,那么进行Game1,否则进行Game2。最终算出来的结果是,这两个“输”的游戏被组合成了一个“赢”的游戏。我觉得,要点是,“从开始玩到现在,我赢得的钱数是3的倍数”这个事件的概率变了。

此博客中的热门博文

在windows下使用llvm+clang

少写代码,多读别人写的代码

tensorflow distributed runtime初窥