Skip to main content

Questions tagged [statistics]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2 votes
2 answers
49 views

Information content of a real number

Suppose I have a sequence of 5 IID Bernoulli variables, with probability of having value 1 being 0.5. If we observe an instance of the sequence, the information content would be 5 bits, as each ...
Ishan Kashyap Hazarika's user avatar
1 vote
1 answer
22 views

Best internal representation of a random variable to enable iterative sampling and interpolation/regression

Let $[0,100]$ denote the interval of real numbers between $0$ and $100$. Given a function $f:[0,100]^n \rightarrow \mathbb{R}^+$, I want to implement the following simple algorithm to search for the ...
EXPTIME-complete's user avatar
1 vote
1 answer
80 views

Impact of label flipping on ROC-AUC score

I was exploring a problem of label flipping in the target column: Problem: I have a data frame with just two columns: Predicted probability | Target. Target column is binary (contains only 0 and 1) ---...
Grigori's user avatar
  • 105
0 votes
2 answers
220 views

Minimum number of comparisons to find $2$nd smallest element

Show that the second smallest of $n$ elements can be found with $n+\lceil\lg n\rceil-2$ comparisons in the worst case. (Hint: Also find the smallest element.) [1] I tried but I have no idea how to, e....
C.C.'s user avatar
  • 159
0 votes
1 answer
48 views

Finding the mode of a continuous distribution

I need to find the empirical mode of a sample of numbers taken from a continuous distribution (i.e. floating-point data). I can think of using an histogram, but choosing an appropriate bin size does ...
user avatar
2 votes
0 answers
32 views

Sample Complexity Lower bound for PCA

I am trying to find (without success) a sample complexity lower bound for PCA. The concrete problem I am considering is - $X_{1}, X_{2}, \cdots X_{n} \sim D(0, \Sigma)$ are $d$-dimensional vectors ...
Syamantak Kumar's user avatar
-1 votes
1 answer
88 views

How to calculate the growth function of a hypothesis class?

