29
What you can do, is to employ a method called rejection sampling:
Flip the coin 3 times and interpret each flip as a bit (0 or 1).
Concatenate the 3 bits, giving a binary number in $[0,7]$.
If the number is in $[1,6]$, take it as a die roll.
Otherwise, i.e. if the result is $0$ or $7$, repeat the flips.
Since $\frac 68$ of the possible outcomes lead to ...
23
Imagine a different problem: if you had to place $k$ sticks of equal heights in $n$ slots then the expected distance between sticks (and the expected distance between the first stick and a notional slot $0$, and the expected distance between the last stick and a notional slot $n+1$) is $\frac{n+1}{k+1}$ since there are $k+1$ gaps to fit in a length $n+1$.
...
14
What you're looking for is based on Rejection sampling or the accept-reject method (note that the Wiki page is a bit technical).
This method is useful in these kinds of situations: you want to pick some random object from a set (a random integer in the set $[a,b]$ in your case), but you don't know how to do that, but you can pick some random object from a ...
14
Also, the Wikipedia page (https://en.wikipedia.org/wiki/Log_probability) is confusing in this respect, stating "The conversion to log form is expensive, but is only incurred once." I don't understand this, because I think you would need to take the log of every term independently before adding. What am I missing?
If you just want to compute $P(A_1)\ldots P(...
13
First of all, I will assume that by
Additionally, the state $f_S$ of $f$ is set to a value $f_S' = f_S \pm k$, where $k$ is selected uniformly at random from $$\{0, 1, 2, ..., \lfloor n/2 \rfloor - ((f_S - x) \mod n)\} $$
you actually mean
Additionally, the state $f_S$ of $f$ is set to a value $f_S' = f_S + k \mod n$, where $k$ is selected uniformly ...
13
Yes and no, depending on what you mean by “the only way”. Yes, in that there is no method that is guaranteed to terminate, the best you can do (for generic values of $N$ and $R$) is an algorithm that terminates with probability 1. No, in that you can make the “waste” as small as you like.
Why guaranteed termination is impossible in general
Suppose that you ...
answered Jul 4 '12 at 23:18
Gilles 'SO- stop being evil'
38k7 gold badges102 silver badges166 bronze badges
13
We will show by induction that the permutation $\rho_n = (2,3,4,\ldots, n,1)$ is an example with $C(\rho_n) = 2^{n-1}$. If this is the worst case, as it is for the first few $n$ (see the notes for OEIS sequence A192053), then $m(n) \approx (2/e)^{n}$. So the normalized min, like the normalized max, is 'exponentially bad'.
The base case is easy. For the ...
12
Suppose your array has $n$ elements. As you have noted, the median is always in the bigger part after the first partition. The bigger part has size at most $\alpha n$ if the smaller part has size at least $(1-\alpha) n$. This happens when you pick a pivot that isn't one of the smallest or largest $(1-\alpha) n$ elements. Because $\alpha > 1/2$, you ...
12
(This answer uses the second link you gave.)
$\newcommand{\Like}{\text{L}}\newcommand{\E}{\text{E}}$Recall the definition of likelihood: $$\Like[\theta | X] = \Pr[X| \theta] = \sum_Z \Pr[X, Z | \theta]$$
where in our case $\theta = (\theta_A, \theta_B)$ are the estimators for the probability
that coins A and B respectively land heads, $X = (X_1, \dotsc, X_5)...
12
To have a slightly more efficient method than the one pointed out by @FrankW but using the same idea, you can flip your coin $n$ times to get a number below $2^n$. Then interpret this as a batch of $m$ die flips, where $m$ is the largest number so that $6^m < 2^n$ (as already said, equality never holds here). If you get a number greater or equal to $6^m$ ...
11
Henry's solution is both simpler and more general than this one!
$E[V]$ is roughly half the expected number of comparisons performed by randomized quicksort.
Assuming the sticks have distinct heights, we can derive a closed-form solution for $E[Y]$ as follows.
For any indices $i\le j$, let $X_{ij} = 1$ if $Y_j = \max\{Y_i,...,Y_j\}$ and $X_{ij}=0$ ...
11
The algorithm works, but to understand why, you need to know basic probability theory. The idea is to prove by induction that at step $t$, the currently selected algorithm is uniform among the first $t$ elements. This is clearly the case when $t=1$. Assume now the induction hypothesis for time $t$, and consider what happens at time $t+1$. With probability $1/...
11
No, it's not possible. Suppose the bias of the coin is $1/3$, and suppose you could guarantee termination. Then there would be some $n$ such that this always terminates after $n$ coin flips. Let $S$ denote the set of flip-sequences that causes your algorithm to output 0 (so that $\overline{S}$ is the set of flip-sequences that causes your algorithm to ...
11
Your process is a textbook example of a branching process. Starting with one $E$, we have an expected $3/2$ many $F$s, $9/4$ many $T$s, and so $9/8$ many remaining $E$s in expectation. Since $9/8 > 1$, it is not surprising that your process often failed to terminate.
To gain more information, we need to know the exact distribution of the number of $E$-...
10
After some digging around thanks to mhum's pointer to OEIS, I've finally found an excellent analysis and a nice (relatively) elementary argument (due, as far as I can tell, to Goldstein and Moews [1]) that $M(n)$ grows superexponentially fast in $n$:
Any involution $\iota$ of $\{1\ldots n\}$ corresponds to a run of the 'naive' shuffling algorithm that ...
10
Suppose you wish to compute the random graph $G(n,p)$ that is the graph with $n$ vertices where each edge is added with probability $p.$
Suppose you have a coin that gives tails with probability $p$ and heads with probability $1-p.$
Then what you do you take $\{1,...,n\}$ to be the vertex set of your graph and for each pair $(i,j) \in { \{1,\ldots,n\} \...
10
A Continuous-time Markov Chain can be represented as a directed graph with constant non-negative edge weights. An equivalent representation of the constant edge-weights of a directed graph with $N$ nodes is as an $N \times N$ matrix. The Markov property (that the future states depend only on the current state) is implicit in the constant edge weights (or ...
9
So basically there are three questions involved.
I know that $E(X_k)=\tbinom{n}{k}\cdot p^{\tbinom{k}{2}}$, but how do I prove it?
You use the linearity of expectation and some smart re-writing. First of all, note that
$$ X_k = \sum_{T \subseteq V, \, |T|=k} \mathbb{1}[T \text{ is clique}].$$
Now, when taking the expectation of $X_k$, one can simply draw ...
9
Due to the dubious nature of the question, I only provide hints.
Have you tried the obvious? With probability $\frac{1}{n}$, add the new element to the sample. If it is added, choose one of the elements already in the sample uniformly at random and drop it. Sounds about fair, does it not?
For a proof, you will have to proceed inductively. In the step, you ...
9
Your coin flips form a one-dimensional random walk $X_0,X_1,\ldots$ starting at $X_0 = 0$, with $X_{i+1} = X_i \pm 1$, each of the options with probability $1/2$. Now $H_i = |X_i|$ and so $H_i^2 = X_i^2$. It is easy to calculate $E[X_i^2] = i$ (this is just the variance), and so $E[H_i] \leq \sqrt{E[H_i^2]} = \sqrt{i}$ from convexity. We also know that $X_i$ ...
9
Use reservoir sampling. This is a good description in Wikipedia, or in Knuth.
Let's start with the simple case, where $k=1$. You always have one string in memory. When you read the first string, you store it in memory. Each time you read a new string, you replace it with the one in memory with probability $1/i$, if this is the $i$th string you've read so ...
8
As $m = k \times n$, we can look at this in terms of $k$ and $n$ instead of $n$ and $m$. Let's say $T_i$ is the time it takes the $i$-th processor to finish its work.
As $n$ grows, the probability that $T_i$ = $5k$ (the processor was assigned only $T=5$ tasks) for some $i$ approaches $1$, so makespan being defined as $\mathrm{max}(T_i)$, $E[M]$ approaches $...
8
Markov Chains come in two flavors: continuous time and discrete time.
Both continuous time markov chains (CTMC) and discrete time markov chains (DTMC) are represented as directed weighted graphs.
For DTMC's the transitions always take one unit of "time." As a result, there is no choice for what your weight on an arc should be-- you put the probability of ...
8
There is no decision problem that is (unconditionally) known to be in $coNP \setminus NP$. If we had a decision problem that we could prove is in $coNP$ and could prove is not in $NP$, then we would have proven that $NP \ne coNP$, from which it follows that $P \ne NP$. In other words, if we knew of such a problem, a proof that is in $coNP \setminus NP$ ...
8
This is an example of a branching process. The behavior of a branching process depends on the expected number of children, which in your case is $1.25 > 1$. When this number is at most 1, the process gets extinct with probability 1. When the number is more than 1, it has a chance of surviving forever; the extinction probability is just what you calculated ...
7
(technicalities: the answer fits selection of number $a \le x < b$)
Since you are allowed to flip your coin as many times as you wish, you can get your probability as-close-as-you-wish to uniform by picking a fraction $r\in [0,1]$ (using binary radix: you flip the coin for each digit after the point) and multiply $r$ by $b-a$ to get a number between 0 ...
7
Choose a number in the next larger power of 2 range, and discard answers greater than $b-a$.
n = b-a;
N = round_to_next_larger_power_of_2(n)
while (1) {
x = random(0 included to N excluded);
if (x < n) break;
}
r = a + x;
7
Nobody mentioned this, so let me formally prove that if $D$ is a domain whose size is not a power of two, then finitely many fair coin tosses aren't enough to generate a uniformly random member of $D$. Suppose you use $k$ coins to generate a member of $D$. For each $d \in D$, the probability that your algorithm generated $d$ is of the form $A/2^k$ for some ...
7
The standard library of Coq has a section about real numbers. These are the classical real numbers, using the Dedekind completion. There are also results about complex numbers, I suppose there are several libraries, I happen to know this one. Note that there is also a lot of results for constructive real and complex numbers, C-CoRN is the reference.
Side ...
7
Consider this: get two elements $x_0$ and $x_1$ from $S$. If $x_0x_1$ is $aa$ or $bb$ then discard them and repeat. Otherwise return $0$ for $ab$ and $1$ for $ba$, events that occur with the same probability $p_ap_b$.
This will use $2n$ elements from $S$, $n$ the number of performed steps. The probability of stopping at each step is $p=1-2p_ap_b$. The ...
Only top voted, non community-wiki answers of a minimum length are eligible
