Timeline for Another colored balls puzzle (part II)
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 18, 2013 at 21:42 | comment | added | Douglas Zare | @Jon Peterson: Yes, that's why I looked at the graph $C/\sim$, where $\sim$ identifies antipodal points of the cube, which has $2^{n-1}$ vertices. $C/\sim$ is also connected and regular. Stopping at either $00\ldots 0$ or $11 \ldots 1$ is equivalent to stopping at the original point in a random walk on $C/\sim$. | |
| May 17, 2013 at 13:39 | comment | added | Jon Peterson | @Ori: There is an error in your application here. The process is completed either when all balls become the one color. Thus, you should be looking for the the expected time for the random walk to reach either the vertex $00\ldots 0$ or the vertex $11\ldots 1$. I did a few computations, and it appears that this is equal to $2^{n-1}-1$. | |
| May 17, 2013 at 9:50 | comment | added | user25199 | @ButchMalahide You're right - must be much older. After all Lovasz's section 1 is "Basic notions and facts." | |
| May 16, 2013 at 22:13 | comment | added | user25199 | @navid: Lovász, László. "Random walks on graphs: A survey." Combinatorics, Paul Erdos is Eighty 2.1 (1993): 1-46. See the end of section 1. | |
| May 16, 2013 at 20:50 | comment | added | navid | @ButchMalahide Do you know a reference for that remarkable fact? | |
| May 15, 2013 at 9:26 | comment | added | Vincent Beffara | Very nice indeed! | |
| May 15, 2013 at 8:51 | comment | added | Johan Wästlund | Nice! And just a comment for people like myself who don't see it immediately: If you walk around in the graph forever, then by symmetry you will spend $1/2^n$ of your time at each vertex, and therefore the expected time until you return is $2^n$. | |
| May 15, 2013 at 6:17 | history | answered | Ori Gurel-Gurevich | CC BY-SA 3.0 |