I have this hypothesis class: H = {ha : R → {0, 1} | a > 0, a ∈ R, where ha(x) = 1−a,a = { 1, x ∈ [−a, a] 0, x ̸ ∈ [−a, a] } I need to compute the growth function for m>= 0. So I think that this ...
anonymus's user avatar
0 votes
2 answers
93 views

Bucket sort for gaussian / standard distribution

I know this post. But I still have no idea to adapt the bucket sort algorithm to handle input with a gaussian / normal distribution. Can someone provide me a Pseudocode / Python code for that? So far ...
Titanlord's user avatar
  • 121
1 vote
3 answers
215 views

What set.seed() mean in the Monte Carlo method

I'm trying to learn the implementation of the Monte Carlo method in R language. I am following a course with an example of predicting results for a board game. What I'm not understanding is the usage ...
Lyra Dobruna's user avatar
1 vote
2 answers
129 views

Why use Welford's Method over a more naive approach?

I came across this pair of blog posts explaining the problem with calculating variance on floating point data: https://jvns.ca/blog/2023/01/13/examples-of-floating-point-problems/#example-3-a-variance-...
fpf3's user avatar
  • 111
0 votes
0 answers
32 views

How to create random pseudo samples from a non-stationary time series containing NaNs using Monte-Carlo method?

I am looking for answers creating 500 samples of non-stationary Time series based on its probability distribution preferably using monte-carlo simulation. DATA LINK Secondly, the most example ...
shewag's user avatar
  • 1
1 vote
1 answer
74 views

Efficient algorithm for finding linear combination of piecewise functions

While porting an algorithm, I having a bit of a problem with finding an efficient algorithm for finding a linear combination of piecewise functions. The procedure is described in the Table 3 of the ...
RikH's user avatar
  • 113
1 vote
1 answer
43 views

Naïve array sampling algorithm: the possibility of a item being chosen and its time complexity

This naïve sampling algorithm I am talking about is fairly simple: create a set for storing chosen items first, randomly select an item from the array, and examminate if it is in the set. If it isn't, ...
Stephen.W's user avatar
  • 111
0 votes
0 answers
31 views

Tight bounds for expected maximum of k binomial(n,p) IIDs

What is the tightest lower and upper bound for the expected maximum value of k IID Binomial(n, p) random variables I tried to derive it : $$Pr[max \leq C] = (\sum_{i = 0}^C {n \choose i}p^i(1 - p)^i)^...
Goli Emami's user avatar
1 vote
1 answer
33 views

Distribution maximizing ratio of expected maximum over the mean

I’m looking for a distribution that is non-negative, or has good tail bounds (so non-negative with high probability) and maximizes the ratio between the expected maximum of $n$ iid samples and the ...
Goli Emami's user avatar
3 votes
0 answers
68 views

Algorithm for half-sample mode better than O(N^2)

The half-sample mode is a mode estimator that homes in on the highest density region of a set of samples in search of the mode. It is one of the better mode estimators, though it fails for J-shaped ...
Paul Chernoch's user avatar
1 vote
0 answers
43 views

Precise definition of Universal Learner in Machine Learning

It is surprising to me that I cannot find a precise definition of universal learner on the internet. I can guess what it should bebut I don't want to make a mistake, therefore I have come here. Here's ...
Suraj's user avatar
  • 11
1 vote
0 answers
110 views

Hoeffding's inequality applicability for sample complexity

I am trying to determine some bounds for sample complexity. Suppose we have a bounded loss function $\ell$ and target function $f:\mathcal{X}\to\mathcal{Y}$. Hypothesis $h$ is learned, then the ...
somefellow's user avatar
1 vote
0 answers
155 views

Computational complexity of median filter in image processing

I found this paper http://nomis80.org/ctmf.pdf, that describes an efficient algorithm for applying a median filter to an image. Though this works for non-HDR images, I am not sure how well it scales ...
user877329's user avatar
4 votes
2 answers
974 views

What empirical evidence do we have for or against a correlation between fault density and LOC?

LOC = lines of code KLOC = Thousand lines of code Fault (or defect) density = number of reported bugs per line of code. Software artifact = function, class, module Reading research papers on fault ...
Olle Härstedt's user avatar
0 votes
1 answer
102 views

Efficient random sampling from large discrete distribution

I have a random variable $X$ that can take finite values in $\{X_1, ..., X_n\}$ with probabilities $\{p_1,..., p_n\}$. Is there a computationally efficient way to sample a number from this set? My ...
andysark's user avatar
1 vote
0 answers
13 views

Distributed Graph Consensus to fit a distribution?

$G$ is a strongly connected graph with nodes $V$ and edges $E$. Each node $v_i$ receives a sample $x_i$ from a Gaussian $\mathcal{N}(\mu,\sigma^2)$ with unknown mean and variance. The objective is for ...
chausies's user avatar
  • 532
1 vote
0 answers
23 views

Distribution independence property testing

I have been reading the proof in the following paper, and I am unable to understand some parts in the proof. This paper shows that a distribution $A$ over $[n]\times[m]$, $n\geq m$, can be $\epsilon$-...
user141088's user avatar
1 vote
2 answers
781 views

Sliding window max/min algorithm without dynamic allocations

I'm working on a suite of DSP tools in Rust, and one of the features of the library is a collection of windowed statistics (mean, RMS, min, max, median, etc) on streams of floating-point samples. For ...
Mark LeMoine's user avatar
1 vote
1 answer
53 views

EM algorithm - What happens with the standard deviation?

What have you tried? So I watched this video. According to the video, we've to calculate the variance $\sigma^2$ as follows: $$ \sigma_{k}^{2} = \frac { p_{1} \left(x_{1} -...
TornaxO7's user avatar
  • 121
0 votes
1 answer
43 views

PCA applicability

I understand that PCA takes a data set with input size, with output labels, and reduces the inputs to a set of principal components size r, where r < n. My question is whether or not this can be ...
Jeffery's user avatar
0 votes
0 answers
146 views

Most popular path in weighted cylic directed graph

Context I have a graph $G=(V,E)$ with weighted edges, all weights are positive integers $w(e)\in\mathbb{N}\setminus\{0\}$. The weights represent the popularity/count of each edge, for example $w(e) = ...
NoVariation's user avatar
1 vote
1 answer
358 views

Approximate max weight path in directed graph

Context This question is related to the fact one can't use Bellman-Ford to find max weight paths in directed graphs with cycles. The reason is that giving a new graph $\tilde{G}$ with negative weights ...
NoVariation's user avatar
0 votes
1 answer
320 views

Chebyshev’s inequality problem in one exercises I can't understand if I did it right or not

This is what do I have to solve: Byron Book: Exercise 8.3 chapter 8 Verify the use of Chebyshev’s inequality in (8.6) of Example 8.16. Show that if the population mean is indeed 48.2333 and the ...
Alex97's user avatar
  • 119
2 votes
0 answers
22 views

Separating labelled points with a plane, minimizing label variance

Suppose we have observations with associated labels $\{({\bf x}_1, y_1), ({\bf x}_2, y_2), \dots, ({\bf x}_n, y_n)\}$ where ${\bf x}_i \in \mathbb{R}^d$ and $y_i \in \mathbb{R}$. Can we efficiently ...
orlp's user avatar
  • 13.6k
1 vote
0 answers
14 views

Tracking approximate values of specific percentiles

At the moment I use HdrHistogram to track approximate distribution of a stream of values. But I don't really need all percentiles, just three of them. Is there some algorithm to track specific ...
synapse's user avatar
  • 111
3 votes
1 answer
164 views

Differential Privacy with only positive noise

The Laplace mechanism is a standard way of making the output of a function $f$ differentially private. More concretely, let $\Delta_f$ be the sensitivity of $f$, i.e. the maximum value by which the ...
Cryptonaut's user avatar
1 vote
1 answer
62 views

How to implement conditional probability distribution on set-valued Random Variables

I'm trying to implement conditional probability distribution when the events of two RVs are sets. If I try to extrapolate concepts from real or categorical variables to sets things become confusing ...
Nacho's user avatar
  • 11
2 votes
1 answer
40 views

Averaging a list of variances

In a setting where I have n clients each owns a subset of the dataset, each computes the mean and variance on his data and send them to the server. The server would average all means and variances. ...
Meryem Janati's user avatar
2 votes
1 answer
58 views

Is this statistical group summation unambiguously reversible?

Let $X$ be a finite multisubset of $\mathbb{N}^2$. Let's introduce the following notation: $A$ is a set of all first elements of pairs from $X$ and $B$ is a set of all second elements of pairs from $X$...
Tobias Hermann's user avatar
2 votes
0 answers
26 views

Algorithm to mapping given probabilities to empirical probabilities

Consider following problem statement: You have given $n$ actions. You can perform any of them. Each action gives you success with some probability. The challenge is to perform given finite number of ...
Rnj's user avatar
  • 235
1 vote
2 answers
167 views

Find the average number of steps to sort an array by randomly selecting two elements

I have sequence of an unique numbers from 1 to 10 in randomly order (for example: list = [7, 5, 3, 4, 2, 6, 10, 1, 9, 8]). I can choose two random number and if the list from left number larger then ...
andkot's user avatar
  • 11
1 vote
1 answer
22 views

SGD statistical guarantee

I have a question regard online learning with SGD. Is there a way to give a statistical guarantee that the value obtained after $n$ samples deviates at most $\epsilon$ from the real value? Thank you ...
Mark Regev's user avatar
0 votes
0 answers
35 views

How to handle distribution of values with same attributes into different classes

I'm a student studying a data mining course and have come across a problem. I need to explain the problem with the help of an example scenario as I do not know how to explain the problem in any other ...
mahesh Rao's user avatar
1 vote
1 answer
53 views

Chebyshev inequality comparison

Given $n$ distinct values $(x_i)_{i=1}^{n}$ with mean $\mu$ and standard deviation $s$, for all $i$, we have $|x_i−\mu| ≤ s \sqrt{n − 1}$. How does this inequality compare with Chebyshev inequality as ...
user avatar
3 votes
1 answer
1k views

Efficiently selecting a random subset of size $m$ from a set of size $n$

This is a cross post of my question here on math.se. I have a list of $n$ items and would like to randomly select an $m$ set from it efficiently (in terms of time complexity). Also, I want all ...
Mathew's user avatar
  • 229
2 votes
0 answers
61 views

In a machine learning system, why use differentially private SGD if our input data is already perturbed by a DP mechanism?

I'm trying to implement my own version of a deep neural network with differential privacy to preserve the privacy of the parties involved in the training dataset. I'm using the method by Abadi et al. ...
Saam's user avatar
  • 121
0 votes
1 answer
46 views

Gaussian distribution with condition?

What does this expression mean? Normal distribution with condition I am reading a research paper and found the following expression (Eq.28 in the paper below). It means a Gaussian distribution, but ...
salto's user avatar
  • 3
1 vote
2 answers
77 views

Algorithm for Estimating Number of Unique Monthly Visitors

Is there a way to estimate the number of unique monthly visitors to a site based on a limited sample of one week of data? I have information about when a given user visited the site. This isn't as ...
malisper's user avatar
  • 111
9 votes
1 answer
5k views

What is the optimal algorithm for playing the hangman word game?

Suppose we are playing the game hangman. My opponent and I both have access to the dictionary during the game. My opponent picks a word from the dictionary with knowledge of the algorithm which I will ...
zfj3ub94rf576hc4eegm's user avatar
1 vote
1 answer
40 views

Minimizing Trimmed Distances

I'm trying to understand what is the minimum of the following function, $$ f(\mu) = \frac{1}{n}\sum_{i=1}^n F\left(\frac{\pi(i)}{n}\right) (x_i - \mu )^2 $$ where $F$ is a step function that assign $...
Andrea's user avatar
  • 137
0 votes
0 answers
35 views

Does this problem have a formal name?

I have come across the following problem but am unable to understand the solution for it. Hence I would like to know if it has a formal name then, I can search for it and read about it in more detail. ...
ng.newbie's user avatar
  • 215
0 votes
0 answers
91 views

How to find clusters of a set of points in n-dimensional space that are furthest from unwanted points

I have a list of 25 points and their coordinates in a 512-dimensional space. I have 8 target points and 17 points I need to avoid (the 17 points to avoid also have differences in priority of how ...
disdyakis's user avatar
1 vote
1 answer
454 views

Amount of expected loop iterations when searching an array by random index

Lets say we have an array A of size n. It has 1 as its first index and n as its last index. It contains a value x, with x occurring k times in A where 1<=k<=n If we have a search algorithm like ...
Enkrypton's user avatar
0 votes
0 answers
22 views

Kullback-Liebler Divergence

For $P(x)=N(\mu,\sigma^2)$ and $Q(x)=N(0,1)$ I am supposed to calculate $KL(P(x)||Q(x))$, here is what I did \begin{align*} KL(P(x)||Q(x)) & = \int P(x) \cdot \log\left(\frac{P(x)}{Q(x)}\...
LRS25's user avatar
  • 11