<p>Here is a simple example from the field of distributed algorithms.</p>

<p>Typically randomness helps tremendously. Randomised distributed algorithms are often easier to design and they are faster.</p>

<p>However,  if you have a fast <em>deterministic</em> distributed algorithm, you can mechanically convert [<a href="http://dx.doi.org/10.1109/SFCS.1988.21938">1</a>, <a href="http://dx.doi.org/10.1109/SFCS.1991.185377">2</a>] it into a fast <a href="http://en.wikipedia.org/wiki/Self-stabilization">self-stabilising algorithm</a>. In essence, you will get a very strong version of fault-tolerance for free (at least if the bottleneck resource is the number of communication rounds). You can simplify your algorithm design by focusing on fault-free synchronous static networks, and the conversion will give you a fault-tolerant algorithm that can handle asynchronous dynamic networks.</p>

<p>No such conversion is known for <em>randomised</em> distributed algorithms in general.</p>

CC BY-SA 2.5
2010-10-16T08:44:20.163Z
2010-10-16T08:44:20.163Z
Jukka Suomela
<p>Let me first bring about an issue regarding randomness:</p>

<blockquote>
  <p>Does there exist any randomness in the universe, or is everything deterministic?</p>
</blockquote>

<p>This is a philosophical question which is both controversial and unrelated to the context here. Yet I used it as word of warning, since the upcoming answer will be controversial if one digs too deep into the above question.</p>

<hr>

<p><a href="http://en.wikipedia.org/wiki/Shannon%E2%80%93Hartley_theorem#Noisy_channel_coding_theorem_and_capacity" rel="nofollow">Shannon–Hartley theorem</a> describes the <em>capacity</em> of a communication channel in the presence of noise. The noise changes 0s to 1s and vice versa, with some pre-specified probability.</p>

<p>If the channel behaved in a deterministic way---That is, if we could model noise in a way that we were able to determine what bits would change---The capacity of the channel would be infinitely large. Very desirable!</p>

<p>I like to analogize randomness to friction: It is resisting movement, yet movement is impossible without it.</p>

CC BY-SA 3.0
2010-10-16T06:15:04.710Z
2013-08-26T17:12:20.843Z
2013-08-26T17:12:20.843Z
Sadeq Dousti
<p>Here is a simple example from game theory. In games in which both pure and mixed Nash equilibria exist, the mixed ones are often much less natural, and much "worse".</p>

<p>For example, consider a simple balls and bins game: there are n bins, and n balls (players). Each player gets to pick a bin, and incurs a cost equal to the number of people in his bin. The pure Nash equilibrium has everyone each picking a unique bin, and nobody incurs cost more than 1. However, there is a mixed Nash equilibrium in which everyone randomly chooses a bin, and then with high probability, there will be one bin with ~ $\log(n)/\log\log(n)$ people. Since OPT is 1, that means that (if what we care about is max player cost), if randomization is not allowed, then the price of anarchy is 1. But if randomization is allowed, it grows unboundedly with the number of players in the game.</p>

<p>The takeaway message: randomization can harm coordination. </p>

CC BY-SA 2.5
2010-10-15T22:59:37.713Z
cool - I like this interpretation of balls and bins as a 2 player game.  This is the kind of answer I had in mind!
Lev Reyzin
CC BY-SA 2.5
2010-10-15T23:06:33.603Z
It is sometimes discussed in its disguised form as "the load balancing game on identical machines" :-)
Aaron Roth
CC BY-SA 2.5
2010-10-15T22:54:30.287Z
2011-02-16T21:11:55.180Z
2011-02-16T21:11:55.180Z
Aaron Roth
<p>This question is inspired by the Georgia Tech <a href="http://arc.gatech.edu">Algorithms and Randomness Center</a>'s t-shirt, which asks "Randomize or not?!"</p>

<p>There are many examples where randomizing helps, especially when operating in adversarial environments.  There are also some settings where randomizing doesn't help or hurt.  My question is:</p>

<blockquote>
  <p>What are some settings when randomizing (in some seemingly reasonable way) actually hurts?</p>
</blockquote>

<p>Feel free to define "settings" and "hurts" broadly, whether in terms of problem complexity, provable guarantees, approximation ratios, or running time (I expect running time is where the more obvious answers will lie).  The more interesting the example, the better!</p>

CC BY-SA 2.5
2010-10-15T22:21:18.167Z
Downvoted.  This question seems to me like a question about rhetoric because the focus of the question seems to be how to argue that a particular fact can be referred to as “randomizing hurts.”
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-15T22:27:00.907Z
Fair enough.  But let me give you an example of what I had in mind.  Say we have a learning algorithm that has actions it can take, and, in the learning phase, takes them round robin.  Suppose it has some guarantee.  Now, say, we instead consider taking actions uniformity at random and find the guarantee is lost.  Hard to argue that this isn't an example of randomizing "hurting."  And feel free to define "hurts" for yourself!  Though that might be part of your criticism...
Lev Reyzin
CC BY-SA 2.5
2010-10-15T22:40:10.757Z
let it play out: maybe we'll get an interesting discussion. I know of at least one case where the simple randomized strategy is actually worse than a careful deterministic algorithm
Suresh Venkat
CC BY-SA 2.5
2010-10-15T22:50:37.677Z
The reason I do not like this question as is stated is probably because I expect that most voted answers will be “interesting” only in their interpretations of the question.  The question seems to be encouraging creative and rhetorical interpretations.  If this is not what you want and you can think of a better way to phrase the question, please revise it (but I cannot think of any).
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-15T22:57:44.453Z
Eek I didn't expect this question to be so controversial :) Anyhow I do not mind interesting interpretations!  I guess we'll have to disagree in this one.  Btw if the vagueness of the question is bothersome, I completely don't mind @Suresh making it a CW...
Lev Reyzin
<randomness><big-picture><randomized-algorithms>
Randomize or Not?
Lev Reyzin
# Randomize or Not?

