Newest questions tagged sampling - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-08-23T15:30:56Z https://cs.stackexchange.com/feeds/tag?tagnames=sampling&sort=newest http://www.creativecommons.org/licenses/by-sa/3.0/rdf https://cs.stackexchange.com/q/112697 1 Quota sampling participants parnas https://cs.stackexchange.com/users/108449 2019-08-12T14:43:45Z 2019-08-14T10:23:31Z <p>We need to select participants, based on the quotas provided. For example:</p> <p>exactly 15 men exactly 15 women</p> <p>exactly 10 young exactly 10 middle aged exactly 10 old</p> <p>exactly 10 poor exactly 10 middle class exactly 10 rich</p> <p>The total number of participants should be exactly 30.</p> <h2>What algorithm should be used to do that?</h2> <p>Simpler, more detailed, example. Let's say that output quota is: 4 people: 2 women, 2 men, 2 old, 2 young.</p> <p>Input set is:</p> <pre><code>Man Young Man Young Man Old Woman Old Woman Young </code></pre> <p>So the matching output set should be:</p> <pre><code>Man Young Man Old Woman Young Woman Old </code></pre> <p>If we'll just start adding people to the output set one by one, skipping those, that would go over the quota, we'll end up with:</p> <p>Man Young Man Young Woman Old</p> <p>We'll have Man Old and Woman Young left, but none of those would match the quota.</p> https://cs.stackexchange.com/q/111792 4 Peculiar MCMC sampling problem Puzzled https://cs.stackexchange.com/users/107538 2019-07-13T16:14:19Z 2019-07-13T16:14:19Z <p>I have two random variables, X and Y, and Y is a positive real number. I can sample from <span class="math-container">$p(y|x)$</span>, but I need to sample from <span class="math-container">$p(x)$</span>, which I know to be proportional to <span class="math-container">$\frac 1 {E[y|x]}$</span>. I could estimate <span class="math-container">$p(x)$</span> from the mean of a lot of samples from <span class="math-container">$p(y|x)$</span> and then use a Metropolis algorithm, but sampling from y isn't cheap, so sampling a lot of them for each step is somewhere between prohibitively expensive and ain't gonna happen. Is there a better way to do this?</p> https://cs.stackexchange.com/q/111697 2 Generate random matrix and its inverse D.W. https://cs.stackexchange.com/users/755 2019-07-10T16:04:02Z 2019-07-11T22:14:06Z <p>I want to randomly generate a pair of invertible matrices <span class="math-container">$A,B$</span> that are inverses of each other. In other words, I want to sample uniformly at random from the set of pairs <span class="math-container">$A,B$</span> of matrices such that <span class="math-container">$AB=BA=\text{Id}$</span>.</p> <p>Is there an efficient way to do this? Can we do it with expected running time approaching <span class="math-container">$O(n^2)$</span>?</p> <p>Assume we are working with <span class="math-container">$n\times n$</span> boolean matrices (all entries 0 or 1, arithmetic done modulo 2). I am fine with an approximate algorithm (say, it samples from a distribution exponentially close to the desired distribution). My motivation is solely curiousity; I have no practical application in mind.</p> <hr> <p>The obvious approach is to generate a random invertible matrix <span class="math-container">$A$</span>, compute its inverse, and set <span class="math-container">$A=B^{-1}$</span>. This has running time <span class="math-container">$O(n^\omega)$</span>, where <span class="math-container">$\omega$</span> is the matrix multiplication constant -- something in the vicinity of <span class="math-container">$O(n^3)$</span> in practice. Can we do better?</p> <p>An approach that occurred to me is to choose a set <span class="math-container">$T$</span> of simple linear transformations on matrices such that, for each <span class="math-container">$t \in T$</span>, we can apply the modifications <span class="math-container">$M \mapsto tM$</span> and <span class="math-container">$M \mapsto Mt^{-1}$</span> in <span class="math-container">$O(1)$</span> time. Then, we could set <span class="math-container">$A_0=B_0=\text{Id}$</span>, and in step <span class="math-container">$i$</span>, sample a random <span class="math-container">$t$</span> from <span class="math-container">$T$</span>, set <span class="math-container">$A_{i+1}=tA_i$</span> and <span class="math-container">$B_{i+1}=B_it^{-1}$</span>, and repeat for some number of steps (say <span class="math-container">$O(n^2 \log n)$</span> iterations). However I'm not sure how we would prove how quickly this approaches the desired distribution.</p> https://cs.stackexchange.com/q/111518 1 Raters and subsampling Jean-Philippe Pellet https://cs.stackexchange.com/users/107278 2019-07-05T11:47:40Z 2019-07-05T11:47:40Z <p>In order to select questions for an online contest, we get contributors to submit potential questions that they write themselves. Then, out of, say 100 submitted questions, we have to rate them and select the best ones, say about 30. Suppose we have 4-5 people willing to help on the final selection task. No one has time to go though all 100 proposals, but can give a grade to a subset (say, 30-35).</p> <p>We can assume those raters are internally consistent (i.e., will always give the same rate to the same question) but not with each other (e.g., there may be a systematic bias between two raters).</p> <p>What algorithms are there to help assign questions to raters and them try to estimate and adjust the biais so as to obtain a maximally consistent global rating without anyone having to read all the questions?</p> https://cs.stackexchange.com/q/110764 0 Algorithm for selecting a sample that's as spread out as possible? Leo Jiang https://cs.stackexchange.com/users/41170 2019-06-16T19:29:58Z 2019-07-17T02:01:30Z <p>I have a large database of data with dates. There are large gaps and large chunks of data without gaps. I want to get a sample of this data such that the dates are as spread out as possible (i.e. as close to evenly distributed as possible).</p> <p>E.g. if the dates are <code>[1, 2, 3, 4, 100]</code> and I want to sample 3 elements, the ideal sample would be <code>[1, 50.5, 100]</code> and the closest available dates are <code>[1, 4, 100]</code>.</p> <p>Is this a known problem with an existing algorithm?</p> https://cs.stackexchange.com/q/110076 2 Sampling in large graph using simple random walk user3322017 https://cs.stackexchange.com/users/106003 2019-05-31T09:29:29Z 2019-06-02T19:11:33Z <p>I'm studying sampling techniques in online social networks. The assumption is we don't have full access to the network(i.e, <strong>we don’t know the size of the network</strong>). However crawling is supported, i.e, starting with any arbitrary node we can access its neighbors. Hence we go for random walk(Markov Chain) based crawling techniques as it requires only neighborhood information for any node. </p> <p>Let's assume we choose simple random walk(SRW) for crawling the network. </p> <p>In SRW we start with an arbitrary seed node then choose one of the neighbors as new node. At the new node we choose one of its neighbors and this process continues. <a href="https://i.stack.imgur.com/NfyHk.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/NfyHk.png" alt=""></a></p> <p>Let G be our graph show in above figure, assume graph is large and <strong>size of the graph is not known</strong>. We go for SRW with node 'A' as initial node.</p> <p><a href="https://i.stack.imgur.com/tQZhu.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/tQZhu.png" alt="enter image description here"></a></p> <p>Since the size of the graph is not known how do we select initial distribution <span class="math-container">$X_0$</span>(at time 0), and initial transition probabilities <span class="math-container">$P_0$</span>(at time 0). After time 0 if I choose one of the neighbors(say B), how the transition probabilities <span class="math-container">$P_1$</span>(at time 1) and distribution <span class="math-container">$X_1$</span>(at time 1) are calculated.</p> https://cs.stackexchange.com/q/105156 3 Sampling numbers from a weighted set that sum to constant value Shubham Chaudhary https://cs.stackexchange.com/users/101253 2019-03-05T06:51:28Z 2019-03-06T01:15:06Z <p>So I have a multi-set of positive integers <span class="math-container">$S = \{n_1, n_2, \dots\}$</span> with associated weights <span class="math-container">$W = \{w_1, w_2, \dots\}$</span>. I want to sample some numbers, without replacement, from <span class="math-container">$S$</span> according to weights <span class="math-container">$W$</span> such that the sampled numbers sum to a given constant positive integer <span class="math-container">$k$</span>.</p> <p>The naive way to do it, as I understand it, is to find out all combinations of numbers from <span class="math-container">$S$</span> that sum to <span class="math-container">$k$</span> and add their weights and choose one of the combinations according to the sum of weights. But doing that is <span class="math-container">$O(|S|^k)$</span>, which is unacceptably large.</p> <p>What I'm doing right now is do a weighted shuffle of <span class="math-container">$S$</span> according to weights <span class="math-container">$W$</span>, and picking number in the obtained order until the requirement is fulfilled. If, for example, the order obtained is <span class="math-container">$3, 2, 3, 2, 1$</span> and <span class="math-container">$k = 4$</span>, then I'll pick <span class="math-container">$3$</span>, ignore <span class="math-container">$2$</span> (as picking it will exceed <span class="math-container">$k = 4$</span>) and pick <span class="math-container">$1$</span>. This approach turns out to be <span class="math-container">$O(n\log\ n)$</span>.</p> <p>Does anyone have a better idea for doing this sampling in a way that is faster than exponential but more robust than what I'm currently doing now?</p> https://cs.stackexchange.com/q/104930 2 Efficient n-choose-k random sampling user101043 https://cs.stackexchange.com/users/101043 2019-02-27T18:37:00Z 2019-02-27T21:05:48Z <p>Is there an efficient method of sampling an n-choose-k combination at random (with uniform probability, for example)?</p> <p>I have read <a href="https://cs.stackexchange.com/questions/79555">this question</a> but it asks for generations of all combinations, not combinations at random.</p> <p>I general I'm aware of rejection sampling, however it's very inefficient.</p> <p>I also came across <a href="https://cs.stackexchange.com/questions/87631">reservoir sampling</a>, but that appears to be primarily geared towards very large or unknown n. I'm more interested in large but finite n (definitely not large enough to not be able to fit in memory. Well. An n-sized array itself will fit in memory, but the state space of all n-choose-k combinations might not).</p> <p>Is there any survey/review on this topic? Does Knuth cover random n-choose-k sampling in his TAOCP texts?</p> <p>Thanks in advance.</p> <p><strong>Edit</strong>: To be a bit more specific, a 5-choose-3 space over the string 'ABCDE' would look like this:</p> <p>['ABC', 'ABD', 'ABE', 'ACD', 'ACE', 'ADE', 'BCD', 'BCE', 'BDE', 'CDE']</p> <p>(Note: this is combination without replacement). And I want to be able to sample from this space with uniform distribution, using a general algorithm (one that works with arbitrary n and k).</p> https://cs.stackexchange.com/q/103041 2 Complexity of generating non-uniform random variates user1494080 https://cs.stackexchange.com/users/14654 2019-01-18T14:06:50Z 2019-01-18T14:30:00Z <p>What can we say about the complexity of generating (negative) binomial and (negative) hypergeometric random variates? In particular, it is possible to generate (negative) binomial and (negative) hypergeometric variates in (expected) constant time (i.e. independent of the distribution parameters)?</p> <p>There is quite a bunch of literature; however, it’s hard to understand a lot of the papers. Moreover, I found some statements that seem contradictory to me (probably due to wrong understanding).</p> <p>For example, <a href="https://www.sciencedirect.com/science/article/pii/0377042790903495" rel="nofollow noreferrer">Stadlober</a> (or similar <a href="https://www.researchgate.net/publication/256371290_Sampling_from_Poisson_binomial_and_hypergeometric_distributions_ratio_of_uniforms_as_a_simple_and_fast_alternative" rel="nofollow noreferrer">here</a>) mentions a "generalization [of the ratio-of-uniforms approach] to any unimodal discrete distribution". The ratio-of-uniforms approach has been called <em>uniformly fast</em>, which is a synonym for constant time, I suppose (?). That would mean that we can generate random variates for each discrete distribution in (expected) constant time.</p> <p>However, in <a href="https://people.mpi-inf.mpg.de/~kbringma/paper/2013ICALP-1.pdf" rel="nofollow noreferrer">another paper</a>, I found the following theorem: On a RAM with word size <span class="math-container">$w$</span>, any algorithm sampling a geometric random variate <span class="math-container">$Geo(p)$</span> with parameter <span class="math-container">$p \in (0,1)$</span> needs at least expected runtime <span class="math-container">$\Omega(1 + \log(1/p)/w)$</span>.</p> <p>Apparently, this means that it is not possible to generate negative binomial variates in time independent of the distribution parameters.</p> https://cs.stackexchange.com/q/100493 3 Efficiently shuffling items in $N$ buckets using $O(N)$ space Tom Zych https://cs.stackexchange.com/users/19400 2018-11-24T11:04:50Z 2018-11-28T21:03:16Z <p>I’ve run into a challenging algorithm puzzle while trying to generate a large amount of test data. The problem is as follows:</p> <ul> <li><p>We have <span class="math-container">$N$</span> buckets, <span class="math-container">$B_1$</span> through <span class="math-container">$B_N$</span>. Each bucket <span class="math-container">$B_i$</span> maps to a unique <strong>item</strong> <span class="math-container">$a_i$</span> and a <strong>count</strong> <span class="math-container">$k_i$</span>. Altogether, the collection holds <span class="math-container">$T=\sum_1^N{k_i}$</span> items. This is a more compact representation of a vector of <span class="math-container">$T$</span> items where each <span class="math-container">$a_i$</span> is repeated <span class="math-container">$k_i$</span> times.</p></li> <li><p>We want to output a shuffled list of the <span class="math-container">$T$</span> items, all permutations equally probable, using only <span class="math-container">$O(N)$</span> space and minimal time complexity. (Assume a perfect RNG.)</p></li> <li><p><span class="math-container">$N$</span> is fairly large and <span class="math-container">$T$</span> is much larger; 5,000 and 5,000,000 in the problem that led me to this investigation.</p></li> </ul> <p>(EDIT: further research instigated by @YuvalFilmus’s comment shows that this is equivalent to <strong>weighted sampling without replacement</strong>, a search term that leads to quite a lot of research.)</p> <p>Now clearly the time complexity is at least <span class="math-container">$O(T)$</span> since we have to output that many items. But how closely can we approach that lower bound? Some algorithms:</p> <ul> <li><p>Algorithm 1: Expand the buckets into a vector of <span class="math-container">$T$</span> items and use <a href="https://en.wikipedia.org/wiki/Fisher-Yates" rel="nofollow noreferrer">Fisher-Yates</a>. This uses <span class="math-container">$O(T)$</span> time, but also <span class="math-container">$O(T)$</span> space, which we want to avoid.</p></li> <li><p>Algorithm 2: For each step, choose a random number <span class="math-container">$R$</span> from <span class="math-container">$[0,T-1]$</span>. Traverse the buckets, subtracting <span class="math-container">$k_i$</span> from <span class="math-container">$R$</span> each time, until <span class="math-container">$R&lt;0$</span>; then output <span class="math-container">$i$</span> and decrement <span class="math-container">$k_i$</span> and <span class="math-container">$T$</span>. This seems correct and does not use extra space. However, it takes <span class="math-container">$O(NT)$</span> time, which is quite slow when <span class="math-container">$N$</span> is large.</p></li> <li><p>Algorithm 3: Convert the vector of buckets into a balanced binary tree with buckets at the leaf nodes; the depth should be close to <span class="math-container">$\log_2{N}$</span>. Each node stores the total count of all the buckets under it. To shuffle, choose a random number <span class="math-container">$R$</span> from <span class="math-container">$[0,T-1]$</span>, then descend into the tree accordingly, decrementing each node count as we go; when descending to the right, reduce <span class="math-container">$R$</span> by the left count. When we reach a leaf node, output its value. It uses <span class="math-container">$O(N)$</span> space and <span class="math-container">$O(T\log{N})$</span> time.</p></li> <li><p>Algorithm 3a: Same as Algorithm 3, but with a <a href="https://en.wikipedia.org/wiki/Huffman_coding" rel="nofollow noreferrer">Huffman tree</a>; this should be faster if the <span class="math-container">$k_i$</span> values vary widely, since the most often visited nodes will be closer to the root. The performance is more difficult to assess, but looks like it would vary from <span class="math-container">$O(T)$</span> to <span class="math-container">$O(T\log{N})$</span> depending on the distribution of <span class="math-container">$k_i$</span>.</p></li> </ul> <p>Algorithm 3 is the best I’ve come up with. Here are some illustrations to clarify it:</p> <p><a href="https://i.stack.imgur.com/wou5R.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/wou5R.png" alt="Illustrations of Algorithm 3"></a></p> <p>Does anyone know of a more efficient algorithm? I tried searching with various terms but could not find any discussion of this particular task.</p> https://cs.stackexchange.com/q/98209 2 Nyquist theorem, sample meaning TomasLife https://cs.stackexchange.com/users/93641 2018-10-06T13:26:54Z 2018-10-06T17:03:59Z <p>Given that this wave was sampled at a sampling frequency <em>f</em>:</p> <p><img src="https://i.imgur.com/R7oFWcn.jpg" alt="1]"></p> <p>Why does the wave sampled at a sampling frequency <em>3f/2</em> look like this?</p> <p><img src="https://i.imgur.com/tElBRqu.png" alt="2]"></p> <p>What does <em>3f/2</em> mean? Does it mean that we sample every 2 waves 3 times?</p> https://cs.stackexchange.com/q/96134 4 Fast sampling from discrete space John T.L https://cs.stackexchange.com/users/92548 2018-08-10T10:31:27Z 2018-08-11T00:46:01Z <p>Assume we are given a set $X = \{x_1,...,x_n \}$ of size $n$, and a probability distribution $P$ over $X$. I am interested in an algorithm $A$ which can sample from $X$ according to $P$, i.e. $\Pr(A=x_i) =p_i$.</p> <p>More specifically, I assume $A$ can generate a uniformly distributed real number in the interval $[0,1]$ in a constant time, and try to characterize the distributions $P$ which can be sampled in $o(|X|)$ time.</p> <p>For example, if $P$ is the uniform distribution, I can assign to each element of $X$ a string from $\{0,1\}^{\log(n)}$, then sample each bit uniformly (toss of a coin) and independently, which means I can sample in $O(\log(n))$ time. Are there distributions such that any algorithm requires $\Omega(|X|)$ time? Are there known results in this direction?</p> https://cs.stackexchange.com/q/95746 0 L1 sampling for sampling edges of a graph sindhuja https://cs.stackexchange.com/users/92121 2018-07-29T10:31:11Z 2018-07-29T10:31:11Z <p>I am trying to sample the edges of an undirected graph using weights. The goal is to run a sparsification algorithm on the graph. I see the point that L1 norm is best for sparsification. Can someone tell me how exactly is L1 sampling performed on edges of a graph.</p> <p>To be more precise with my query, Should we vectorize the indices of the graph and then apply L1 sampling on the sub vectors and perform sparse recovery?(correct me if I am wrong) or is there a better way?</p> https://cs.stackexchange.com/q/94066 3 How to use Latin hypercube sampling with fixed points? HennyKo https://cs.stackexchange.com/users/83893 2018-07-09T12:48:14Z 2018-07-09T16:55:09Z <p>I use Latin hypercube sampling to select what point to evaluate my function. As evaluations take a lot of time, I want to limit the time by adding already evaluated points.</p> <p>I thought about taking the min distance between the points, and if I have an already evaluated point that is near on LHS point, I remove the LHS to minimize the number of evaluations. Sadly this is not how LHS works, and the results are not very good.</p> <p><a href="https://i.stack.imgur.com/zNsyN.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/zNsyN.png" alt="enter image description here"></a></p> https://cs.stackexchange.com/q/93810 0 Sample K representative frames within a video Tina J https://cs.stackexchange.com/users/76164 2018-07-03T14:31:14Z 2018-08-26T10:12:39Z <p>I have an image-based processing module that takes photos for some computer vision processing. I have many videos, but I need to sample representative frames as its inputs, preferably those frames with higher attention.</p> <p>What are some good and effective algorithms or approaches to take K sample frames in a video? Interesting feature is that usually camera doesn't move much in successive frames with higher attention. So basically we have more stable scenes when a person is focusing on something important. Is there any ways to take this into account for our sampling?</p> https://cs.stackexchange.com/q/92466 1 Uniform sampling with constraints John e https://cs.stackexchange.com/users/89092 2018-05-29T11:53:57Z 2018-05-29T13:19:14Z <p>Suppose one wants to uniformly sample a string $w$ of a given length over a finite alphabet, such $w$ satisfies a set of structural constraints (such as - "the third character has to be equal to the first character and the last character has to be equal to the second one").<br> The obvious method is to uniformly sample $w$, check if the constraints hold and return it if so. However, I am dealing with the case where there are many constraints, and the probability of random string to satisfy them is extremely low. Is there a way to sample uniformly from the set of all strings satisfying the set of constraints?</p> https://cs.stackexchange.com/q/91879 1 Backward mapping with bilinear sampler Derpson https://cs.stackexchange.com/users/79552 2018-05-14T02:43:10Z 2018-05-14T15:42:52Z <p>I have some experiences with Convolutional Neural Networks before. I have a question regarding the Bilinear Sampler used in "Unsupervised Monocular Depth Estimation With Left-Right Consistency" (the link to it is provided here: <a href="https://arxiv.org/pdf/1609.03677.pdf" rel="nofollow noreferrer">https://arxiv.org/pdf/1609.03677.pdf</a> and <a href="https://www.youtube.com/watch?v=jI1Qf7zMeIs" rel="nofollow noreferrer">https://www.youtube.com/watch?v=jI1Qf7zMeIs</a>)</p> <p>I understand that the author had made the convolutional neural network predict the disparity map of the left image, then uses the disparity map to transform the right image back into the predicted left image. </p> <p>However, I don't understand how the transformation is done (shown in 5:35 in the youtube video, and "Our network generates the predicted image with backward mapping using a bilinear sampler, resulting in a fully differentiable image formation model").</p> <p>I understand that the system needs to be fully differentiable so that backpropagation can be used, and I understand that Spatial Transformer Networks can map images from a transformed grid, but I cannot understand how the bilinear sampler in the spatial transformer network is used to transform the right view image into a left view image given the left disparity map. In particular, in spatial transformer networks, the sampling stage requires a set of sampling points (which is a 2x3 matrix) and an image so that it can sample a new image from the old one. However, in the depth estimation paper, I can't understand how they extract the set of sampling points (the 2x3 matrix) from the disparity map. How does that work?</p> https://cs.stackexchange.com/q/91874 0 Testing two distributions, both accept null hypothesis oldboy123 https://cs.stackexchange.com/users/85352 2018-05-13T22:39:57Z 2018-05-14T00:51:36Z <p>I have a sample that is collected to verify the accuracy of a new random number generator. Applying the goodness of fit test to check if this sample comes from the Standard Normal Distribution and Uniform Distribution, I found out that both of these accept null hypothesis although they are contradicting to each other. Is it theoretically possible? Why?</p> https://cs.stackexchange.com/q/89912 2 Limit repetitions in randomized list with each unique element occurring n times Adrian https://cs.stackexchange.com/users/86385 2018-03-28T13:25:03Z 2018-03-29T22:23:59Z <p>I have a set of 3 elements and need to generate a randomized sequence containing each element n times with the condition that one element can only occur m times in a row.</p> <p>So with elements [0,1,2] n = 4 and m = 3:<br> [1, 2, 0, 0, 0, 1, 1, 2, 2, 2, 0, 1] valid<br> [1, 2, 0, 0, 0, 0, 1, 2, 2, 2, 1, 1] invalid </p> <p>The only solutions I found were to add all elements n times to a list and then shuffle until the condition is satisfied or generate the whole search space and then randomly sample from the correct solutions. Both seem possibly slow and memory intensive.<br> Could just be looking for the wrong terms, this has to be documented somewhere.</p> <p>I came up with this approach, but am not sure about correctness.</p> <pre><code>E: set of elements e n: of each element in sequence m: maximum repetitions of one element S = [] # empty sequence while |S| &lt; |E| * n: R = shuffled list containing each e m times for m: if s+r satisfies condition: S &lt;- s+r # Extend s with r else: rotate r by one element return the first |E| * n elements of S </code></pre> <p>It <em>seems</em> to produce correct results, but is it ok to sample and then rotate the subsequences R like that?<br> Would the time complexity be just O(|E| * n * m)?</p> <p>Here is my python implementation: </p> <pre><code>def generate_sequence(e, n, m): # Final sequence s = [] # Extend s by n * len(elements) each iteration for _ in range(n//m+1): r = list(e) * m random.shuffle(r) for _ in range(len(r)): # List of all windows of size m+1 where at least one element is from s or r. windows = filter(lambda x: len(x) == m + 1, [s[-i:] + r[:(m + 1 - i)] for i in range(1, m + 1)]) # check if any window contains an invalid sequence if not all(len(set(window)) &gt; 1 for window in windows): # rotate r one to right r = [r[-1]] + r[:-1] else: # Valid s+r s.extend(r) break return s[:len(list(e)) * n] </code></pre> https://cs.stackexchange.com/q/89394 2 Constrained selection of a random sample from a set of items with multiple attributes Anne Hanna https://cs.stackexchange.com/users/85764 2018-03-16T00:02:57Z 2018-03-16T01:07:47Z <p>Suppose I have a collection of <em>N</em> items, each of which has <em>A</em> different attributes, <em>a<sub>1</sub></em>, <em>a<sub>2</sub></em>, ..., <em>a<sub>A</sub></em>. Attribute a<sub>i</sub> can take on <em>V<sub>i</sub></em> different possible (discrete) values, distributed across the population with some kind of complicated joint probability <em>&phi;(a<sub>1</sub>, a<sub>2</sub>, ..., a<sub>A</sub>)</em>. It is quite likely that many possible combinations of attributes are either extremely rare in or entirely absent in my collection.</p> <p>Now suppose I want to draw a sample of <em>S</em> items from my collection, and I want my final sample to satisfy a set of aggregate constraints, each having the form <em>l<sub>ij</sub> &le; S<sub>ij</sub> &le; u<sub>ij</sub></em>, where <em>S<sub>ij</sub></em> is the number of items in the sample for which attribute <em>a<sub>i</sub></em> takes on its <em>j</em>th value.</p> <p>What I'd like to find is an efficient way to do the following things:</p> <ol> <li>Determine for certain whether or not there exists a possible sample from my collection that satisfies the constraints.</li> <li>Get at least a rough idea of what fraction of possible samples from the collection will satisfy the constraints.</li> <li>Efficiently select such a sample at random. In particular, if only a very small fraction of possible samples will satisfy the constraints, I'd like a good way to do some kind of pre-filtration on the space I sample from, to reduce the number of random samples I have to draw before I get one that satisfies my constraints. Since the space of possible samples is quite large, exhaustively enumerating possibilities and filtering for satisfactory ones is not a reasonable option.</li> </ol> <p>I don't have a lot of domain knowledge in this area, so even suggestions of better terminology for expressing this issue would be helpful.</p> https://cs.stackexchange.com/q/83863 1 Randomly choose a line - algorithm Maria https://cs.stackexchange.com/users/80139 2017-11-13T18:38:10Z 2017-11-13T21:57:01Z <p>We have a large file that can't fit into internal memory. How do we randomly pick one line so that each line has the same probability to be picked? </p> <p>And how do we randomly pick such n lines so that they all have the same probability?</p> <p>We don't know the number of lines beforehand.</p> <p>Any hint on where to start solving this, which algorithm to use, or at least an idea where to start would be appreciated.</p> https://cs.stackexchange.com/q/83540 5 How to select a binary tree node uniformly at random justin https://cs.stackexchange.com/users/79826 2017-11-06T21:55:46Z 2017-11-07T12:25:38Z <p>The exercise I'm trying to solve is</p> <blockquote> <p>You are implementing a binary search tree class from scratch, which, in addition, to insert, find and delete, has a method <code>getRandomNode()</code> which returns a random node from the tree. All nodes should be equally likely to be chosen. Design and implement an algorithm for <code>getRandomNode()</code>, and explain how you would implement the rest of the methods. </p> </blockquote> <p>The answer from the book is:</p> <pre><code> 1 class TreeNode { 2 private int data; 3 public TreeNode left; 4 public TreeNode right; 5 private int size = 0; ... 12 public TreeNode getRandomNode() { 13 int leftSize = left == null ? 0 : left.size(); 14 Random random = new Random(); 15 int index = random.nextInt(size); 16 if (index &lt; leftSize) { 17 return left.getRandomNode(); 18 } else if (index == leftSize) { 19 return this; 20 } else { 21 return right.getRandomNode(); 22 } 23 } ... 55 } </code></pre> <p>But here is the problem. With this algorithm, I don't see how nodes are equally likely to be chosen. In line 16, it says if <code>leftsize &gt; index,</code> where <code>index</code> is a number from 0 to <code>size</code>, then the algorithm will continue with the left node, otherwise the right node. It only works when the tree has a depth of 2. When the tree is taller, the probability of each node being chosen will not be equal. </p> <p>Am I wrong? Does this algorithm work? </p> https://cs.stackexchange.com/q/81863 1 What is the relationship between entropy rate and quantization? Paul Uszak https://cs.stackexchange.com/users/31167 2017-09-29T12:38:54Z 2017-09-29T12:38:54Z <p>I have a totally random source of signal data that looks like a typical normal distribution. I've included an image as I like pictures:-</p> <p><a href="https://i.stack.imgur.com/mDwJw.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/mDwJw.png" alt="normal"></a></p> <p>The source has a mean of 0, and a standard deviation of 1. It's analogue and therefore of infinite resolution. Very typical.</p> <p>I then sample the signal with a Tricorder and record the raw data. Clearly as the original signal is random, irreducible information entropy is accrued at some rate, and will be smaller (in bits) than the raw data. My particular Tricorder model has a sample resolution setting, so for example I can record at anything from 1 bit resolution /sample to say 48 bits /sample. You might think of this as a quantization setting.</p> <p>The crux of my question is: what is the relationship between the recorded entropy rate and the level of quantization? I'm hoping for either a formula or an example calculation such as 4.5 bits /sample with 10 bit quantization. </p> <p>There is (perhaps) a similar question at <a href="https://cs.stackexchange.com/questions/20156/compressing-normally-distributed-data">Compressing normally distributed data</a>, but I'm not sure and it doesn't really deal with sample bit depth in the same way. I'm developing the argument that real world entropy is generated by the observer, not the underlying process.</p> <p>PS. Read analogue to digital converter for Tricorder.</p> https://cs.stackexchange.com/q/81861 5 Bilinear Interpolation user2835098 https://cs.stackexchange.com/users/77945 2017-09-29T12:10:06Z 2017-09-30T11:38:54Z <p>I am trying to implement bilinear interpolation as described in the paper <strong>Spatial Tranformer Networks</strong> by <em>Jaderberg et. al</em> (see <a href="https://arxiv.org/pdf/1506.02025.pdf" rel="nofollow noreferrer">link to paper</a>). They describe bilinear interpolation in Equation 5 as:</p> <p>$$V_i^c = \sum_{n}^{H}\sum_{m}^{W} U_{nm}^c \max(0,1-|x_i^s - m|)\cdot\max(0,1-|y_i^s - n|),$$ where:</p> <ul> <li>$V_i^c$ is the resulting pixel value in the new image</li> <li>$H$ and $W$ are the height and width of the original image (or feature map) in pixels</li> <li>$c$ refers to the channel (e.g. RGB)</li> <li>$(x_i^s, y_i^s)$ are the coordinates where the original image is sampled (where the image is normalized such that $-1 \le x_i^s, y_i^s\le 1$)</li> <li>$U_{nm}^c$ is defined as the pixel value at location $(n,m)$ in channel $c$.</li> </ul> <p>I am having trouble interpreting the variables $n$ and $m$. Are these</p> <ul> <li>coordinates in the normalized image (i.e. $-1 \le n, m\le 1$, where you would sum $n$ from $n=-1$ to $H=1$ in steps of the normalized resolution, e.g. steps of $1/100$ for an image that is 100 px in height)</li> <li>or are these row and column values (e.g. you sum $n$ from $n=0$ to $n=100$ for an image that is 100px in height)?</li> </ul> <p>I have tried out both to do downsampling of an image, but don't get consistent results.</p> <p>If someone can help me out interpreting this, I would appreciate it very much.</p> <p>Below I have included what I understand of bilinear interpolation. Maybe that someone can help me out based on this.</p> <hr> <p>In the below figure, a single channel feature map (or image) with one channel is displayed that consists of four pixels with values $U_{nm}$, where $n$ and $m$ are the coordinates of the center of the pixels, i.e. $m,n \in \{-0.5, 0.5\}$. If we index $m$ and $n$ as $m_k, n_k$, with $k \in [1,4]$, we can also index the pixel values as $U_{n_km_k}$. The values of all four pixels can be reduced to a single value $V$ at position $(x_i^s, y_i^s)$ by applying bilinear interpolation. <a href="https://i.stack.imgur.com/m5tiS.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/m5tiS.png" alt="Bilinear Interpolation"></a></p> <p>The procedure can be divided into three linear interpolations. First the value $U_1'$ at position $(x_{U_1'}, y_{U_1'})$ can be computed by interpolating the values $U_{n_1m_1}$ and $U_{n_2m_2}$: \begin{equation} U_1' = \Delta x_2\ U_{n_1m_1} + \Delta x_1\ U_{n_2m_2}. \end{equation} As the sum of $\Delta x_1$ and $\Delta x_2$ is equal to one, due to normalization of the axes, the above equation can be rewritten as: \begin{equation} U_1' = (1-\Delta x_1) U_{n_1m_1} + (1-\Delta x_2) U_{n_2m_2}. \end{equation} The terms $\Delta x_1$ and $\Delta x_2$ can be expressed as: \begin{align} \Delta x_1 = |x_i^s - {m_1}|\\ \Delta x_2 = |x_i^s - {m_2}|, \end{align} which, substituted into the equation for $U_1'$ yields: \begin{equation} U_1' = U_{n_1m_1}(1-|x_i^s - {m_1}|) + U_{n_2m_2}(1-|x_i^s - {m_2}|). \end{equation}</p> <p>Similarly the value for $U_2'$ can be computed: \begin{equation} U_2' = U_{n_3m_3}(1-|x_i^s - {m_3}|) + U_{n_4m_4}(1-|x_i^s - {m_4}|). \end{equation}</p> <p>Once $U_1'$ and $U_2'$ have been computed, $V$ can be determined by linearly interpolating $U_1'$ and $U_2'$: \begin{equation} V = U_1'(1-\Delta y_1) + U_2'(1-\Delta y_2) . \end{equation} The values for $\Delta y_1$ and $\Delta y_2$ can be expressed as follows: \begin{align} \Delta y_1 = |y_i^s - y_{U_1'}| = |y_i^s - {n_1}| = |y_i^s - {n_2}|\\ \Delta y_2 = |y_i^s - y_{U_2'}| = |y_i^s - {n_3}| = |y_i^s - {n_4}| . \end{align}</p> <p>Substituting the above equations and those of $\Delta x_1$ and $\Delta x_2$ into the equation for $V$ yields: \begin{equation} \begin{split} V &amp;= U_{n_1m_1}\cdot (1-|x_i^s - {m_1}|) \cdot (1-|y_i^s - {n_1}|) \\ &amp;+ U_{n_2m_2}\cdot (1-|x_i^s - {m_2}|) \cdot (1-|y_i^s - {n_2}|) \\ &amp;+ U_{n_3m_3}\cdot (1-|x_i^s - {m_3}|) \cdot (1-|y_i^s - {n_3}|) \\ &amp;+ U_{n_4m_4}\cdot (1-|x_i^s - {m_4}|) \cdot (1-|y_i^s - {n_4}|), \end{split} \end{equation} which can be written more compactly as: \begin{equation} \begin{split} V &amp;= \sum_{k=1}^{4} U_{n_km_k} \cdot (1-|x_i^s - {m_k}|) \cdot (1-|y_i^s - {n_k}|)\\ &amp;=\sum_{n}^{H}\sum_{m}^{W} U_{nm} \cdot (1-|x_i^s - {m}|) \cdot (1-|y_i^s - {n}|). \end{split} \end{equation}</p> <hr> <p><strong>Edit to clarify my comment to @D.W.</strong></p> <p>Initially I also thought that $n$ and $m$ are row and column indices as you normally do a summation over integer values. Also the summation is up to $H$ and $W$, respectively, which are the # of rows and # of columns. So it seems logical to think that $\sum_{n=1}^{H = \#rows}\sum_{m=1}^{W = \#columns}$, with $n=1,2,3,...,H$ and $m=1,2,3,...,W$. </p> <p>However, when you apply it in this way, the terms within the summation will always be zero. This is because of the condition $-1 \le x_i^s, y_i^s \le 1$. Taking the example in the figure where $(x_i^s, y_i^s) = (-0,25, 0,25)$, we have: \begin{equation} \begin{split} V &amp;= \sum_{n}^{H}\sum_{m}^{W} U_{nm}\cdot \max(0, 1-|x_i^s-m|)\cdot \max(0, 1-|y_i^s-n|) \\ &amp;= U_{11}\cdot \max(0, 1-|-0.25-1|)\cdot \max(0, 1-|0.25-1|)\\ &amp;+ U_{12}\cdot \max(0, 1-|-0.25-2|)\cdot \max(0, 1-|0.25-1|)\\ &amp;+ U_{21}\cdot \max(0, 1-|-0.25-1|)\cdot \max(0, 1-|0.25-2|)\\ &amp;+ U_{22}\cdot \max(0, 1-|-0.25-2|)\cdot \max(0, 1-|0.25-2|)\\ &amp;= U_{11}\cdot 0 + U_{12}\cdot 0 + U_{21}\cdot 0 + U_{22}\cdot 0= 0 \end{split} \end{equation} When you have $n$ go from $n=0$ to $H-1$ (and similarly for $m$), it does work in this (simple) example, which would lead to concluding that $n$ and $m$ should start from zero.</p> <p>However, when you try to apply this to an image which is larger than 2x2 pixels, you get a similar problem than the one for $n=1, ..., H$, i.e. all elements within the summation will be zero when $n&gt;0$ and $m&gt;0$.</p> <p>To clarify this, look at the below image. Here the original image is an 8x8 image with pixels depicted by black squares. We wish to downsample the image to a 6x6 image, depicted by the dashed red squares. If we want to compute the value of the pixel marked by the pink star with coordinates $(x_1^s, y_1^s) = (-0.833, 0.833)$, we would have: \begin{equation} \begin{split} V_{1} &amp;= \sum_{n}^{H}\sum_{m}^{W} U_{nm}\cdot \max(0, 1-|x_1^s-m|)\cdot \max(0, 1-|y_1^s-n|) \\ &amp;= U_{00}\cdot \max(0, 1-|-0.833-0|)\cdot \max(0, 1-|0.833-0|)\\ &amp;+ U_{01}\cdot \max(0, 1-|-0.833-1|)\cdot \max(0, 1-|0.833-0|)\\ &amp;+ U_{02}\cdot \max(0, 1-|-0.833-2|)\cdot \max(0, 1-|0.833-0|)\\ &amp;+ ...\\ &amp;+ U_{10}\cdot \max(0, 1-|-0.833-0|)\cdot \max(0, 1-|0.833-1|)\\ &amp;+ U_{11}\cdot \max(0, 1-|-0.833-1|)\cdot \max(0, 1-|0.833-1|)\\ &amp;+ ...\\ &amp;+ U_{77}\cdot \max(0, 1-|-0.833-7|)\cdot \max(0, 1-|0.833-7|)\\ &amp;= U_{00}\cdot 0.167^2 + U_{10}\cdot 0.167\cdot 0.833, \end{split} \end{equation} which is only a function of $U_{00}$ and $U_{10}$ and not of $U_{00}$, $U_{01}$, $U_{10}$ and $U_{11}$ as one would reason.</p> <p>If we look at the blue star with coordinates $(x_{49}^s, y_{49}^s) = (0.833, -0.833)$ and apply the same equation, we have: \begin{equation} \begin{split} V_{49} &amp;= \sum_{n}^{H}\sum_{m}^{W} U_{nm}\cdot \max(0, 1-|x_{49}^s-m|)\cdot \max(0, 1-|y_{49}^s-n|) \\ &amp;= U_{00}\cdot \max(0, 1-|0.833-0|)\cdot \max(0, 1-|-0.833-0|)\\ &amp;+ U_{01}\cdot \max(0, 1-|0.833-1|)\cdot \max(0, 1-|-0.833-0|)\\ &amp;+ U_{02}\cdot \max(0, 1-|0.833-2|)\cdot \max(0, 1-|-0.833-0|)\\ &amp;+ ...\\ &amp;+ U_{10}\cdot \max(0, 1-|0.833-0|)\cdot \max(0, 1-|-0.833-1|)\\ &amp;+ U_{11}\cdot \max(0, 1-|0.833-1|)\cdot \max(0, 1-|-0.833-1|)\\ &amp;+ ...\\ &amp;+ U_{77}\cdot \max(0, 1-|0.833-7|)\cdot \max(0, 1-|-0.833-7|)\\ &amp;= U_{00}\cdot 0.167^2 + U_{01}\cdot 0.833\cdot 0.167, \end{split} \end{equation} which again is only function of $U_{00}$ and $U_{01}$ and not of $U_{66}$, $U_{67}$, $U_{76}$ and $U_{77}$ as one would expect.</p> <p>I have also tried normalizing $n$ and $m$, such that $n =-1, -1+ 2/8, -1 +4/8, ..., 1$ (and similarly for $m$, but I end up with similar problems. <a href="https://i.stack.imgur.com/UOONG.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/UOONG.png" alt="New image"></a></p> https://cs.stackexchange.com/q/80611 1 Strength-based player cards sampling [closed] Brans Ds https://cs.stackexchange.com/users/61401 2017-08-29T21:39:55Z 2017-08-30T11:15:16Z <p>Let's say we have a card game, like poker. Inputs are board cards and an array of cards strength(that is calculated based on the board cards and game rules). </p> <p>For example for 3 ranks(A, K, Q) /2 suits(h,s) simplified poker(Leduc) with Qs on board as input we will have a strength array [2, 2, 1, 1, -1, 3] indexes are [As, Ah, Ks, Kh, Qs, Qh]. The highest strength has Qh because pair wins, then aces and kings. -1 means that Qs is impossible because it is on board already.</p> <p>We need to sample vectors of player ranges - probabilities that player holds each possible hand. We are using this vectors to train some machine learning algorithm to play with this cards.</p> <p>On the average for the example above we should sample Qh with the same probability as As + Ah and Ks + Kh. For this example, it is ideally to get [1/6, 1/6, 1/6, 1/6, 0, 1/8] as a result.</p> <p>So we need to split input array onto the strength "clusters" and split probability between them and then divide each cluster probability by the number of elements in that cluster. But how to define such clusters? What algorithm can you suggest for this task?</p> <hr> <p>Update: Here the procedure that is used by Alberta University for the "generating pseudo-random ranges that attempt to cover the space of possible ranges"</p> <p>We used a recursive procedure R(S, p), that assigns probabilities to the hands in the set S that sum to probability p, according to the following procedure.</p> <blockquote> <p>If |S| = 1, then Pr(s) = p. </p> <p>Otherwise,</p> <p>(a) Choose p1 uniformly at random from the interval (0, p), and let p2 = p − p1.</p> <p>(b) Let S1 ⊂ S and S2 = S \ S1 such that |S1| = |S|/2 and all of the hands in S1 have a hand strength no greater than hands in S2. Hand strength is the probability of a hand beating a uniformly selected random hand from the current public state.</p> <p>(c) Use R(S1, p1) and R(S2, p2) to assign probabilities to hands in S = S1 ∪ S2.</p> </blockquote> <p>Also, I have looked at their implementation one note is that if we have an odd number of cards middle card goes to randomly to the left or right subsets.</p> <p>But the real results of this algorithm looks strange: For the example above average cars sampling probability: [0.185,0.189,0.185,0.220,0, 0.219]</p> <p>For the empty board: [0.19,0.12,0.19,0.19,0.12, 0.19] = [3/8, 1/8, 3/8, 3/8, 1/8, 3/8]. Not uniform because of an odd number of cards(6/2 = 3) on the second iteration. The results look not very good and accurate. Is this a best that we can achieve?</p> https://cs.stackexchange.com/q/79986 2 Why do we need Gibbs sampling (and MCMC)? Covvar https://cs.stackexchange.com/users/72341 2017-08-12T15:42:05Z 2017-08-12T22:22:30Z <p>I just learned about Gibbs Sampling which is an MCMC method. Given a distribution $\pi$, we want to sample an item according to $\pi$.</p> <p>Maybe my alternative suggestion would sound somewhat naive (even stupid) but why can't we just draw a number in random from $[0,M]$ for some sufficiently large enough $M$. Then, we divide the range to buckets with appropriate sizes according to the distribution. </p> <p>This will be a true sampling of $\pi$. </p> <p>One could argue that my suggestion demands a PRNG, but Gibbs Sampling uses randomness too when deciding the next state from the neighbors of the current state.</p> <p>So for a reasonable distribution, wouldn't my suggestion work way better? It's essentially $O(1)$ and accurate.</p> https://cs.stackexchange.com/q/76619 2 Finding the (probable) maximum of a large set of integers *without* iterating over all of the values R. Granton https://cs.stackexchange.com/users/73471 2017-06-10T13:35:35Z 2017-06-11T16:24:37Z <p>As in the title, I am trying to find the largest (aka least upper bound) of a (very large) set of integers. Importantly, I do not have direct access to the full list of integers, but I do have a function $f(n)$ which returns true/false if $n$ is in the set. The function $f(n)$ is expensive and I would like to minimize the number of calls I must make to it.</p> <p>The integers might or might not be consecutive, or have large gaps between them (i.e. might be sparse or dense). There is no prior-known upper bound on the largest integer in the set, which can go off to infinity in theory.</p> <p>Is there a well-trodden algorithm for doing this? My inkling is to do some kind of random sample to determine the density, and then try to find the upper bound within some certainty. I'm not sure how to bound my initial sample properly then though, or which distribution I might assume the integers have based on that sample.</p> <p>Thanks.</p> https://cs.stackexchange.com/q/72332 1 Sampling among constrained partitions Seb Destercke https://cs.stackexchange.com/users/35991 2017-04-01T09:10:35Z 2017-04-01T09:59:28Z <p>I'm working on a clustering problem and want to sample partitions (possible clustering solutions) among a set of constrained ones. </p> <p>Here is the problem: I have a set of objects $O=\{o_1,\ldots,o_n\}$ and would like to sample among reflexive, symmetric and transitive relations $R \in O \times O$ such that samples satisfy a set of must-link/cannot-link constraints. More specifically, I do have for some pairs $o_i,o_j$ either that $(o_i,o_j) \in R$ or $(o_i,o_j) \not\in R$. Alternatively, I could see it as the problem of sampling graphs that are disjoint cliques with pre-specified arcs or absences or arcs. </p> <p>Reject sampling is likely to not work in practice, as the number of rejection would quickly be prohibitive as n and the set of constraints get high enough (something we can expect). </p> <p>Do any of you know if this problem has been treated, or any easy way to solve it? Uniformity within the set of samples is desirable, but not absolutely necessary. </p> <p>Thanks.</p> https://cs.stackexchange.com/q/71440 3 Sampling from a set of numbers with a fixed sum Soheil https://cs.stackexchange.com/users/67654 2017-03-12T19:02:12Z 2017-03-12T20:15:22Z <p>Let $s = \{x_1, x_2, \ldots, x_n\}$ be a set of $n$ random non-negative integers where $\sum_i x_i = n$. And let $\{y_1, y_2, \ldots, y_{\sqrt{n}}\}$ denote a subset of size $\sqrt{n}$ of $s$, chosen uniformly at random. Defining $y$ to be $\sum_i y_i$ I am interested in calculating the value of $y$.</p> <p>By linearity of expectation, I know $E[y] = \sum_i E[y_i] = \sqrt{n}$. But can I prove with high probability that $y$ is close to its mean?</p> <p>I tried using Chernoff bound but unfortunately since $x_i$'s and therefore $y_i$'s are not independent, I can't apply it here.</p> <p>I also tried using Chebyshev's inequality since $y_i$'s seem to be negatively correlated but I can't calculate the variance of $y_i$ and the proof would be messy even if I do.</p> <p>Does anyone have any idea for a simpler proof? </p> https://cs.stackexchange.com/q/70640 2 Randomly select a uniform subsample from a nonuniform dataset thegreatemu https://cs.stackexchange.com/users/66753 2017-02-22T01:36:33Z 2017-02-22T21:12:04Z <p>I have a dataset of events with timestamps spanning several months. The event rate is "bursty", i.e. there are periods of much higher and lower rate than the average. I would like to randomly select a subset of these events having approximately uniform time distribution. What weight should be applied to the random sampling? </p> <p>One approach I've already considered is to histogram the data and weight samples by 1/binheight, but this ends up being dependent on the binning chosen and runs into problems with very sparse samples. </p> <p>Can the appropriate method also be extended to another, possibly related parameter? For example, I may have a unix timestamp (1 second resolution) and another parameter measuring phase of the 60 Hz AC power line. My subsample should be uniform in both dimensions. </p>