Tag: random

Complexity of Merge Sort that splits in a random position

I got a question that I don’t fully understand: Given a new algorithm to merge sort (AKA mergesort2) that instead of splitting the list in the middle it splits the list in a random number between 1- n-1. Also, we know the probability of getting 1 is 2/n and to every other number 1/n.

I have tried again and again and came up with the regular $ \theta \ (n*logn)$ of the merge sort algorithm but I’m not sure about it.

Pseudo-Code:

   MergeSort2(A,p,q)    if(p=q) then return    i = random number from (1...q-p)    MergeSort2(A,p,p+i-1)    MergeSort2(A,p+i,q)    Merge(A,p,p+i-1,q)

How do I calculate properly the complexity of the given algorithm?

Do advice.

Improving speed of Binomial and Multinomial Random Draws

A number of users have discussed the speed of Random number generation in Mathematica.

The Binomial and Multinomial random number generators in Mathematica are fast if multiple draws are needed for the same distribution parameters. For example, generating 500000 draws from the Binomial distribution is very quick

In[30]:= AbsoluteTiming[  RandomVariate[BinomialDistribution[100, 0.6], 500000];]  Out[30]= {0.017365, Null}

However, the speed is slow compared to that in R and Julia when the parameters change across draws, as may be required when performing certain Monte Carlo simulations.

For example, if we have a vector nvec that contains the number of trials for each draw and a vector pvec that contains the corresponding probabilities of success. 

nvec = RandomInteger[{5, 125}, 500000];  pvec = RandomReal[{0, 1}, 500000];

Then we have 

