7

The behavior when $p = 1/2$ and when $p > 1/2$ is rather different. When $p > 1/2$, in expectation you move $2p-1$ steps to the left, so you will hit the origin after a linear number of steps. When $p = 1/2$, the situation is more complicated. Consider a random walk on the line started at the origin. The number of walks of length $2n$ which never move ...


2

Is there any survey/review on this topic? Does Knuth cover random n-choose-k sampling in his TAOCP texts? I first looked at The Art of Computer Programming Volume 4A ("Combinatorial Algorithms Part 1"), specifically Section 7.2.1.3 "Generating all combinations" (which comes under Section 7.2.1 "Generating Basic Combinatorial Patterns", itself under 7.2 "...


1

Fix a star graph of $c + 1$ vertices. A star graph is a vertex connected to all other vertices in the graph (a universal vertex called the center), and all other vertices are pairwise not adjacent. Here is a visual example. $c$ is the center of the star. Now an optimal solution is to pack the center of the star. The size of this solution is equal to 1. For ...


Only top voted, non community-wiki answers of a minimum length are eligible