Mathematics desk
< July 26	<< Jun \| July \| Aug >>	July 28 >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

July 27

Uniform mapping function

I need to program a mapping function that for a given input will return a value uniformly selected from an arbitrary array when the input and output ranges are of different length (and won't necessarily have common factors, i.e. they aren't congruent [if I'm using that term right]). For example, if my array is a..z, (array[0]="a", array[1]="b"...array[25]=z), and my input is a random number between 0 and 31, how can I ensure the output of my function is uniform? Doing a modulo would introduce artifacts into my output, because the first 8 elements (0-7) have more of chance of showing up (0-7 and 26-31), breaking the uniform distribution of the output. I could just discard values out of range, but then I'm wasting my input data. Ultimately my question is how I can get uniformly distributed output from a function wasting as little input data as possible. Thanks. Shadowjams (talk) 18:05, 27 July 2010 (UTC)[reply]

Use some form of dithering, perhaps? Qwfp (talk) 18:41, 27 July 2010 (UTC)[reply]

Hmm. I'm still stuck. The dithering article's about image dithering and I don't think they care about the output being uniform. Maybe I can solve this a different way... can I make a non-uniform distribution uniform? Shadowjams (talk) 21:26, 27 July 2010 (UTC)[reply]

I suggest you take another look at dither#Digital audio; that's not about image dithering and the example seems to me to be analogous to your problem. Sorry i won't have time to respond in more detail in the next day or so. Qwfp (talk) 21:44, 27 July 2010 (UTC)[reply]

This is impossible. That is, if your input is uniform, and the function is fixed and deterministic, then the output can be uniform only if the number of possible inputs is a multiple of the number of possible outputs. So if your output has 26 values then the input can have 26, 52, etc. values.

However. It is very probable that there is really something else you want to do, which is solvable, but you have restricted the available solutions with the way you have described the problem. If you tell us what you need this for, we can help you come up with a solution. -- Meni Rosenfeld (talk) 05:52, 28 July 2010 (UTC)[reply]

Are you trying to write a randomness extractor? In practice you should probably just take enough of your 0-31 inputs to make an unpredictable seed (100+ bits, say), and use it to initialize a cryptographic PRNG and stop worrying. Fortuna is an elegant way though not very efficient way to occasionally fold new entropy into the generator. 67.122.211.208 (talk) 08:57, 28 July 2010 (UTC)[reply]

Technically, what you say can be accomplished by something simple like this:

int map_random(int len,int choice) {
  static int last;  /* 'static' means retained between function calls */
  if(choice<len) last=choice;
  else last=(last+choice)%len;
  return last;
}

Then the output is uniformly drawn from [0,len), but the outputs aren't independent. (Also, this function isn't "fixed" as Meni used it.) If instead you have a function already that returns in one range, you can reduce the waste by doing this:

#define MANY 42  /* make bigger to waste less randomness and more memory */
int map_random(int len,int (*src)(),int slen) {
  static bignum_t buf,lim;  /* for simplicity, pretend we can use regular operators on them */
  int ret,i;
  if(lim<len) {
    lim=1; buf=0;
    for(i=0;i<MANY;++i) {
      lim*=slen; buf=buf*slen+src();
    }
  }
  ret=buf%len;
  buf/=len; lim/=len;
  return ret;
}

This treats the remap as a change of number base; if MANY is large, almost all the input bits will be used. It's possible to never waste bits with a similar approach, but only at the expense of a memory requirement that grows linearly with the number of function calls (forever!). Does that help? --Tardis (talk) 14:48, 28 July 2010 (UTC)[reply]

Thank you to everyone--this is extremely helpful. I should have explained before, I need the function to be deterministic. I suppose the dithering might work for an entropy extractor, which is part of what I'm interested in, and Meni's response is perfect because I had an instinct that this might be an impossible request, but I didn't know for sure.

I will take a look at Fortuna. I'm interested in incorporating multiple sources of entropy of varying lengths, so that's one, but I'm also interested in how reduce functions work for rainbow tables. That would need to be deterministic so dithering using the same source for input in a standardized way might work for that, but even if I'm wasting fewer bits, I'm still wasting some.

Tardis: thank you for the code too. I had thought about using the extra bits as a second random "stream" that I could then fold back into the main stream when it reached the right size... which I suppose is a practical solution. Again thanks, all of these responses are very helpful. Shadowjams (talk) 16:31, 30 July 2010 (UTC)[reply]

Infinite sequence

What's the value of 1 - 1 + 1 - 1 + 1 - 1 + ...? --138.110.206.99 (talk) 19:35, 27 July 2010 (UTC)[reply]

Indeterminate. It oscillates between 1 and 0. -- SGBailey (talk) 19:45, 27 July 2010 (UTC)[reply]

Your series is an example of a geometric series. A general geometric series is given by

\sum _{k=0}^{\infty }ar^{k}=a+ar+ar^{2}+ar^{3}+ar^{4}+\cdots ,

where a and r are real numbers. In your case a = 1 and r = −1. For a convergent series you need the absolute value of r to be less than 1; i.e. −1 < r < 1. — Fly by Night (talk) 21:26, 27 July 2010 (UTC)[reply]

If I said 1/2 would you actually believe me? That's the sort of power I like. I see myself in the guise of the baddie Thulsa Doom in Conan the Barbarian (film) calling a young girl forward to fall to her death. :) Dmcq (talk) 21:38, 27 July 2010 (UTC)[reply]

You know, most of the time I do not actually understand what you say ... ;) PS T 01:02, 28 July 2010 (UTC)[reply]

This can be evaluated using a resummation method such as e.g. Borel resummation:

$\sum _{k=0}^{\infty }(-1)^{k}=\sum _{k=0}^{\infty }{\frac {(-1)^{k}}{k!}}k!=\sum _{k=0}^{\infty }{\frac {(-1)^{k}}{k!}}\int _{0}^{\infty }x^{k}\exp(-x)dx$

Let's now interchange summation and integration, which is an illegal operation. Here you have to consider that the original series is not convergent and using only legal operations you cannot get an unambiguous answer. So, if a method does yield an answer, it necessarily has to indroduce an illegal step somewhere. Now, if we assume that the original series itself was obtained form some well defined mathematical expression and then it was expanded in a series expansion that does not converge, then the problem is to guess what the original expression is.

Here we can assume that the mistake did not introduce nontrivial information (it is not like someone adding random numbers to the terms of a convergent series), so the information about the correct answer should be present in the divergent series. If we then apply some generic formal manipulation that for this series is an illegal operation but which does turn it into a convergent expression, then chances are that you get the original mathematical expression back.

So, let's see what we get in this case:

$\int _{0}^{\infty }\exp(-x)\sum _{k=0}^{\infty }{\frac {(-x)^{k}}{k!}}dx=\int _{0}^{\infty }\exp(-2x)dx={\frac {1}{2}}$

Count Iblis (talk) 15:03, 28 July 2010 (UTC)[reply]

Compliments for a truly misleading answer! --pm a 23:12, 29 July 2010 (UTC)[reply]