In[28]:= AbsoluteTiming[  Mean[Table[     RandomVariate[BinomialDistribution[nvec[[i]], pvec[[i]]]], {i, 1,       Length@nvec}]] // N  ]  Out[28]= {36.2144, 32.5283}

This hit in speed most probably stems from how these are implemented internally in Mathematica.

Are there alternate methods that are fast for the case when the parameter distribution changes across the draws?

Probability that maximal elements has the same position in samples from correlated random variables

Let $ x$ and $ y$ be two correlated random variable (say, standard normal) with correlation coefficient $ \rho>0$ . Let $ X= \{x_1, x_2, …, x_L\}$ and $ Y= \{y_1, y_2, .. y_L\}$ be samples of size $ L$ from $ x$ and $ y$ respectively.

What is the probability that $ \mbox{argmax}\ X = \mbox{argmax}\ Y$ .

Alternatively, suppose that $ x_1$ is maximal element, what is the probability that $ y_1$ is maximal too.

Any references pointing to the solution of either question would also be appreciated.

Generating Biased Random Values (Walker’s Alias Method)

Am simply wondering if I made any egregious mistakes while implementing the Alias Method as an IEnumerator<TElement>; would also like to know if there are any sorts of general improvements that can be made to the design of the class.

Usage:

var rng = Pcg32XshRr.New(0, 1); var generator = ProbabilisticEnumerator     .New(         elementWeights: new Dictionary<string, int> {             { "A", 1 },             { "B", 2 },             { "C", 4 }         },         randomNumberGenerator: rng     )     .Take(100000); var summary = generator     .GroupBy(item => item)     .Select(item => new {         Element = item.Key,         Count = item.Count(),     })     .OrderBy(item => item.Element);  foreach (var item in summary) {     Console.WriteLine($  "{item.Element} | {item.Count}"); }

Code:

Nuget Package

Source Repository

/// <summary> /// Represents an enumerator that yields elements in accordance with the rules descibed by a probability table; relies on Michael D Vose's implementation of <a href="https://en.wikipedia.org/wiki/Alias_method">Walker's Alias Method.</a> /// </summary> /// <typeparam name="TElement">The type of elements encapsulated by the enumerator.</typeparam> /// <remarks> /// Derived from https://github.com/BlueRaja/Weighted-Item-Randomizer-for-C-Sharp. /// </remarks> public class ProbabilisticEnumerator<TElement> : IEnumerable<TElement>, IEnumerator<TElement> {     private readonly struct ElementMetadata     {         public int ActualIndex { get; }         public int AliasedIndex { get; }         public int Threshold { get; }          public ElementMetadata(int actualIndex, int aliasedIndex, int biasAreaSize) {             ActualIndex = actualIndex;             AliasedIndex = aliasedIndex;             Threshold = biasAreaSize;         }     }      private readonly ElementMetadata[] m_elementMetadata;     private readonly TElement[] m_elements;     private readonly int m_heightPerRectangle;     private readonly IUniformlyDistributedRandomNumberGenerator m_randomNumberGenerator;      /// <summary>     /// Gets the next random element.     /// </summary>     public TElement Current {         get {             var elementMetadata = m_elementMetadata;             var elements = m_elements;             var heightPerRectangle = m_heightPerRectangle;             var randomNumberGenerator = m_randomNumberGenerator;             var randomHeight = randomNumberGenerator.NextInt32(0, heightPerRectangle);             var randomMetadata = elementMetadata[randomNumberGenerator.NextInt32(0, (elementMetadata.Length - 1))];              return ((randomHeight <= randomMetadata.Threshold) ? elements[randomMetadata.ActualIndex] : elements[randomMetadata.AliasedIndex]);         }     }     /// <summary>     /// Gets the next random element.     /// </summary>     object IEnumerator.Current => Current;      /// <summary>     /// Initializes a new instance of the <see cref="ProbabilisticEnumerator{TElement}"/> class.     /// </summary>     /// <param name="elementWeights">The collection of element-to-weight pairs that defines the rules for the table.</param>     /// <param name="randomNumberGenerator">The source of random numbers that will be used to perform extract elements from the table.</param>     private ProbabilisticEnumerator(IReadOnlyDictionary<TElement, int> elementWeights, IUniformlyDistributedRandomNumberGenerator randomNumberGenerator) {         if (elementWeights.IsNull()) {             throw new ArgumentNullException(paramName: nameof(elementWeights));         }          var count = unchecked((ulong)elementWeights.Count);         var elements = new TElement[count];         var index = 0;         var totalWeight = 0UL;          foreach (var kvp in elementWeights) {             var element = kvp.Key;             var weight = kvp.Value;              if (0 > weight) {                 throw new ArgumentOutOfRangeException(actualValue: weight, message: "weight must be a positive integer", paramName: nameof(weight));             }              elements[index++] = element;             totalWeight += unchecked((ulong)weight);         }          var gcd = BitwiseHelpers.GreatestCommonDivisor(count, totalWeight);         var heightPerRectangle = checked((int)(totalWeight / gcd));         var weightMultiplier = checked((int)(count / gcd));          m_elementMetadata = InitializeMetadata(elementWeights, weightMultiplier, heightPerRectangle);         m_elements = elements;         m_heightPerRectangle = heightPerRectangle;         m_randomNumberGenerator = randomNumberGenerator;     }      /// <summary>     /// Releases all resources used by this <see cref="ProbabilisticEnumerator{TElement}"/> instance.     /// </summary>     public void Dispose() { }     /// <summary>     /// Returns an enumerator that yields a random element from the table.     /// </summary>     public IEnumerator<TElement> GetEnumerator() => this;     /// <summary>     /// Returns an enumerator that yields a random element from the table.     /// </summary>     IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();     /// <summary>     /// Returns true.     /// </summary>     public bool MoveNext() => true;     /// <summary>     /// Throws <see cref="NotSupportedException"/>.     /// </summary>     public void Reset() => new NotSupportedException();      private static ElementMetadata[] InitializeMetadata(IReadOnlyDictionary<TElement, int> elementWeights, int weightMultiplier, int heightPerRectangle) {         var count = elementWeights.Count;         var elementMetadata = new ElementMetadata[count];         var index = 0;         var stackLarge = new Stack<KeyValuePair<int, int>>();         var stackSmall = new Stack<KeyValuePair<int, int>>();          foreach (var kvp in elementWeights) {             var newWeight = (kvp.Value * weightMultiplier);              if (newWeight > heightPerRectangle) {                 stackLarge.Push(new KeyValuePair<int, int>(index++, newWeight));             }             else {                 stackSmall.Push(new KeyValuePair<int, int>(index++, newWeight));             }         }          while (0 < stackLarge.Count) {             var largeItem = stackLarge.Pop();             var smallItem = stackSmall.Pop();              largeItem = new KeyValuePair<int, int>(largeItem.Key, (largeItem.Value - (heightPerRectangle - smallItem.Value)));              if (largeItem.Value > heightPerRectangle) {                 stackLarge.Push(largeItem);             }             else {                 stackSmall.Push(largeItem);             }              elementMetadata[--count] = new ElementMetadata(smallItem.Key, largeItem.Key, smallItem.Value);         }          while (0 < stackSmall.Count) {             var smallItem = stackSmall.Pop();              elementMetadata[--count] = new ElementMetadata(smallItem.Key, smallItem.Key, heightPerRectangle);         }          return elementMetadata;     }      /// <summary>     /// Initializes a new instance of the <see cref="ProbabilisticEnumerator{TElement}"/> class.     /// </summary>     /// <param name="elementWeights">The collection of element-to-weight pairs that defines the rules for the table.</param>     /// <param name="randomNumberGenerator">The source of random numbers that will be used to perform extract elements from the table.</param>     public static ProbabilisticEnumerator<TElement> New(IReadOnlyDictionary<TElement, int> elementWeights, IUniformlyDistributedRandomNumberGenerator randomNumberGenerator) => new ProbabilisticEnumerator<TElement>(elementWeights, randomNumberGenerator); }  /// <summary> /// A collection of methods that directly or indirectly augment the <see cref="ProbabilisticEnumerator{TElement}"/> class. /// </summary> public static class ProbabilisticEnumerator {     /// <summary>     /// Initializes a new instance of the <see cref="ProbabilisticEnumerator{TElement}"/> class.     /// </summary>     /// <param name="elementWeights">The collection of element-to-weight pairs that defines the rules for the table.</param>     /// <param name="randomNumberGenerator">The source of random numbers that will be used to perform extract elements from the table.</param>     public static ProbabilisticEnumerator<TElement> New<TElement>(IReadOnlyDictionary<TElement, int> elementWeights, IUniformlyDistributedRandomNumberGenerator randomNumberGenerator) => ProbabilisticEnumerator<TElement>.New(elementWeights, randomNumberGenerator); }

How do you determine if a pair of random variables are independent?

If $ A$ is a subset of $ R$ and $ X$ is a random variable. I have two variables $ X_1$ and $ X_2$ . $ I$ being $ 1$ if $ X$ in subset $ A$ and $ 0$ if not in $ A$ . Let U~$ U(0;1)$ and determine if this pair is independent. Verify your claim using simulation in Matlab.

$ $ X_1 = I_U \epsilon[0,\frac{1}{3}), X_2 = I_U\epsilon[\frac{1}{3},\frac{2}{3})$ $

I usually show my work done, but I cannot find how to determine if these are independent. My question: Please, can someone explain how to show if this pair is independent? From there, then I can attempt how to verify using Matlab.

Random walks on Complete Binary Trees

Let $ T$ be a complete binary tree of height $ n$ and root $ r$ .

A random walk starts at $ r$ , and at each step uniformly at random moves on a neighbor.

There are $ m$ random walkers all starting at $ r$ and let denote with $ H_1,\dots,H_m$ , the heights reached by the walkers after $ n$ steps.

Show that, for some constant $ C$ which do not have to depend on $ n$ and $ m$ , it holds that

$ \mathbb{P}\left(\underset{i \in [m]}\max\left|H_i – \frac{n}{3}\right| \le C \sqrt{n\ln m}\right) \ge 1 – \frac{1}{m}$

I have been trying several strategies, to appropriately define $ H_i$ as sum of random variables and similar, but no one turned out to work. Do you have any idea/suggestion to attach this problem?

Thanks in advance!

Massive Amount of Random Files appearing in Documents

Really hope someone can help me with this issue! For the past few months, I have had an annoying issue whereby I have multiple 2-character 0-byte random folders appearing within Documents, along with an index.dat file at the very top which seems to form the quickest. It appears to only happen when I use Safari, but I have become quite attached to the browser so would prefer to continue doing so.

I have tried deleting all cookies and updated to the latest OSX, but to no avail.

Would appreciate anyone able to help as it’s left me very puzzled!

Thanks in Advance,

Rob

issue

Submit random choices on Google form

I’ve written a Python script that randomly selects radio buttons for each question, and submits the google form. My main questions for improvement are:

  • Algorithm: I collect all the buttons into a 2D array, then use random.choice to select the radio buttons based on each nested array. I’m sure there’s a better way to do this, since my algorithm is basically hard coded.
  • Performance: I know random.choice takes a lot more time than other methods, but it’s the only way I know enough to write with it.
  • Wait Time: Right now, I wait .75 seconds before entering in another form. I’m wondering if there’s a way to wait for the page to load completely, rather than wait and hope that it loads fast enough to not generate a page not found error.

script.py

#run with python3 from selenium import webdriver import random import time  #Setup paths and open chrome browser chrome_path = "desktop/code/python/driver/chrome/chromedriver" website_path = "https://docs.google.com/forms/d/e/1FAIpQLSdcWrIYQlNbywuLg276z0CbBw-GyQOj_s2ncR9qVA7F7FPARQ/viewform" driver = webdriver.Chrome(chrome_path) driver.get(website_path)  #Define options based on each section  #EXCEPT: 9 18 25 28 31 (for text areas) options = [     [0, 1, 2, 3],     [4, 5, 6],     [7, 8],     [10, 11],     [12, 13, 14, 15],     [16, 17],     [19, 20, 21],     [22, 23, 24],     [26, 27],     [29, 30],     [32, 33] ]  #Main loop def main(counter):     count = counter + 1      #Collect all buttons on page and submit button     buttons = driver.find_elements_by_xpath("//*[@class='freebirdFormviewerViewItemsRadioOptionContainer']")     submit = driver.find_element_by_xpath("//*[@class='quantumWizButtonPaperbuttonLabel exportLabel']")      """     Randomly chooses an option from the 2D array based on what i is, and that     number is the index of `buttons`, which the button in that index will be clicked     """     for i in range(len(options)):         buttons[random.choice(options[i])].click()      #Submit form     submit.click()      #Go to previous page, which will be the form     driver.execute_script("window.history.go(-1)")      #Output how many forms have been submitted thus far     print(f"Form #{count} has been submitted!")      #Wait for page to load again, then call main to run again     time.sleep(.75)     main(count)   if __name__ == '__main__':     main(0)