If memory is an issue you could split the 10^x to smaller batches and combine the total count
FromDigits[#,2]&/@Tuples[{0,1},4](*whichintegers*)outcomes=FromDigits[#,2]&/@{{0,0,0,0},{0,0,1,1}}(*whichintegersforoutcomes*)goal=10;(*10^goal*)Grid@Table[{{i,j=goal-i},(cointosses=10^i;vals=ConstantArray[0,Length[outcomes]];Do[datasetI=RandomInteger[{0,15},cointosses];vals+=Values[KeyTake[Counts[datasetI],outcomes]],10^j];N[First@vals/Last@vals])//AbsoluteTiming},{i,3,7}]
Out[]=
{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}
Out[]=
{0,3}
Out[]=
{3,7} | {189.431,0.999901} |
{4,6} | {60.1493,0.999896} |
{5,5} | {46.2618,1.} |
{6,4} | {68.1016,0.999891} |
{7,3} | {56.6221,0.999937} |