Timeline for A balls-and-colours problem
Current License: CC BY-SA 2.5
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 6, 2015 at 14:30 | comment | added | Sebastian Goette | @OriGurel-Gurevich: Apparently, there are some people around who find this answer cryptic, see for example [mathoverflow.net/q/222824/70808]. Could you add some more explanations? | |
| Jun 30, 2014 at 12:04 | comment | added | Ori Gurel-Gurevich | Ying, It states quite clearly that the functions in $F$ are from $\{1,\ldots,n\}$ to $\{1,\ldots,n\}$. Composition by a function in $F$ represents coloring one ball by the color of another ball. | |
| Jun 27, 2014 at 16:47 | comment | added | Ying Zhang | 3. The choice of f being uniform from F at each step? Again this has to do with the definition of f. But this probably doesn't matter as long as the other steps make sense. | |
| Jun 27, 2014 at 16:45 | comment | added | Ying Zhang | Sorry I am a bit confused: 1. what is the domain and codomain of each f? Are we talking about a map between balls and colors, or just a transition between colors? Without this being clear I don't see why introducing the time reversal process is really magic. 2. In Peter's comment above, what are the ``influential balls"? At time t, if we define the influential balls to be the balls whose current color eventually wins in the end, then at time t+1 this number could increase, decrease or stays the same. Why do we have a geometric distribution? | |
| Jan 3, 2011 at 6:41 | history | edited | Aaron Meyerowitz | CC BY-SA 2.5 |
fixed a subscript. Not sure how it survived this long?
|
| Oct 13, 2010 at 17:15 | vote | accept | Hedonist | ||
| Oct 13, 2010 at 17:08 | comment | added | Ori Gurel-Gurevich | $P(\tau > t)=P(g_t \verb"is not constant")=P(h_t \verb"is not constant")=P(\sigma > t)$ | |
| Oct 13, 2010 at 13:13 | comment | added | Peter Shor | Aha! I now understand Ori's answer. At time $t$, considering all steps from step $t$ to the end, there will be $k$ balls whose colors are mapped to all the other balls at the end. Considering time step $t-1$, the only way to reduce $k$ is to choose two of these $k$ influential balls, and have the color of one mapped to that of another. This gives the recursion in his answer. Very nice, although it could be explained better. | |
| Oct 13, 2010 at 8:33 | comment | added | Fedor Petrov | I do not take the point. Why $\sigma$ and $\tau$ have the same distribution? Equality of distributions at each time (not common distributions!), does it imply the equality oа distributions of the first stop? I do not think so. But hopefully we may fix it: expectation of $\sigma$ equals $\sum_{n=1}^{\infty} prob (\sigma\geq n)=\sum \prob(h_{n-1}\ne const)$, and in thi last we may replace $h$ to $g$. | |
| Oct 13, 2010 at 6:44 | history | answered | Ori Gurel-Gurevich | CC BY-SA 2.5 |