(Asked by: username_0 on 2010-10-15)

This question is inspired by the Georgia Tech [Algorithms and Randomness Center](http://arc.gatech.edu)'s t-shirt, which asks "Randomize or not?!"

There are many examples where randomizing helps, especially when operating in adversarial environments. There are also some settings where randomizing doesn't help or hurt. My question is:

> What are some settings when randomizing (in some seemingly reasonable way) actually hurts?

Feel free to define "settings" and "hurts" broadly, whether in terms of problem complexity, provable guarantees, approximation ratios, or running time (I expect running time is where the more obvious answers will lie). The more interesting the example, the better!

**Tags:** randomness, big-picture, randomized-algorithms

> **Comments:**
> **username_1**: Downvoted.  This question seems to me like a question about rhetoric because the focus of the question seems to be how to argue that a particular fact can be referred to as “randomizing hurts.”  
> **username_0**: Fair enough.  But let me give you an example of what I had in mind.  Say we have a learning algorithm that has actions it can take, and, in the learning phase, takes them round robin.  Suppose it has some guarantee.  Now, say, we instead consider taking actions uniformity at random and find the guarantee is lost.  Hard to argue that this isn't an example of randomizing "hurting."  And feel free to define "hurts" for yourself!  Though that might be part of your criticism...  
> **username_2**: let it play out: maybe we'll get an interesting discussion. I know of at least one case where the simple randomized strategy is actually worse than a careful deterministic algorithm  
> **username_1**: The reason I do not like this question as is stated is probably because I expect that most voted answers will be “interesting” only in their interpretations of the question.  The question seems to be encouraging creative and rhetorical interpretations.  If this is not what you want and you can think of a better way to phrase the question, please revise it (but I cannot think of any).  
> **username_0**: Eek I didn't expect this question to be so controversial :) Anyhow I do not mind interesting interpretations!  I guess we'll have to disagree in this one.  Btw if the vagueness of the question is bothersome, I completely don't mind @Suresh making it a CW...  

---

## 3 answers

### Answer by username_5 on 2010-10-15. Score: 25 | Accepted answer

Here is a simple example from game theory. In games in which both pure and mixed Nash equilibria exist, the mixed ones are often much less natural, and much "worse".

For example, consider a simple balls and bins game: there are n bins, and n balls (players). Each player gets to pick a bin, and incurs a cost equal to the number of people in his bin. The pure Nash equilibrium has everyone each picking a unique bin, and nobody incurs cost more than 1. However, there is a mixed Nash equilibrium in which everyone randomly chooses a bin, and then with high probability, there will be one bin with ~ $\log(n)/\log\log(n)$ people. Since OPT is 1, that means that (if what we care about is max player cost), if randomization is not allowed, then the price of anarchy is 1. But if randomization is allowed, it grows unboundedly with the number of players in the game.

The takeaway message: randomization can harm coordination.

> **Comments:**
> **username_0**: cool - I like this interpretation of balls and bins as a 2 player game.  This is the kind of answer I had in mind!  
> **username_5**: It is sometimes discussed in its disguised form as "the load balancing game on identical machines" :-)  

---

### Answer by username_3 on 2010-10-16. Score: 13

Here is a simple example from the field of distributed algorithms.

Typically randomness helps tremendously. Randomised distributed algorithms are often easier to design and they are faster.

However, if you have a fast *deterministic* distributed algorithm, you can mechanically convert [[1](http://dx.doi.org/10.1109/SFCS.1988.21938), [2](http://dx.doi.org/10.1109/SFCS.1991.185377)] it into a fast [self-stabilising algorithm](http://en.wikipedia.org/wiki/Self-stabilization). In essence, you will get a very strong version of fault-tolerance for free (at least if the bottleneck resource is the number of communication rounds). You can simplify your algorithm design by focusing on fault-free synchronous static networks, and the conversion will give you a fault-tolerant algorithm that can handle asynchronous dynamic networks.

No such conversion is known for *randomised* distributed algorithms in general.


---

### Answer by username_4 on 2010-10-16. Score: 6

Let me first bring about an issue regarding randomness:

> Does there exist any randomness in the universe, or is everything deterministic?

This is a philosophical question which is both controversial and unrelated to the context here. Yet I used it as word of warning, since the upcoming answer will be controversial if one digs too deep into the above question.

---

[Shannon–Hartley theorem](http://en.wikipedia.org/wiki/Shannon%E2%80%93Hartley_theorem#Noisy_channel_coding_theorem_and_capacity) describes the *capacity* of a communication channel in the presence of noise. The noise changes 0s to 1s and vice versa, with some pre-specified probability.

If the channel behaved in a deterministic way---That is, if we could model noise in a way that we were able to determine what bits would change---The capacity of the channel would be infinitely large. Very desirable!

I like to analogize randomness to friction: It is resisting movement, yet movement is impossible without it.


---

